034.md

1637. Widest Vertical Area Between Two Points Containing No Points

Difficulty: 🟡 Medium

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.

Examples:

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.length
• 2 <= n <= 105
• points[i].length == 2
• 0 <= xi, yi <= 109

Solutions

O(n*log(n)) solution in Python3

class Solution:
    def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
        points = sorted(points, key=lambda point: point[0])
        maximum = 0
        for i in range(1, len(points)):
            maximum = max(points[i][0]-points[i-1][0], maximum)
        return maximum

The given solution finds the widest vertical area between two points by sorting the points based on their x-coordinates and iterating through the sorted list to calculate the maximum width.

The algorithm works as follows:

1. Sort the points array in ascending order based on the x-coordinate using the sorted() function and a lambda function.
2. Initialize a variable, maximum, to 0, which will store the maximum width of the vertical area.
3. Iterate through the sorted points array from index 1 to the end.
   • Calculate the width between the current point and the previous point by subtracting the x-coordinate of the previous point from the x-coordinate of the current point.
   • Update maximum with the maximum value between the calculated width and the current maximum.
4. Return the maximum value, which represents the widest vertical area between two points.

The algorithm finds the widest vertical area by calculating the width between adjacent points and keeping track of the maximum width.

Analysis of Time and Space Complexity

The time complexity of this algorithm is O(n log n), where n is the number of points. The algorithm performs a sorting operation on the points array, which has a time complexity of O(n log n). The subsequent iteration through the sorted array has a linear time complexity of O(n).

The space complexity of the algorithm is O(n) as it uses additional space to store the sorted points array.

Summary

The given solution finds the widest vertical area between two points on a 2D plane by sorting the points array based on their x-coordinates and calculating the maximum width. It has a time complexity of O(n log n) and a space complexity of O(n), making it an efficient solution for the problem at hand.

NB: If you want to get community points please suggest solutions in other languages as merge requests.