Given n points on a 2D plane where points[i] = [xi, yi], Return the widest vertical area between two points such that no points are inside the area.
A vertical area is an area of fixed-width extending infinitely along the y-axis (i.e., infinite height). 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.
Example 1:
Input: points = [[8,7],[9,9],[7,4],[9,7]] Output: 1 Explanation: Both the red and the blue area are optimal.
Example 2:
Input: points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]] Output: 3
Constraints:
n == points.length2 <= n <= 105points[i].length == 20 <= xi, yi <= 109Problem Overview: You receive a list of 2D points. A vertical area is the space between two vertical lines (x = a and x = b) that contains no points between them. The task is to return the maximum width of such an area. Only the x-coordinates matter because vertical gaps depend purely on horizontal distance.
Approach 1: Sort and Compare Consecutive Differences (O(n log n) time, O(1) extra space or O(n) depending on sorting)
The key observation: the widest empty vertical region must lie between two neighboring x-coordinates after sorting. Extract all x values from the points and sort them. Then iterate through the sorted list and compute the difference between each consecutive pair. Track the maximum difference seen. Sorting ensures that any larger gap would appear between adjacent elements in the ordered sequence. This approach is simple, reliable, and commonly expected in interviews. It relies on concepts from Array traversal and Sorting.
Approach 2: Bucket Sort for Near-Constant Time Gap Calculation (O(n) time, O(n) space)
Sorting works well, but the problem can be solved in linear time using a bucket-based gap strategy similar to the maximum gap problem. First determine the global minimum and maximum x-values. Divide the range into buckets sized so that the expected gap between buckets is roughly (maxX - minX) / (n - 1). Each bucket stores only the minimum and maximum x-values that fall inside it. After distributing points into buckets, iterate through them and compute the gap between the maximum of the previous non-empty bucket and the minimum of the current one. The largest such gap is the answer. Because points inside the same bucket cannot produce the maximum gap, comparisons only occur between buckets. This method avoids full sorting while still using ideas from Array processing and distribution-based Sorting techniques.
Recommended for interviews: The sorting approach is what most interviewers expect. It is easy to implement, easy to reason about, and runs in O(n log n), which is more than sufficient for typical constraints. The bucket-based solution demonstrates deeper algorithmic knowledge and achieves O(n) time, but it is usually presented as an optimization rather than the first solution. Showing the sorting solution first proves you understand the core observation that the widest vertical area must exist between consecutive sorted x-values.
This approach involves sorting the x-coordinates of the points and then finding the maximum difference between consecutive sorted x-coordinates. This difference gives the widest vertical area between any two points.
This solution uses a simple array to extract x-coordinates, sorts it, and finds the maximum gap between consecutive sorted x-coordinates. The function qsort() is used for sorting, and a loop is used after sorting to determine the maximum width.
Time Complexity: O(n log n), due to the sorting step.
Space Complexity: O(n), due to the additional array holding the sorted x-coordinates.
Although not commonly necessary due to the constraints provided, if x-coordinates were to be over a smaller range, a variant of bucket sort could be used to place x-coordinates in a collection of buckets. This helps find consecutive x-coordinate gaps in nearly constant time, potentially improving performance by eliminating the general-purpose sort with more specialized data placement.
With constraints as large as those given, using a fine-grained approach like bucket sort isn't practical here; however, this explanation serves educational purposes.
Time Complexity: O(n) expected when bucket conditions are met.
Space Complexity: O(m) where m is the bucket range size.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Sort and Compare Consecutive Differences | Time Complexity: O(n log n), due to the sorting step. |
| Approach 2: Bucket Sort for Near-Constant Time Gap Calculation | Time Complexity: O(n) expected when bucket conditions are met. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Compare Consecutive Differences | O(n log n) | O(1)–O(n) | General case. Simplest implementation and commonly expected in coding interviews. |
| Bucket Sort Gap Calculation | O(n) | O(n) | When linear time is required or when demonstrating advanced understanding of gap-based bucket strategies. |
Wildest Vertical Area Between Two Points Containing No Points - Leetcode 1637 - Python • NeetCodeIO • 6,867 views views
Watch 9 more video solutions →Practice Widest Vertical Area Between Two Points Containing No Points with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor