Scale Engineer

Widest Vertical Area Between Two Points Containing No Points

Easy
#1503Time: O(n^3), where n is the number of points. There are two nested loops to select a pair of points (O(n^2)), and for each pair, another loop to check all other points (O(n)).Space: O(1), as no additional data structures are used that scale with the input size.1 company
Algorithms
Sorting
Data structures
Array
Companies
General Motors

Prompt

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.

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

Approaches

3 approaches with complexity analysis and trade-offs.

This is a straightforward but highly inefficient approach. The idea is to consider every possible pair of points (p_i, p_j) from the input. These two points can define the boundaries of a vertical area with width |x_j - x_i|. For each such potential area, we must verify that it contains no other points. This is done by iterating through all other points p_k and checking if their x-coordinate x_k lies strictly between x_i and x_j.

Algorithm

  • Initialize maxWidth to 0.
  • Iterate through every point points[i].
  • For each points[i], iterate through every other point points[j].
  • Let the x-coordinates be x1 = points[i][0] and x2 = points[j][0]. To avoid duplicates and simplify, assume x1 < x2.
  • Check if the vertical area between x1 and x2 is empty. To do this, iterate through all points points[k].
  • If any point points[k] has an x-coordinate x_k such that x1 < x_k < x2, the area is not empty.
  • If the area is found to be empty, update maxWidth = max(maxWidth, x2 - x1).
  • After checking all pairs, return maxWidth.

Walkthrough

If an area is found to be empty, its width is compared with the maximum width found so far, and the maximum is updated if necessary. This process is repeated for all pairs of points, making it very computationally expensive.

class Solution {    public int maxWidthOfVerticalArea(int[][] points) {        int n = points.length;        int maxWidth = 0;         // Sort points by x-coordinate to slightly optimize by only checking adjacent candidates        // But a true brute force would not sort.        // Let's stick to the O(N^3) version for a clear worst-case approach.        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                if (i == j) continue;                 int x1 = points[i][0];                int x2 = points[j][0];                 // We only care about the gap where x2 > x1                if (x1 >= x2) continue;                 boolean hasPointsBetween = false;                for (int k = 0; k < n; k++) {                    int xk = points[k][0];                    if (xk > x1 && xk < x2) {                        hasPointsBetween = true;                        break;                    }                }                 if (!hasPointsBetween) {                    maxWidth = Math.max(maxWidth, x2 - x1);                }            }        }        return maxWidth;    }}

Complexity

Time

O(n^3), where n is the number of points. There are two nested loops to select a pair of points (O(n^2)), and for each pair, another loop to check all other points (O(n)).

Space

O(1), as no additional data structures are used that scale with the input size.

Trade-offs

Pros

  • Simple to conceptualize.

  • Uses constant extra space.

Cons

  • Extremely slow due to its cubic time complexity.

  • Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.

Solutions

class Solution { public int maxWidthOfVerticalArea ( int [][] points ) { Arrays . sort ( points , ( a , b ) -> a [ 0 ] - b [ 0 ]); int ans = 0 ; for ( int i = 0 ; i < points . length - 1 ; ++ i ) { ans = Math . max ( ans , points [ i + 1 ][ 0 ] - points [ i ][ 0 ]); } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem