Skip to main content
Talentd

Widest Vertical Area Between Two Points Containing No Points - Solution & Explanation

EasyArraySorting11 min readAsked at: Amazon, Microsoft, General Motors +1
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You receive a list of 2D points. A vertical area is the space between two vertical lines (x = a and x = b) that contains no points between them. The task is to return the maximum width of such an area. Only the x-coordinates matter because vertical gaps depend purely on horizontal distance.

Approach 1: Sort and Compare Consecutive Differences (O(n log n) time, O(1) extra space or O(n) depending on sorting)

The key observation: the widest empty vertical region must lie between two neighboring x-coordinates after sorting. Extract all x values from the points and sort them. Then iterate through the sorted list and compute the difference between each consecutive pair. Track the maximum difference seen. Sorting ensures that any larger gap would appear between adjacent elements in the ordered sequence. This approach is simple, reliable, and commonly expected in interviews. It relies on concepts from Array traversal and Sorting.

Approach 2: Bucket Sort for Near-Constant Time Gap Calculation (O(n) time, O(n) space)

Sorting works well, but the problem can be solved in linear time using a bucket-based gap strategy similar to the maximum gap problem. First determine the global minimum and maximum x-values. Divide the range into buckets sized so that the expected gap between buckets is roughly (maxX - minX) / (n - 1). Each bucket stores only the minimum and maximum x-values that fall inside it. After distributing points into buckets, iterate through them and compute the gap between the maximum of the previous non-empty bucket and the minimum of the current one. The largest such gap is the answer. Because points inside the same bucket cannot produce the maximum gap, comparisons only occur between buckets. This method avoids full sorting while still using ideas from Array processing and distribution-based Sorting techniques.

Recommended for interviews: The sorting approach is what most interviewers expect. It is easy to implement, easy to reason about, and runs in O(n log n), which is more than sufficient for typical constraints. The bucket-based solution demonstrates deeper algorithmic knowledge and achieves O(n) time, but it is usually presented as an optimization rather than the first solution. Showing the sorting solution first proves you understand the core observation that the widest vertical area must exist between consecutive sorted x-values.

Approach 1: Approach 1: Sort and Compare Consecutive Differences

This approach involves sorting the x-coordinates of the points and then finding the maximum difference between consecutive sorted x-coordinates. This difference gives the widest vertical area between any two points.

This solution uses a simple array to extract x-coordinates, sorts it, and finds the maximum gap between consecutive sorted x-coordinates. The function qsort() is used for sorting, and a loop is used after sorting to determine the maximum width.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), due to the sorting step.
Space Complexity: O(n), due to the additional array holding the sorted x-coordinates.

Try this approach in the editor ā†’

Approach 2: Approach 2: Bucket Sort for Near-Constant Time Gap Calculation

Although not commonly necessary due to the constraints provided, if x-coordinates were to be over a smaller range, a variant of bucket sort could be used to place x-coordinates in a collection of buckets. This helps find consecutive x-coordinate gaps in nearly constant time, potentially improving performance by eliminating the general-purpose sort with more specialized data placement.

With constraints as large as those given, using a fine-grained approach like bucket sort isn't practical here; however, this explanation serves educational purposes.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) expected when bucket conditions are met.
Space Complexity: O(m) where m is the bucket range size.

Try this approach in the editor ā†’

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Approach 1: Sort and Compare Consecutive Differences

Time Complexity: O(n log n), due to the sorting step.
Space Complexity: O(n), due to the additional array holding the sorted x-coordinates.

Approach 2: Bucket Sort for Near-Constant Time Gap Calculation

Time Complexity: O(n) expected when bucket conditions are met.
Space Complexity: O(m) where m is the bucket range size.

Default Approachā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sort and Compare Consecutive DifferencesO(n log n)O(1)ā€“O(n)General case. Simplest implementation and commonly expected in coding interviews.
Bucket Sort Gap CalculationO(n)O(n)When linear time is required or when demonstrating advanced understanding of gap-based bucket strategies.

Video Solution

Wildest Vertical Area Between Two Points Containing No Points - Leetcode 1637 - Python ā€¢ NeetCodeIO ā€¢ 6,929 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Widest Vertical Area Between Two Points Containing No Points easy or hard?
The problem is classified as Easy on LeetCode with a high acceptance rate above 80%. The main insight is realizing that only x-coordinates matter and the answer is the maximum gap between consecutive sorted values. Once that observation is made, the implementation becomes straightforward.
Widest Vertical Area Between Two Points Containing No Points Python/Java solution
The typical Python or Java implementation extracts all x-coordinates, sorts them, and scans for the largest difference between adjacent values. The algorithm runs in O(n log n) time and uses a simple loop after sorting. FleetCode provides implementations in Python, Java, C++, JavaScript, C, and C#.
How to solve Widest Vertical Area Between Two Points Containing No Points in O(n)?
Use a bucket-based strategy similar to the maximum gap algorithm. Compute the minimum and maximum x-values, divide the range into buckets, and store only the min and max x within each bucket. The largest gap will occur between the maximum value of one non-empty bucket and the minimum value of the next non-empty bucket. This avoids full sorting and runs in O(n) time.
What is the best approach for Widest Vertical Area Between Two Points Containing No Points?
The most practical approach sorts all x-coordinates and checks the difference between consecutive values. After sorting, the widest empty vertical region must appear between two adjacent x-values. This solution runs in O(n log n) time and requires minimal additional space, making it the most common interview answer.
Is Widest Vertical Area Between Two Points Containing No Points asked at Google/Amazon/Meta?
This problem follows a classic gap-detection pattern and appears in coding interview practice sets used by companies like Amazon and Google. While the exact question may vary, the underlying idea of sorting coordinates and finding maximum gaps is a common interview concept.
What data structure is used in Widest Vertical Area Between Two Points Containing No Points?
The problem primarily uses arrays to store and process x-coordinates. The typical solution applies sorting to the array of x-values. The linear-time optimization uses buckets (arrays storing min and max values) to compute gaps without sorting the entire dataset.
What is the time complexity of Widest Vertical Area Between Two Points Containing No Points?
The standard solution runs in O(n log n) time because it sorts the x-coordinates of the points. After sorting, a single linear scan computes the maximum gap in O(n). A bucket-based optimization can reduce the overall complexity to O(n) with O(n) extra space.

Ready to solve this problem?

Practice Widest Vertical Area Between Two Points Containing No Points with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Consecutive Floors Without Special Floors

Next

Maximum Gap