Vultr DocsLatest Content

Widest Vertical Area Between Two Points Containing No Points

Updated on 27 June, 2025
Widest Vertical Area Between Two Points Containing No Points header image

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

  • C++
  • Java
cpp 
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;
    }
};

The given problem aims to find the widest vertical gap between two points on a coordinate plane where no points lie within that gap along the x-axis. This solution is implemented in C++ utilizing the vector data structure for handling the list of coordinate points.

  • Start by sorting the coords vector to arrange the points based on their x-coordinates. This makes it easier to compare adjacent points, eliminating the need to check every pair of points, thus optimizing the process.
  • Initialize max_width to zero. This variable will store the maximum width found between two points.
  • Iterate through the sorted list starting from the second element (index 1). For each point, calculate the gap to the previous point (difference in their x-coordinates).
  • Update max_width if the current gap is larger than any previously found gap.
  • After the loop, max_width contains the width of the widest vertical area between adjacent points on the x-axis that contains no other points.

The function employs an efficient approach to solving the problem by focusing only on neighboring points post-sorting, leveraging the properties of sorted arrays, which reduces the problem complexity. This straightforward method ensures that the maximum vertical width is determined with minimal computational cost.

java 
class Solution {
    public int calculateMaxWidth(int[][] coordinates) {
        Arrays.sort(coordinates, (first, second) -> Integer.compare(first[0], second[0]));
    
        int maxWidth = 0;
        for (int j = 1; j < coordinates.length; j++) {
            maxWidth = Math.max(maxWidth, coordinates[j][0] - coordinates[j - 1][0]);
        }
    
        return maxWidth;
    }
}

This solution in Java addresses the problem of finding the widest vertical area between two points that contains no other points. The approach taken involves sorting and iteration:

  1. Begin by sorting the array of coordinates based on their x-values using a lambda expression for easy comparison.

  2. Initialize a variable maxWidth to store the maximum width found and set it to zero initially.

  3. Loop through the sorted list of coordinates starting from the second element. During each iteration, calculate the distance (in x-direction) between the current point and the previous point.

  4. Update maxWidth if the current distance is greater than the previously recorded maximum width.

  5. After completing the loop, the function returns the maxWidth which is the widest vertical area with no points between two points.

This approach ensures the solution is efficient and straightforward, using sorting and a single scan through the coordinates. The final result obtained is the maximum width that satisfies the problem condition.

Comments

No comments yet.