Welcome to Subscribe On Youtube
1637. Widest Vertical Area Between Two Points Containing No Points
Description
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 <= 109
Solutions
Solution 1: Sorting
We can sort the array $points$ in ascending order of $x$ and obtain the maximum value of the difference between adjacent points $x$.
Time complexity $O(n \times \log n)$, space complexity $O(\log n)$. Where $n$ is the length of the array $points$.
Solution 2
The time complexity of sorting in method 1 is $O(n \times \log n)$. In fact, we can use the idea of bucket sorting to reduce the time complexity to $O(n)$.
We put the abscissa of the array $points$ into the array $nums$.
Assume that the array $nums$ has $n$ elements, and all elements are from $nums_0$ to $nums_{n - 1}$ from small to large, and the maximum distance is $maxGap$. Consider the difference between the largest and smallest element in an array:
\[nums_{n - 1} - nums_0 = \sum_{i = 1}^{n - 1} (nums_i - nums_{i - 1}) \le{maxGap} \times (n - 1)\]So $maxGap \ge \dfrac{nums_{n - 1} - nums_0}{n - 1}$, i.e. the maximum spacing is at least $\dfrac{nums_{n - 1} - nums_0}{n - 1}$.
You can use the idea of bucket sorting to set the size of the bucket (that is, the maximum number of different elements each bucket contains) to $\dfrac{nums_{n - 1} - nums_0}{n - 1}$, and evenly distribute the elements into each bucket according to the element value. Then the difference between any two elements in the same bucket is less than ${maxGap}$, and the two elements with a difference of ${maxGap}$ must be in two different buckets. For each bucket, maintain the minimum value and maximum value in the bucket. Initially, the minimum value and maximum value in each bucket are positive infinity and negative infinity respectively, indicating that there are no elements in the bucket.
Iterate over all elements in the array ${nums}$. For each element, calculate the number of the bucket to which the element should be assigned based on the difference between the element and the smallest element and the size of the bucket. This ensures that the elements in the bucket with a smaller number are smaller than the elements in the bucket with a larger number. The element value is used to update the minimum and maximum values in the bucket where the element is located.
After traversing the array, the minimum and maximum values in each non-empty bucket can be determined. Each bucket is traversed in order from small to large according to the bucket number. The minimum value of the current bucket and the maximum value of the previous non-empty bucket are the sorted adjacent elements. The difference between the two adjacent elements is calculated and the maximum distance is updated. The maximum distance can be obtained after traversing the bucket.
Time complexity $O(n)$, space complexity $O(n)$. Where $n$ is the length of the array $points$.
-
class Solution { public int maxWidthOfVerticalArea(int[][] points) { Arrays.sort(points, (a, b) -> a[0] - b[0]); int ans = 0; for (int i = 0; i < points.length - 1; ++i) { ans = Math.max(ans, points[i + 1][0] - points[i][0]); } return ans; } } // Solution 2 class Solution { public int maxWidthOfVerticalArea(int[][] points) { int n = points.length; int[] nums = new int[n]; for (int i = 0; i < n; ++i) { nums[i] = points[i][0]; } final int inf = 1 << 30; int mi = inf, mx = -inf; for (int v : nums) { mi = Math.min(mi, v); mx = Math.max(mx, v); } int bucketSize = Math.max(1, (mx - mi) / (n - 1)); int bucketCount = (mx - mi) / bucketSize + 1; int[][] buckets = new int[bucketCount][2]; for (var bucket : buckets) { bucket[0] = inf; bucket[1] = -inf; } for (int v : nums) { int i = (v - mi) / bucketSize; buckets[i][0] = Math.min(buckets[i][0], v); buckets[i][1] = Math.max(buckets[i][1], v); } int prev = inf; int ans = 0; for (var bucket : buckets) { if (bucket[0] > bucket[1]) { continue; } ans = Math.max(ans, bucket[0] - prev); prev = bucket[1]; } return ans; } } -
class Solution { public: int maxWidthOfVerticalArea(vector<vector<int>>& points) { sort(points.begin(), points.end()); int ans = 0; for (int i = 0; i < points.size() - 1; ++i) { ans = max(ans, points[i + 1][0] - points[i][0]); } return ans; } }; // Solution 2 class Solution { public: int maxWidthOfVerticalArea(vector<vector<int>>& points) { int n = points.size(); vector<int> nums; for (auto& p : points) { nums.push_back(p[0]); } const int inf = 1 << 30; int mi = inf, mx = -inf; for (int v : nums) { mi = min(mi, v); mx = max(mx, v); } int bucketSize = max(1, (mx - mi) / (n - 1)); int bucketCount = (mx - mi) / bucketSize + 1; vector<pair<int, int>> buckets(bucketCount, {inf, -inf}); for (int v : nums) { int i = (v - mi) / bucketSize; buckets[i].first = min(buckets[i].first, v); buckets[i].second = max(buckets[i].second, v); } int ans = 0; int prev = inf; for (auto [curmin, curmax] : buckets) { if (curmin > curmax) continue; ans = max(ans, curmin - prev); prev = curmax; } return ans; } }; -
class Solution: def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int: points.sort() return max(b[0] - a[0] for a, b in pairwise(points)) # Solution 2 class Solution: def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int: nums = [x for x, _ in points] n = len(nums) mi, mx = min(nums), max(nums) bucket_size = max(1, (mx - mi) // (n - 1)) bucket_count = (mx - mi) // bucket_size + 1 buckets = [[inf, -inf] for _ in range(bucket_count)] for x in nums: i = (x - mi) // bucket_size buckets[i][0] = min(buckets[i][0], x) buckets[i][1] = max(buckets[i][1], x) ans = 0 prev = inf for curmin, curmax in buckets: if curmin > curmax: continue ans = max(ans, curmin - prev) prev = curmax return ans -
func maxWidthOfVerticalArea(points [][]int) (ans int) { sort.Slice(points, func(i, j int) bool { return points[i][0] < points[j][0] }) for i, p := range points[1:] { ans = max(ans, p[0]-points[i][0]) } return } // Solution 2 func maxWidthOfVerticalArea(points [][]int) (ans int) { n := len(points) nums := make([]int, 0, n) for _, p := range points { nums = append(nums, p[0]) } const inf = 1 << 30 mi, mx := inf, -inf for _, v := range nums { mi = min(mi, v) mx = max(mx, v) } bucketSize := max(1, (mx-mi)/(n-1)) bucketCount := (mx-mi)/bucketSize + 1 buckets := make([][]int, bucketCount) for i := range buckets { buckets[i] = []int{inf, -inf} } for _, v := range nums { i := (v - mi) / bucketSize buckets[i][0] = min(buckets[i][0], v) buckets[i][1] = max(buckets[i][1], v) } prev := inf for _, bucket := range buckets { if bucket[0] > bucket[1] { continue } ans = max(ans, bucket[0]-prev) prev = bucket[1] } return ans } -
function maxWidthOfVerticalArea(points: number[][]): number { points.sort((a, b) => a[0] - b[0]); let ans = 0; for (let i = 1; i < points.length; ++i) { ans = Math.max(ans, points[i][0] - points[i - 1][0]); } return ans; } // Solution 2 function maxWidthOfVerticalArea(points: number[][]): number { const nums: number[] = points.map(point => point[0]); const inf = 1 << 30; const n = nums.length; let mi = inf; let mx = -inf; for (const x of nums) { mi = Math.min(mi, x); mx = Math.max(mx, x); } const bucketSize = Math.max(1, Math.floor((mx - mi) / (n - 1))); const bucketCount = Math.floor((mx - mi) / bucketSize) + 1; const buckets = new Array(bucketCount).fill(0).map(() => [inf, -inf]); for (const x of nums) { const i = Math.floor((x - mi) / bucketSize); buckets[i][0] = Math.min(buckets[i][0], x); buckets[i][1] = Math.max(buckets[i][1], x); } let prev = inf; let ans = 0; for (const [left, right] of buckets) { if (left > right) { continue; } ans = Math.max(ans, left - prev); prev = right; } return ans; } -
/** * @param {number[][]} points * @return {number} */ var maxWidthOfVerticalArea = function (points) { points.sort((a, b) => a[0] - b[0]); let ans = 0; let px = points[0][0]; for (const [x, _] of points) { ans = Math.max(ans, x - px); px = x; } return ans; }; // Solution 2 /** * @param {number[][]} points * @return {number} */ var maxWidthOfVerticalArea = function (points) { const nums = points.map(point => point[0]); const inf = 1 << 30; const n = nums.length; let mi = inf; let mx = -inf; for (const x of nums) { mi = Math.min(mi, x); mx = Math.max(mx, x); } const bucketSize = Math.max(1, Math.floor((mx - mi) / (n - 1))); const bucketCount = Math.floor((mx - mi) / bucketSize) + 1; const buckets = new Array(bucketCount).fill(0).map(() => [inf, -inf]); for (const x of nums) { const i = Math.floor((x - mi) / bucketSize); buckets[i][0] = Math.min(buckets[i][0], x); buckets[i][1] = Math.max(buckets[i][1], x); } let prev = inf; let ans = 0; for (const [left, right] of buckets) { if (left > right) { continue; } ans = Math.max(ans, left - prev); prev = right; } return ans; };