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 <= 109This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) expected when bucket conditions are met.
Space Complexity: O(m) where m is the bucket range size.
| 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. |
Wildest Vertical Area Between Two Points Containing No Points - Leetcode 1637 - Python • NeetCodeIO • 6,455 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