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.
This approach involves sorting the points by their x-coordinates and then using a greedy method to cover as many points as possible with each rectangle. Once the points are sorted, iterate through them and keep a running count of rectangles by checking if a new rectangle is needed to cover uncovered points.
The function minRectangles starts by sorting the points based on their x-coordinates using qsort and a comparison function. Then, it iterates through the sorted list of points, using a greedy approach to determine the minimum number of rectangles required. Each rectangle begins at a position x_start and attempts to cover as many points as possible within the width w. The process is repeated until all points are covered.
Time Complexity: O(n log n) due to the sorting step, where n is the number of points. Space Complexity: O(1) since no additional data structures are used outside the input sorting.
Another efficient way to solve the problem is using a sliding window. By maintaining a window of x-coordinates, stretch it to cover maximum points within the constraint and move it optimally as points are covered. This is particularly beneficial when handling constraints efficiently.
In this sliding window technique for C, after sorting, we use two pointers: i iterates through each point, and start tracks the point where the current rectangle started. If the x-coordinate for i surpasses start + w, a new rectangle is counted, and start is updated.
Time Complexity: O(n log n) due to sorting operation. Space Complexity: O(1) for the pointers, requiring constant space.
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n) due to the sorting step, where n is the number of points. Space Complexity: O(1) since no additional data structures are used outside the input sorting. |
| Sliding Window Approach | Time Complexity: O(n log n) due to sorting operation. Space Complexity: O(1) for the pointers, requiring constant space. |
| 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. |
3111. Minimum Rectangles to Cover Points | Sorting & Greedy • Aryan Mittal • 1,714 views views
Watch 6 more video solutions →Practice Minimum Rectangles to Cover Points with our built-in code editor and test cases.
Practice on FleetCode