💬 Discord
Sign In
NeetCode #929LC-1637EasyMath & Geometry
← Back to All Problems

#929 · #1637 · Widest Vertical Area Between Two Points Containing No Points(两点之间不包含任何点的最宽垂直区域)

📌 Problem Statement & Constraints

Given n points points[i] = [xi, yi], a vertical area is the region between two vertical lines containing no points. Return the widest such area, i.e. the maximum gap between consecutive x-coordinates. Constraints: 2 <= n <= 10^5, 0 <= xi, yi <= 10^9.

💡 Core Algorithmic Approaches

  1. The width depends only on the x-coordinates; the y-values are irrelevant.
  2. Sort the x-coordinates; the widest empty vertical strip is bounded by two adjacent values in that order.
  3. The answer is max(xs[i + 1] - xs[i]) over consecutive pairs.
  4. Duplicate x-values produce a zero gap and are harmless.

💻 Benchmark Python3 Implementation

class Solution:
    def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
        xs = sorted(p[0] for p in points)
        return max(xs[i + 1] - xs[i] for i in range(len(xs) - 1))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the sort dominates.
💾 Space Complexity
O(n): the array of x-coordinates.

⚠️ Interview Pitfalls & Follow-ups

  • Including the y-coordinate: the vertical area width is purely horizontal.
  • Searching for points inside the strip: after sorting by x, two adjacent x-values cannot have any point strictly between them.
  • Using the full range xs[-1] - xs[0]: that region contains all the other points, so it is not empty.