EasyNo. 1637
Widest Vertical Area Between Two Points Containing No Points — LeetCode 1637 Python Solution
- Pattern
- Sorting
- Topics
- Array, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
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
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
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
| No. | Problem | Difficulty |
|---|---|---|
| 0056 | Merge Intervals | Medium |
| 0164 | Maximum Gap | Medium |
| 0274 | H-Index | Medium |
| 0406 | Queue Reconstruction by Height | Medium |
| 0414 | Third Maximum Number | Easy |
| 0462 | Minimum Moves to Equal Array Elements II | Medium |
Frequently asked questions
- How hard is LeetCode 1637. Widest Vertical Area Between Two Points Containing No Points?
LeetCode 1637. Widest Vertical Area Between Two Points Containing No Points is rated Easy on LeetCode.
- What topics does LeetCode 1637. Widest Vertical Area Between Two Points Containing No Points cover?
LeetCode 1637. Widest Vertical Area Between Two Points Containing No Points is tagged Array and Sorting on LeetCode.