3111. Minimum Rectangles to Cover Points LeetCode Solution

In this guide, you will get 3111. Minimum Rectangles to Cover Points LeetCode Solution with the best time and space complexity. The solution to Minimum Rectangles to Cover Points problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Rectangles to Cover Points solution in C++
Minimum Rectangles to Cover Points solution in Java
Minimum Rectangles to Cover Points solution in Python
Additional Resources

3111. Minimum Rectangles to Cover Points LeetCode Solution image

Problem Statement of Minimum Rectangles to Cover Points

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 = 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 <= 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.

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(\texttt{sort})

3111. Minimum Rectangles to Cover Points LeetCode Solution in C++

class Solution {
 public:
  int minRectanglesToCoverPoints(vector<vector<int>>& points, int w) {
    int ans = 0;
    int prevX = -w - 1;
    vector<int> xs;

    for (const vector<int>& point : points) {
      const int x = point[0];
      xs.push_back(x);
    }

    ranges::sort(xs);

    for (const int x : xs)
      if (x > prevX + w) {
        ++ans;
        prevX = x;
      }

    return ans;
  }
};
/* code provided by PROGIEZ */

3111. Minimum Rectangles to Cover Points LeetCode Solution in Java

class Solution {
  public int minRectanglesToCoverPoints(int[][] points, int w) {
    int ans = 0;
    int prevX = -w - 1;
    int[] xs = new int[points.length];

    for (int i = 0; i < points.length; ++i)
      xs[i] = points[i][0];

    Arrays.sort(xs);

    for (final int x : xs)
      if (x > prevX + w) {
        ++ans;
        prevX = x;
      }

    return ans;
  }
}
// code provided by PROGIEZ

3111. Minimum Rectangles to Cover Points LeetCode Solution in Python

class Solution:
  def minRectanglesToCoverPoints(self, points: list[list[int]], w: int) -> int:
    ans = 0
    prevX = -w - 1
    xs = sorted([x for x, _ in points])

    for x in xs:
      if x > prevX + w:
        ans += 1
        prevX = x

    return ans
 # code by PROGIEZ