Widest Vertical Area Between Two Points Containing No Points

Problem Statement

Given a set of n points on a 2D Cartesian plane, your task is to determine the largest possible width of a vertical area such that there are no points inside this vertical space. Each point is represented as a coordinate pair [xi, yi]. A vertical area is described as a segment parallel to the y-axis (extending infinitely in both upward and downward directions) with a specific width, and the edge of this vertical area can touch points but should not have any points located strictly within. The objective is to identify this widest vertical segment and return its width.

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

Approach and Intuition

To solve this problem, one effective strategy involves focusing on the x-coordinates of the points, given that the width of the area we are calculating is purely horizontal and the area extends infinitely vertically.

1. Extract the x-coordinates from the given list of points.
2. Sort these x-coordinates in ascending order.
3. Compute the difference between consecutive x-coordinates to find all possible widths of the vertical areas.
4. The largest of these differences will be the answer, as it represents the width of the widest vertical area where no points lie strictly within.

The intuition behind sorting the x-coordinates is that any potential maximum-width vertical area would need to be between two points that are farthest apart from each other horizontally with no other points in between. Thus, by examining the differences between consecutively sorted x-coordinates, we can guarantee finding such an area. This is a direct and efficient approach as it leverages sorting followed by a linear pass through the list of coordinates.

Solutions

class Solution {
public:
    int maxVerticalWidth(vector<vector<int>>& coords) {
        sort(coords.begin(), coords.end());
            
        int max_width = 0;
        for (int i = 1; i < coords.size(); i++) {
            max_width = max(max_width, coords[i][0] - coords[i - 1][0]);
        }
            
        return max_width;
    }
};