Widest Vertical Area Between Two Points Containing No Points - Leetcode Solution

Problem:

Given n points on a 2D plane, find the widest vertical area between two points such that no points are inside the area.

Solution:

The problem asks us to find the widest vertical area between two points, such that no other points lie inside the area. We can solve this problem in several ways, two of which are discussed below:

1. Brute Force

In the brute force approach, we can consider every pair of points and calculate the vertical distance between them. We can keep track of the maximum vertical distance we find and return it at the end. The time complexity of this approach will be O(n^2).

Algorithm:

1. Sort the given points based on their x-coordinates.
2. For every pair of points (p1, p2) where p1 and p2 have different x-coordinates and p1.x <= p2.x, a. Find the vertical distance between the two points and store it in a variable max_vertical_distance. b. Iterate over all the remaining points and check if they lie within the vertical distance between p1 and p2. If yes, ignore this pair and move on to the next pair of points. c. Update max_vertical_distance with the new value if it is greater than the current max_vertical_distance value.
3. Return max_vertical_distance.

Time Complexity: O(n^2)

2. Using Two-Pointer Approach

In the two-pointer approach, we can maintain two pointers left and right, initially pointing to the first and last points respectively. We can calculate the vertical distance between these two points and keep track of the maximum vertical distance we find. We can then move the pointer corresponding to the smaller x-coordinate. This is because, any point inside the widest vertical area must have an x-coordinate larger than the left pointer and smaller than the right pointer. Therefore, moving the pointer with the smaller x-coordinate will ensure that no other points lie inside the area. We can continue this until the left and right pointers meet.

Algorithm:

1. Sort the given points based on their x-coordinates.
2. Initialize two pointers left and right pointing to the first and last points respectively.
3. Calculate the vertical distance between left and right and store it in a variable max_vertical_distance.
4. While left < right, a. Calculate the vertical distance between left and right and update max_vertical_distance if it is greater than the current value. b. If the next point after left has a greater y-coordinate than the next point after right, move the right pointer one position to the left, otherwise move the left pointer one position to the right.
5. Return max_vertical_distance.

Time Complexity: O(n log n)

Note: In both approaches, the points are sorted based on their x-coordinates, which takes O(n log n) time. However, the two-pointer approach has a lower time complexity for finding the widest vertical area as compared to the brute force approach.

1