1637. Widest Vertical Area Between Two Points Containing No Points LeetCode Solution
In this guide, you will get 1637. Widest Vertical Area Between Two Points Containing No Points LeetCode Solution with the best time and space complexity. The solution to Widest Vertical Area Between Two Points Containing No Points problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Widest Vertical Area Between Two Points Containing No Points
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.
n == points.length
2 <= n <= 105
points[i].length == 2
0 <= xi, yi <= 109
Complexity Analysis
Time Complexity: O(\texttt{sort})
Space Complexity: O(n)
1637. Widest Vertical Area Between Two Points Containing No Points LeetCode Solution in C++
class Solution {
public:
int maxWidthOfVerticalArea(vector<vector<int>>& points) {
int ans = 0;
vector<int> xs;
for (const vector<int>& point : points) {
const int x = point[0];
xs.push_back(x);
}
ranges::sort(xs);
for (int i = 1; i < xs.size(); ++i)
ans = max(ans, xs[i] - xs[i - 1]);
return ans;
}
}; /* code provided by PROGIEZ */
1637. Widest Vertical Area Between Two Points Containing No Points LeetCode Solution in Java
class Solution {
public int maxWidthOfVerticalArea(int[][] points) {
int ans = 0;
int[] xs = new int[points.length];
for (int i = 0; i < points.length; ++i)
xs[i] = points[i][0];
Arrays.sort(xs);
for (int i = 1; i < xs.length; ++i)
ans = Math.max(ans, xs[i] - xs[i - 1]);
return ans;
}
} // code provided by PROGIEZ
1637. Widest Vertical Area Between Two Points Containing No Points LeetCode Solution in Python
class Solution:
def maxWidthOfVerticalArea(self, points: list[list[int]]) -> int:
xs = sorted([x for x, _ in points])
return max(b - a for a, b in itertools.pairwise(xs)) # code by PROGIEZ
