Widest Vertical Area Between Two Points Containing No Points

How it works

The key insight is that a vertical area containing no points must exist between two consecutive points when sorted by x-coordinate. If we sort all points by their x-values, the widest gap between adjacent points gives us the answer directly. This works because any non-adjacent pair would have at least one point between them, making that area invalid.

Steps

1. Sort the points array by x-coordinate.
2. Iterate through consecutive pairs of sorted points.
3. For each consecutive pair, calculate the difference in their x-coordinates.
4. Return the maximum difference found.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(1) or O(n) depending on the sorting algorithm.

Things to watch for

Using Y-Coordinates Instead of X-Coordinates

The problem asks for the widest vertical area, which means we need to find gaps along the x-axis. A common mistake is to consider y-coordinates or try to compute 2D distances between points.

Checking Non-Adjacent Points After Sorting

After sorting by x-coordinate, the maximum gap must occur between consecutive points. Some attempt to check all pairs even after sorting, which is unnecessary and leads to O(n^2) complexity.

Forgetting to Sort by X-Coordinate Only

When sorting 2D points, the default sort may use both x and y coordinates for tie-breaking. While this still works, some mistakenly sort by y-coordinate or use a complex comparator when only x matters.

from typing import List

class Solution:
    def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
        points.sort()
        res = 0
        for i in range(len(points) - 1):
            res = max(res, points[i + 1][0] - points[i][0])
        return res

class Solution {
public:
    int maxWidthOfVerticalArea(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](const auto& a, const auto& b) {
            return a[0] < b[0];
        });

        int res = 0;
        for (int i = 0; i < points.size() - 1; i++) {
            res = max(res, points[i + 1][0] - points[i][0]);
        }

        return res;
    }
};