# Widest Vertical Area Between Two Points Containing No Points
**Difficulty:** EASY
[External](https://leetcode.com/problems/widest-vertical-area-between-two-points-containing-no-points)
Canonical: https://scaleengineer.com/dsa/problems/widest-vertical-area-between-two-points-containing-no-points
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [General Motors](https://scaleengineer.com/companies/general-motors)
---
## Problem
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:**

![](https://assets.glich.co/dsa/widest-vertical-area-between-two-points-containing-no-points/image0.png)​ 

**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
## Brute Force by Checking All Pairs
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`.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Sorting the X-Coordinates
A more efficient approach recognizes that the y-coordinates are irrelevant to the problem. The problem can be reduced to finding the maximum gap between consecutive x-coordinates. By sorting all the x-coordinates, we can easily find this maximum gap by iterating through the sorted list once.
**Time:** O(n log n), dominated by the sorting step. Extracting the coordinates and finding the max difference both take O(n) time. · **Space:** O(n) to store the list of x-coordinates. If sorting is done in-place on the original array (by providing a custom comparator), the auxiliary space could be O(log n) to O(n) depending on the sort implementation.
**Pros:** Significantly faster than the brute-force approach.; Relatively simple to implement.; Guaranteed to find the correct answer.
**Cons:** Requires extra space to store the x-coordinates.; The time complexity is dominated by sorting, which is not linear time.
### Explanation
The core insight is that the y-coordinates of the points do not affect the width of a vertical area. Therefore, this problem can be simplified to a one-dimensional problem focusing only on the x-coordinates.
The widest vertical area must lie between two consecutive x-coordinates when all unique x-coordinates are sorted. If there were another x-coordinate `x_k` between `x_i` and `x_j`, the area between `x_i` and `x_j` would not be empty.
Thus, the algorithm is to extract all x-coordinates, sort them, and then find the maximum difference between any two adjacent x-coordinates in the sorted list.

```java
import java.util.Arrays;

class Solution {
    public int maxWidthOfVerticalArea(int[][] points) {
        int n = points.length;
        int[] xCoords = new int[n];
        for (int i = 0; i < n; i++) {
            xCoords[i] = points[i][0];
        }

        Arrays.sort(xCoords);

        int maxWidth = 0;
        for (int i = 1; i < n; i++) {
            int width = xCoords[i] - xCoords[i-1];
            if (width > maxWidth) {
                maxWidth = width;
            }
        }

        return maxWidth;
    }
}
```
### Algorithm
- Extract all x-coordinates from the `points` array into a new list or array, let's call it `xCoords`.
- Sort the `xCoords` array in non-decreasing order.
- Initialize a variable `maxWidth` to 0.
- Iterate through the sorted `xCoords` array from the second element (`i = 1` to `n-1`).
- For each element, calculate the difference with the previous element: `diff = xCoords[i] - xCoords[i-1]`.
- Update `maxWidth` with the maximum difference found so far: `maxWidth = max(maxWidth, diff)`.
- Return `maxWidth`.

## Linear Time Solution using Bucketing
This is the most optimal approach, achieving linear time complexity. It uses a bucketing strategy, which is an application of the Pigeonhole Principle. The core idea is that the maximum gap between sorted elements will not occur between elements that fall into the same 'bucket' if the bucket size is chosen correctly. Therefore, the maximum gap must exist between the maximum x-coordinate in one bucket and the minimum x-coordinate in a subsequent non-empty bucket.
**Time:** O(n). There are a few passes over the input data (to find min/max, to distribute into buckets) and a pass over the buckets. All these steps take linear time. · **Space:** O(n) to store the buckets. In the worst case, we might need a number of buckets proportional to n.
**Pros:** Achieves optimal O(n) time complexity.; Very efficient for large datasets.
**Cons:** More complex to implement correctly than the sorting approach.; Requires careful handling of floating-point arithmetic and integer division for bucket calculations.
### Explanation
The algorithm proceeds as follows:
1.  Find the minimum and maximum x-coordinates (`minX`, `maxX`).
2.  Calculate an appropriate `bucketSize`. A size of `ceil((maxX - minX) / (n - 1))` guarantees that the maximum gap will be at least `bucketSize`.
3.  Create buckets and distribute the x-coordinates into them. For each bucket, we only need to store the minimum and maximum x-coordinate it contains.
4.  Iterate through the buckets, keeping track of the maximum value of the previous non-empty bucket (`prevMax`). The gap is calculated as the current bucket's minimum minus `prevMax`. The largest such gap found is the answer.

```java
import java.util.Arrays;

class Solution {
    public int maxWidthOfVerticalArea(int[][] points) {
        int n = points.length;
        if (n < 2) {
            return 0;
        }

        int minX = Integer.MAX_VALUE;
        int maxX = Integer.MIN_VALUE;
        for (int[] point : points) {
            minX = Math.min(minX, point[0]);
            maxX = Math.max(maxX, point[0]);
        }

        if (minX == maxX) {
            return 0;
        }

        int bucketSize = (int) Math.ceil((double) (maxX - minX) / (n - 1));
        int numBuckets = (maxX - minX) / bucketSize + 1;

        int[] bucketMin = new int[numBuckets];
        int[] bucketMax = new int[numBuckets];
        Arrays.fill(bucketMin, Integer.MAX_VALUE);
        Arrays.fill(bucketMax, Integer.MIN_VALUE);

        for (int[] point : points) {
            int x = point[0];
            int bucketIdx = (x - minX) / bucketSize;
            bucketMin[bucketIdx] = Math.min(bucketMin[bucketIdx], x);
            bucketMax[bucketIdx] = Math.max(bucketMax[bucketIdx], x);
        }

        int maxWidth = 0;
        int prevMax = minX;

        for (int i = 0; i < numBuckets; i++) {
            if (bucketMin[i] == Integer.MAX_VALUE) {
                continue; // Skip empty bucket
            }
            
            maxWidth = Math.max(maxWidth, bucketMin[i] - prevMax);
            prevMax = bucketMax[i];
        }

        return maxWidth;
    }
}
```
### Algorithm
- Find the minimum (`minX`) and maximum (`maxX`) x-coordinates from all points.
- If `minX == maxX`, return 0.
- Calculate the `bucketSize` based on the range and number of points: `bucketSize = ceil((double)(maxX - minX) / (n - 1))`.
- Determine the number of buckets needed: `numBuckets = (maxX - minX) / bucketSize + 1`.
- Create two arrays, `bucketMin` and `bucketMax`, to store the minimum and maximum x-value for each bucket.
- Iterate through the points and place each x-coordinate into its corresponding bucket, updating the bucket's min and max values.
- Iterate through the buckets, keeping track of the maximum value from the previously seen non-empty bucket (`prevMax`).
- The widest area is the maximum difference between the current bucket's minimum and `prevMax`.
- Return the overall maximum difference found.

# Solutions
### Java

```java
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 ; } }
```

### JavaScript

```javascript
/** * @param {number[][]} points * @return {number} */ var maxWidthOfVerticalArea =
  function (points) {
    points.sort((a, b) => a[0] - b[0]);
    let ans = 0;
    let px = points[0][0];
    for (const [x, _] of points) {
      ans = Math.max(ans, x - px);
      px = x;
    }
    return ans;
  };

```

### CPP

```cpp
class Solution { public: int maxWidthOfVerticalArea ( vector < vector < int >>& points ) { sort ( points . begin (), points . end ()); int ans = 0 ; for ( int i = 0 ; i < points . size () - 1 ; ++ i ) { ans = max ( ans , points [ i + 1 ][ 0 ] - points [ i ][ 0 ]); } return ans ; } };
```

### Python

```python
class Solution : def maxWidthOfVerticalArea ( self , points : List [ List [ int ]]) -> int : points . sort () return max ( b [ 0 ] - a [ 0 ] for a , b in pairwise ( points ))
```