Widest Vertical Area Between Two Points Containing No Points — LeetCode 1637 Python Solution

The 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).

Example

Input

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

Output

1

Explanation

Both the red and the blue area are optimal.

Python solution

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

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1637. Widest Vertical Area Between Two Points Containing No Points is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems