Widest Vertical Area Between Two Points Containing No Points

Difficulty: Easy | Acceptance: 87.10% | Paid: No Topics: Array, Sorting

Given n points on a 2D plane, find the widest vertical area between two points such that no points lie inside the area.

A vertical area is an area of fixed-width extending infinitely along the y-axis. The widest vertical area is the one with the maximum width.

Note that points on the edge of a vertical area are not considered included in the area.

• Examples
• Constraints
• Sorting
• Brute Force

Examples

Example 1:

Input: points = [[8,7],[9,9],[7,4],[9,7]]
Output: 1
Explanation: The red-shaded region is between x = 7 and x = 9, which has a width of 1. No other points lie inside this region.

Example 2:

Input: points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]
Output: 3
Explanation: The red-shaded region is between x = 5 and x = 8, which has a width of 3. No other points lie inside this region.

Constraints

- n == points.length
- 2 <= n <= 10^5
- points[i].length == 2
- 0 <= xi, yi <= 10^9

Sorting

Intuition The y-coordinates are irrelevant to the width of the vertical area. The problem reduces to finding the maximum difference between consecutive x-coordinates after sorting them.

Steps

• Extract all x-coordinates from the points array.
• Sort the array of x-coordinates.
• Iterate through the sorted array to find the maximum difference between adjacent elements.
• Return the maximum difference found.

class Solution:
    def maxWidthOfVerticalArea(self, points: list[list[int]]) -> int:
        xs = sorted([p[0] for p in points])
        max_width = 0
        for i in range(1, len(xs)):
            max_width = max(max_width, xs[i] - xs[i-1])
        return max_width

Complexity

• Time: O(N log N) due to sorting.
• Space: O(N) to store the x-coordinates.
• Notes: This is the most efficient approach for the given constraints.

Brute Force

Intuition Check every possible pair of points to see if they form a valid empty vertical area, and track the maximum width found.

Steps

• Iterate through all pairs of points (i, j).
• For each pair, determine the left and right x-coordinates.
• Check if any other point k has an x-coordinate strictly between left and right.
• If no such point exists, update the maximum width with the difference between right and left.

class Solution:
    def maxWidthOfVerticalArea(self, points: list[list[int]]) -> int:
        n = len(points)
        max_width = 0
        for i in range(n):
            for j in range(i + 1, n):
                x1, x2 = points[i][0], points[j][0]
                if x1 == x2: continue
                left, right = min(x1, x2), max(x1, x2)
                valid = True
                for k in range(n):
                    if k == i or k == j: continue
                    if left < points[k][0] < right:
                        valid = False
                        break
                if valid:
                    max_width = max(max_width, right - left)
        return max_width

Complexity

• Time: O(N³) in the worst case.
• Space: O(1).
• Notes: This approach is not efficient for large inputs and will result in a Time Limit Exceeded error on LeetCode.