Widest Vertical Area Between Two Points Containing No Points

Widest Vertical Area Between Two Points Containing No Points

What is this problem about?

This problem gives you a set of points on a 2D plane. You need to find the maximum width of a vertical area between two points such that no other points are inside that area. A vertical area is an area of infinite height extending along the y-axis. Effectively, you only care about the x-coordinates of the points and the largest gap between any two adjacent x-coordinates.

Why is this asked in interviews?

This is a popular "Easy" level question at companies like Amazon and Bloomberg because it tests whether a candidate can filter out irrelevant information. In a 2D plane problem, many beginners get distracted by the y-coordinates. Realizing that the y-coordinates are completely irrelevant to the "vertical width" is the first step toward the correct solution.

Algorithmic pattern used

The pattern used is Sorting. Since we only care about the vertical width, we extract all x-coordinates, sort them in ascending order, and then find the maximum difference between any two consecutive x-coordinates. The time complexity is dominated by sorting, which is O(N log N).

Example explanation

Points: [[5, 10], [1, 5], [9, 2], [3, 8]].

1. Extract x-coordinates: [5, 1, 9, 3].
2. Sort them: [1, 3, 5, 9].
3. Find gaps:
   • 3 - 1 = 2
   • 5 - 3 = 2
   • 9 - 5 = 4 The widest vertical area has a width of 4.

Common mistakes candidates make

• Processing Y-coordinates: Wasting time sorting or comparing y-values when they don't affect the vertical width.
• Not sorting: Trying to find the largest gap without sorting the points first.
• Off-by-one: Not checking all adjacent pairs in the sorted list.

Interview preparation tip

Always identify which dimensions are relevant to the goal. In geometry problems, "vertical" usually implies a dependence on X, and "horizontal" implies a dependence on Y. Simplify your data as early as possible.