# Minimum Rectangles to Cover Points
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-rectangles-to-cover-points)
Canonical: https://scaleengineer.com/dsa/problems/minimum-rectangles-to-cover-points
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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:**

![](https://assets.glich.co/dsa/minimum-rectangles-to-cover-points/image0.png)

**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:**

![](https://assets.glich.co/dsa/minimum-rectangles-to-cover-points/image1.png)

**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:**

![](https://assets.glich.co/dsa/minimum-rectangles-to-cover-points/image2.png)

**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 <= 105`
* `points[i].length == 2`
* `0 <= xi == points[i][0] <= 109`
* `0 <= yi == points[i][1] <= 109`
* `0 <= w <= 109`
* All pairs `(xi, yi)` are distinct.

# Approaches
## Dynamic Programming Approach
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.
**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).
**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.
### Explanation
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: 
1. **Sort**: First, we sort the `points` array based on the x-coordinates in non-decreasing order. This allows us to process points from left to right. 
2. **DP State**: We define a DP array, `dp`, where `dp[i]` stores the minimum number of rectangles required to cover the first `i+1` points (i.e., `points[0]` to `points[i]`). 
3. **DP Transition**: To calculate `dp[i]`, we consider the `i`-th point. We must place it in a rectangle. This rectangle can potentially cover previous points as well. We iterate backwards from point `i` with an index `j`. As long as `points[i][0] - points[j][0] <= w`, all points from `j` to `i` can be covered by a single new rectangle. The total cost would be `1` (for this new rectangle) plus the cost to cover points up to `j-1`, which is `dp[j-1]`. We take the minimum over all valid `j`. The recurrence relation is: `dp[i] = min(dp[j-1] + 1)` for all `j` from `0` to `i` such that `points[i][0] - points[j][0] <= w` (with `dp[-1]` being `0`). The final answer is `dp[n-1]`. 
Here is the Java implementation: 
```java
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];
    }
}
```
### Algorithm
- 1. Sort the `points` array by x-coordinate. - 2. Create a `dp` array of size `n`, where `dp[i]` is the minimum rectangles to cover points `0` to `i`. - 3. Iterate `i` from `0` to `n-1`. - 4. For each `i`, iterate `j` from `i` down to `0`. - 5. If `points[i][0] - points[j][0] <= w`, update `dp[i]` with `min(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 is `dp[n-1]`.

## Greedy Approach with Sorting
A highly efficient greedy approach is optimal for this problem. By sorting the points by their x-coordinate, we can iterate through them once. We greedily form rectangles that are as wide as possible to cover the maximum number of points at each step, which leads to the minimum total number of rectangles.
**Time:** O(N log N), where N is the number of points. This is dominated by the initial sorting step. The subsequent greedy scan of the array is a single pass, taking O(N) time. · **Space:** O(log N) or O(N), depending on the sorting algorithm's implementation. An in-place sort like quicksort uses O(log N) stack space, while a stable sort like Timsort might use O(N) space in the worst case.
**Pros:** Very efficient, with a time complexity dominated by the sorting step.; Simple and intuitive to implement.; Space-efficient, requiring minimal extra memory.
**Cons:** The main dependency is on sorting, which might be a drawback if the input must remain unchanged, thus requiring a copy.
### Explanation
This problem has an optimal greedy substructure, which allows for a much more efficient solution than dynamic programming. The core idea remains the same: the problem is one-dimensional, concerning only the x-coordinates of the points. The greedy strategy is as follows: 
1. **Sort**: Sort the points based on their x-coordinates. This is crucial as it allows us to consider points in a left-to-right sweep. 
2. **Greedy Choice**: Iterate through the sorted points. When we encounter the first uncovered point, we must place a new rectangle to cover it. To be maximally efficient (i.e., greedy), we should make this single rectangle cover as many subsequent points as possible. 
3. **Extend and Cover**: We start a new rectangle whose x-range begins at the current point's x-coordinate, let's call it `x_start`. This rectangle can cover any point `p` whose x-coordinate `p.x` is in the range `[x_start, x_start + w]`. We use this one rectangle to cover the current point and all subsequent points that fall within this range. 
4. **Iterate**: After covering a group of points with one rectangle, we move our consideration to the next point that was not covered and repeat the process until all points are accounted for. This greedy choice is optimal because by extending the rectangle to its maximum possible width, we cover the largest possible set of upcoming points. This choice never prevents us from finding an optimal solution for the remaining points. 
Here is the Java implementation: 
```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int minRectanglesToCoverPoints(int[][] points, int w) {
        if (points.length == 0) {
            return 0;
        }

        // Sort the points based on their x-coordinates
        Arrays.sort(points, Comparator.comparingInt(p -> p[0]));

        int rectangles = 1;
        int currentRectStartX = points[0][0];

        for (int i = 1; i < points.length; i++) {
            // If the current point's x-coordinate is outside the
            // current rectangle's coverage
            if (points[i][0] > currentRectStartX + w) {
                // We need a new rectangle
                rectangles++;
                // Start the new rectangle from the current point's x-coordinate
                currentRectStartX = points[i][0];
            }
            // Otherwise, the current point is covered by the existing rectangle,
            // so we do nothing and move to the next point.
        }

        return rectangles;
    }
}
```
### Algorithm
- 1. Sort the `points` array based on the x-coordinate. - 2. If the array is empty, return 0. - 3. Initialize `rectangles = 1` and `currentRectStartX = points[0][0]`. - 4. Iterate through the points starting from the second point (`i=1`). - 5. If the current point's x-coordinate `points[i][0]` is greater than `currentRectStartX + w`, it means the point cannot be covered by the current rectangle. - 6. In that case, increment `rectangles` and start a new rectangle by updating `currentRectStartX` to `points[i][0]`. - 7. After the loop finishes, return the total `rectangles` count.

# Solutions
### CSharp

```csharp
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;
    }
}
```

### Java

```java
class Solution {
public
  int minRectanglesToCoverPoints(int[][] points, int w) {
    Arrays.sort(points, (a, b)->a[0] - b[0]);
    int ans = 0;
    int x1 = -(1 << 30);
    for (int[] p : points) {
      int x = p[0];
      if (x1 + w < x) {
        x1 = x;
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minRectanglesToCoverPoints(vector<vector<int>> &points, int w) {
    sort(points.begin(), points.end());
    int ans = 0, x1 = -(1 << 30);
    for (auto &p : points) {
      int x = p[0];
      if (x1 + w < x) {
        x1 = x;
        ++ans;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minRectanglesToCoverPoints(self, points: List[List[int]], w: int) -> int: points . sort() ans, x1 = 0, - inf for x, _ in points: if x1 + w < x: x1 = x ans += 1 return ans

```