LeetCode 1637 - Widest Vertical Area Between Two Points Containing No Points

LeetCode Problem 1637

Difficulty: 🟢 Easy
Topics: Array, Sorting

Solution

Problem Understanding

This problem gives us a list of points on a 2D plane, where each point is represented as [x, y]. We need to find the widest vertical area that contains no points strictly inside it.

A vertical area is defined by two vertical lines. Since the area extends infinitely along the y-axis, only the x-coordinates matter. The y-values are completely irrelevant for determining the width of a vertical gap.

The width of a vertical area is simply the horizontal distance between two x-coordinates. We want the maximum possible width such that no points exist strictly between those two x-values.

An important detail is that points lying exactly on the boundary are allowed. This means if two points have x-coordinates x1 and x2, then the vertical area between them is valid as long as there are no other points with x-values strictly between x1 and x2.

For example, consider these x-values:

1, 3, 5, 9

The gaps are:

• Between 1 and 3 → width 2
• Between 3 and 5 → width 2
• Between 5 and 9 → width 4

The answer is 4.

The constraints are important:

• 2 <= n <= 10^5
• 0 <= xi, yi <= 10^9

Since there can be up to 100,000 points, an inefficient quadratic solution will be too slow. We need an algorithm close to O(n log n) or better.

There are several important edge cases:

• Multiple points may share the same x-coordinate.
• The widest gap may appear at the beginning or end after sorting.
• Large coordinate values require careful handling, but standard integer types are sufficient.
• The y-coordinates do not affect the answer at all.

The problem guarantees at least two points, so there will always be at least one vertical gap to evaluate.

Approaches

Brute Force Approach

A naive approach would compare every pair of points and check whether there exists another point whose x-coordinate lies strictly between them.

For every pair (xi, xj):

1. Compute the width abs(xi - xj).
2. Scan all other points.
3. Verify whether any point lies strictly inside the interval.

If no point exists inside the interval, then the width is a candidate answer.

This approach is correct because it explicitly checks every possible vertical area. However, it is far too slow.

There are O(n^2) pairs, and for each pair we may scan all n points, leading to O(n^3) time complexity.

Even a slightly optimized version that checks all pairs without the inner validation would still be too expensive for n = 10^5.

Key Insight

The key observation is that only the sorted x-coordinates matter.

Suppose we sort all x-values:

x1 <= x2 <= x3 <= ... <= xn

The widest valid vertical area must lie between two consecutive x-values in sorted order.

Why?

Because if there were another x-coordinate between them, then the area would contain a point and would not be empty.

Therefore, after sorting, we only need to compute:

x[i] - x[i - 1]

for every adjacent pair.

The maximum adjacent difference is the answer.

Sorting transforms the problem from a geometric problem into a simple array gap problem.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every pair and validates emptiness
Optimal	O(n log n)	O(n)	Sort x-coordinates and find largest adjacent gap

Algorithm Walkthrough

1. Extract all x-coordinates from the input points.

The y-coordinates are irrelevant because the vertical area extends infinitely upward and downward. Only horizontal distances matter. 2. Sort the x-coordinates in ascending order.

Sorting places all points along the x-axis in order, making it easy to identify consecutive gaps. 3. Initialize a variable to store the maximum width found so far.

Start with 0 because widths are non-negative. 4. Iterate through the sorted x-values starting from index 1.

For each position:

• Compute the gap:

current_gap = x[i] - x[i - 1]

• Update the maximum width if this gap is larger.

5. Return the maximum width after processing all adjacent pairs.

Why it works

After sorting, any valid empty vertical area must lie between two consecutive x-coordinates. If two x-values are not consecutive, then at least one other point exists between them, meaning the area is not empty.

Therefore, the largest adjacent difference in the sorted array exactly represents the widest vertical area containing no points.

Python Solution

from typing import List

class Solution:
    def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
        x_coordinates = sorted(point[0] for point in points)

        max_width = 0

        for i in range(1, len(x_coordinates)):
            current_width = x_coordinates[i] - x_coordinates[i - 1]
            max_width = max(max_width, current_width)

        return max_width

The implementation begins by extracting all x-coordinates using a generator expression. Since only x-values matter, we ignore the y-values completely.

The x-coordinates are then sorted in ascending order. Once sorted, every adjacent pair represents the smallest possible interval between those positions.

The loop starts at index 1 because each gap is computed against the previous element.

For every adjacent pair, the algorithm calculates the width and updates the maximum value found so far.

Finally, the maximum width is returned.

The implementation is concise because the key insight greatly simplifies the problem.

Go Solution

package main

import "sort"

func maxWidthOfVerticalArea(points [][]int) int {
	xCoordinates := make([]int, len(points))

	for i, point := range points {
		xCoordinates[i] = point[0]
	}

	sort.Ints(xCoordinates)

	maxWidth := 0

	for i := 1; i < len(xCoordinates); i++ {
		currentWidth := xCoordinates[i] - xCoordinates[i-1]

		if currentWidth > maxWidth {
			maxWidth = currentWidth
		}
	}

	return maxWidth
}

The Go solution follows the same logic as the Python implementation.

A slice is allocated to store all x-coordinates. The built-in sort.Ints() function sorts the slice in ascending order.

The algorithm then scans adjacent elements and tracks the largest difference.

Go's int type safely handles the coordinate range in this problem because the maximum difference is at most 10^9.

Worked Examples

Example 1

Input:

points = [[8,7],[9,9],[7,4],[9,7]]

Step 1: Extract x-coordinates

Point	x-coordinate
[8,7]	8
[9,9]	9
[7,4]	7
[9,7]	9

Result:

[8, 9, 7, 9]

Step 2: Sort x-coordinates

[7, 8, 9, 9]

Step 3: Compute adjacent gaps

Index	Current x	Previous x	Gap
1	8	7	1
2	9	8	1
3	9	9	0

Maximum gap:

1

Final answer:

1

Example 2

Input:

points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]

Step 1: Extract x-coordinates

[3, 9, 1, 1, 5, 8]

Step 2: Sort x-coordinates

[1, 1, 3, 5, 8, 9]

Step 3: Compute adjacent gaps

Index	Current x	Previous x	Gap
1	1	1	0
2	3	1	2
3	5	3	2
4	8	5	3
5	9	8	1

Maximum gap:

3

Final answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(n)	Stores extracted x-coordinates

The sorting step is the most expensive operation. Extracting coordinates and scanning adjacent gaps both require linear time.

The extra space comes from storing the list or slice of x-coordinates separately from the input.

Test Cases

from typing import List

class Solution:
    def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
        x_coordinates = sorted(point[0] for point in points)

        max_width = 0

        for i in range(1, len(x_coordinates)):
            current_width = x_coordinates[i] - x_coordinates[i - 1]
            max_width = max(max_width, current_width)

        return max_width

solution = Solution()

assert solution.maxWidthOfVerticalArea(
    [[8,7],[9,9],[7,4],[9,7]]
) == 1  # Basic example with duplicate x-values

assert solution.maxWidthOfVerticalArea(
    [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]
) == 3  # Largest gap appears in the middle

assert solution.maxWidthOfVerticalArea(
    [[1,1],[2,2]]
) == 1  # Minimum number of points

assert solution.maxWidthOfVerticalArea(
    [[1,1],[1,5],[1,10]]
) == 0  # All points share same x-coordinate

assert solution.maxWidthOfVerticalArea(
    [[0,0],[1000000000,1]]
) == 1000000000  # Maximum coordinate range

assert solution.maxWidthOfVerticalArea(
    [[5,2],[2,1],[10,3],[20,4]]
) == 10  # Largest gap near the end

assert solution.maxWidthOfVerticalArea(
    [[20,1],[10,2],[5,3],[1,4]]
) == 10  # Unsorted descending input

assert solution.maxWidthOfVerticalArea(
    [[1,1],[3,2],[6,3],[10,4]]
) == 4  # Increasing gaps

assert solution.maxWidthOfVerticalArea(
    [[1,1],[2,2],[3,3],[4,4]]
) == 1  # Uniform gaps

print("All test cases passed!")

Test Summary

Test	Why
Example 1	Validates duplicate x-values
Example 2	Validates typical unsorted input
Two points only	Smallest valid input size
All same x-coordinate	Ensures zero-width handling
Maximum coordinate range	Verifies large integer handling
Largest gap at end	Checks boundary positioning
Reverse sorted input	Confirms sorting works correctly
Increasing gaps	Validates maximum gap selection
Uniform gaps	Ensures consistent processing

Edge Cases

Multiple Points With the Same x-coordinate

A common source of bugs is assuming all x-values are unique. If multiple points share the same x-coordinate, the gap between them is zero.

For example:

[[1,1], [1,5], [1,10]]

After sorting, all adjacent differences are 0, so the answer is 0.

The implementation handles this naturally because adjacent subtraction correctly produces zero.

Only Two Points

The smallest possible input contains exactly two points.

For example:

[[1,1], [10,10]]

There is only one possible vertical gap, which has width 9.

The implementation correctly processes this because the loop runs exactly once.

Very Large Coordinate Values

Coordinates can be as large as 10^9.

For example:

[[0,0], [1000000000,1]]

The answer is 1000000000.

The algorithm only performs subtraction and sorting, both of which are safe within standard integer limits in Python and Go.