Minimum Rectangles to Cover Points
MedPrompt
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:
- A rectangle with a lower end at
(1, 0)and its upper end at(2, 8) - A rectangle with a lower end at
(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:
- A rectangle with a lower end at
(0, 0)and its upper end at(2, 2) - A rectangle with a lower end at
(3, 0)and its upper end at(5, 5) - A rectangle with a lower end at
(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:
- A rectangle with a lower end at
(1, 0)and its upper end at(1, 2) - A rectangle with a lower end at
(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- All pairs
(xi, yi)are distinct.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses dynamic programming to find the minimum number of rectangles. After sorting the points by their x-coordinate, it builds a solution for the first i points by leveraging the solutions for smaller subproblems. It systematically checks all possible groupings for the last rectangle.
Algorithm
-
- Sort the
pointsarray by x-coordinate. - 2. Create adparray of sizen, wheredp[i]is the minimum rectangles to cover points0toi. - 3. Iterateifrom0ton-1. - 4. For eachi, iteratejfromidown to0. - 5. Ifpoints[i][0] - points[j][0] <= w, updatedp[i]withmin(dp[i], (j > 0 ? dp[j-1] : 0) + 1). - 6. If the condition fails, break the inner loop as further points won't satisfy it. - 7. The final answer isdp[n-1].
- Sort the
Walkthrough
The problem can be solved using dynamic programming after an initial sorting step. The key observation is that the y-coordinates of the points are irrelevant for determining the minimum number of rectangles; only the x-coordinates matter. The width constraint w is the deciding factor for grouping points. The algorithm proceeds as follows:
- Sort: First, we sort the
pointsarray based on the x-coordinates in non-decreasing order. This allows us to process points from left to right. - DP State: We define a DP array,
dp, wheredp[i]stores the minimum number of rectangles required to cover the firsti+1points (i.e.,points[0]topoints[i]). - DP Transition: To calculate
dp[i], we consider thei-th point. We must place it in a rectangle. This rectangle can potentially cover previous points as well. We iterate backwards from pointiwith an indexj. As long aspoints[i][0] - points[j][0] <= w, all points fromjtoican be covered by a single new rectangle. The total cost would be1(for this new rectangle) plus the cost to cover points up toj-1, which isdp[j-1]. We take the minimum over all validj. The recurrence relation is:dp[i] = min(dp[j-1] + 1)for alljfrom0toisuch thatpoints[i][0] - points[j][0] <= w(withdp[-1]being0). The final answer isdp[n-1]. Here is the Java implementation:
import java.util.Arrays;import java.util.Comparator; class Solution { public int minRectanglesToCoverPoints(int[][] points, int w) { int n = points.length; if (n == 0) { return 0; } Arrays.sort(points, Comparator.comparingInt(p -> p[0])); int[] dp = new int[n]; // dp[i] = min rectangles to cover points 0...i for (int i = 0; i < n; i++) { // Initialize with the case where point i starts a new rectangle // covering only itself, adding to the solution for points 0...i-1. dp[i] = (i > 0 ? dp[i-1] : 0) + 1; // Try to group with previous points for (int j = i; j >= 0; j--) { if (points[i][0] - points[j][0] <= w) { // Points from j to i can be in one rectangle. // The cost is 1 (for this rectangle) + cost to cover points up to j-1. int prevCost = (j > 0) ? dp[j-1] : 0; dp[i] = Math.min(dp[i], prevCost + 1); } else { // Since sorted, no point before j will satisfy the condition break; } } } return dp[n-1]; }}Complexity
Time
O(N^2). The initial sort takes O(N log N). The nested loops for the DP calculation result in a quadratic time complexity, which is the dominant factor.
Space
O(N), where N is the number of points. This is for storing the DP array. Additional space might be required for sorting, typically O(log N) or O(N).
Trade-offs
Pros
Provides a structured way to arrive at the correct solution.
Guaranteed to be correct if implemented properly.
Cons
Inefficient for large inputs due to its O(N^2) time complexity, which will likely time out on larger constraints.
Requires O(N) extra space for the DP table.
Solutions
Solution
public class Solution { public int MinRectanglesToCoverPoints(int[][] points, int w) { Array.Sort(points, (a, b) => a[0] - b[0]); int ans = 0, x1 = -1; foreach(int[] p in points) { int x = p[0]; if (x > x1) { ans++; x1 = x + w; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.