Watch 7 video solutions for Minimum Rectangles to Cover Points, a medium level problem involving Array, Greedy, Sorting. This walkthrough by Aryan Mittal has 1,714 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 2D integer array points, where points[i] = [xi, yi]. You are also given an integer w. Your task is to cover all the given points with rectangles.
Each rectangle has its lower end at some point (x1, 0) and its upper end at some point (x2, y2), where x1 <= x2, y2 >= 0, and the condition x2 - x1 <= w must be satisfied for each rectangle.
A point is considered covered by a rectangle if it lies within or on the boundary of the rectangle.
Return an integer denoting the minimum number of rectangles needed so that each point is covered by at least one rectangle.
Note: A point may be covered by more than one rectangle.
Example 1:
Input: points = [[2,1],[1,0],[1,4],[1,8],[3,5],[4,6]], w = 1
Output: 2
Explanation:
The image above shows one possible placement of rectangles to cover the points:
(1, 0) and its upper end at (2, 8)(3, 0) and its upper end at (4, 8)Example 2:
Input: points = [[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6]], w = 2
Output: 3
Explanation:
The image above shows one possible placement of rectangles to cover the points:
(0, 0) and its upper end at (2, 2)(3, 0) and its upper end at (5, 5)(6, 0) and its upper end at (6, 6)Example 3:
Input: points = [[2,3],[1,2]], w = 0
Output: 2
Explanation:
The image above shows one possible placement of rectangles to cover the points:
(1, 0) and its upper end at (1, 2)(2, 0) and its upper end at (2, 3)
Constraints:
1 <= points.length <= 105points[i].length == 20 <= xi == points[i][0] <= 1090 <= yi == points[i][1] <= 1090 <= w <= 109(xi, yi) are distinct.Problem Overview: You are given coordinates of points on a 2D plane and a rectangle width w. Each rectangle spans vertically but only covers an x-range of length w. The goal is to place the minimum number of rectangles so every point falls within at least one rectangle.
The key observation: the y-coordinate does not affect coverage. A rectangle extends vertically, so only the x-coordinate determines whether a point is covered. The problem reduces to covering x-values with the minimum number of intervals of length w.
Approach 1: Greedy with Sorting (O(n log n) time, O(1) extra space)
Sort the points by their x-coordinate using a standard sorting step. Start with the leftmost point and place a rectangle whose left boundary begins at that point's x-coordinate. This rectangle covers the interval [x, x + w]. Iterate through the sorted list and skip every point whose x-value lies within that range. When a point falls outside the current rectangle, start a new rectangle from that point and repeat the process. This greedy strategy works because placing the rectangle as far left as possible maximizes the number of points covered by each placement.
This solution relies on a classic greedy decision: always cover the earliest uncovered point with the widest possible valid interval. Each point is processed once after sorting, so the dominant cost is the sort operation.
Approach 2: Sliding Window over Sorted Points (O(n log n) time, O(1) space)
Another way to frame the same idea is with a array traversal using a sliding window. After sorting points by x-coordinate, maintain a window that represents the current rectangle's coverage. The left pointer marks the first uncovered point. Extend the right pointer while points remain within x[left] + w. Once the window exceeds that boundary, you finalize the rectangle count and move the left pointer to the first uncovered point.
The sliding window interpretation helps visualize the coverage range and is often easier to reason about during interviews. Both pointers move monotonically across the sorted array, so the scan itself is linear after sorting.
Recommended for interviews: The greedy sorting approach is what interviewers typically expect. It demonstrates recognition that the problem reduces to interval coverage on the x-axis. A quick brute-force attempt might show initial reasoning, but identifying the greedy invariant and sorting the points signals strong algorithmic intuition. The optimal complexity is O(n log n) due to sorting, with O(1) extra space if sorting in place.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(n log n) | O(1) | General case when points are unsorted. Standard interview solution. |
| Sliding Window on Sorted Points | O(n log n) | O(1) | When reasoning about coverage ranges or two-pointer traversal. |