Minimum Rectangles to Cover Points - Practice Coding Problems

Minimum Rectangles to Cover Points - 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.

Input & Output

Example 1 — Basic Case

$ Input: points = [[2,1],[1,1],[4,1]], w = 2

› Output: 2

💡 Note: We can cover point (1,1) and (2,1) with one rectangle [1,3], and point (4,1) with another rectangle [4,6]. Total: 2 rectangles.

Example 2 — Single Rectangle

$ Input: points = [[1,0],[1,1],[2,0]], w = 2

› Output: 1

💡 Note: All points have x-coordinates between 1 and 2, so one rectangle [1,3] can cover all points.

Example 3 — Wide Spread

$ Input: points = [[0,0],[5,0],[10,0]], w = 3

› Output: 3

💡 Note: Points are spread far apart. Need rectangle [0,3] for (0,0), [5,8] for (5,0), and [10,13] for (10,0). Total: 3 rectangles.

Constraints

1 ≤ points.length ≤ 1000
points[i].length == 2
0 ≤ x_i == points[i][0] ≤ 40
0 ≤ y_i == points[i][1] ≤ 40
1 ≤ w ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Points at coordinates (2,1), (1,1), (4,1) with maximum width w=2

Process

Sort points and place rectangles greedily from left to right

Output

Minimum 2 rectangles needed to cover all points

Key Takeaway

🎯 Key Insight: Sort points by x-coordinate and greedily place rectangles to maximize coverage

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to sort points by x-coordinate and greedily place rectangles starting from the leftmost uncovered point, extending each rectangle as far right as possible. Best approach is Greedy with sorting. Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^n)	O(n)	Try all possible ways to place rectangles and find minimum count
Greedy Approach - Sort and Cover	O(n log n)	O(1)	Sort points by x-coordinate and greedily place rectangles

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible rectangle positions
For each combination, check if all points are covered
Return minimum rectangles needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Input Points

Points at coordinates (2,1), (1,1), (4,1) with width w=2

Try All Placements

Generate all possible rectangle starting positions and combinations

Find Minimum

Return the minimum number of rectangles that cover all points

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int minRectangles(int points[][2], int pointsCount, int w, int* covered, int rectCount, int* xCoords, int xCount) {
    // Check if all points are covered
    int allCovered = 1;
    for (int i = 0; i < pointsCount; i++) {
        if (!covered[i]) {
            allCovered = 0;
            break;
        }
    }
    if (allCovered) return rectCount;
    
    if (rectCount >= pointsCount) return INT_MAX;
    
    int minResult = INT_MAX;
    
    // Try placing rectangle at each possible x position
    for (int j = 0; j < xCount; j++) {
        int startX = xCoords[j];
        int endX = startX + w;
        int* newCovered = (int*)malloc(pointsCount * sizeof(int));
        memcpy(newCovered, covered, pointsCount * sizeof(int));
        
        // Mark points covered by this rectangle
        for (int i = 0; i < pointsCount; i++) {
            if (startX <= points[i][0] && points[i][0] <= endX) {
                newCovered[i] = 1;
            }
        }
        
        // Recursively solve remaining
        int result = minRectangles(points, pointsCount, w, newCovered, rectCount + 1, xCoords, xCount);
        if (result < minResult) {
            minResult = result;
        }
        
        free(newCovered);
    }
    
    return minResult;
}

int solution(int points[][2], int pointsCount, int w) {
    if (pointsCount == 0) return 0;
    
    // Extract unique x-coordinates
    int* xCoords = (int*)malloc(pointsCount * sizeof(int));
    int xCount = 0;
    
    for (int i = 0; i < pointsCount; i++) {
        int found = 0;
        for (int j = 0; j < xCount; j++) {
            if (xCoords[j] == points[i][0]) {
                found = 1;
                break;
            }
        }
        if (!found) {
            xCoords[xCount++] = points[i][0];
        }
    }
    
    int* covered = (int*)calloc(pointsCount, sizeof(int));
    int result = minRectangles(points, pointsCount, w, covered, 0, xCoords, xCount);
    
    free(xCoords);
    free(covered);
    return result;
}

int main() {
    // Simple parsing for demo
    int points[100][2];
    int pointsCount = 3;
    points[0][0] = 2; points[0][1] = 1;
    points[1][0] = 1; points[1][1] = 1;
    points[2][0] = 4; points[2][1] = 1;
    int w = 2;
    
    int result = solution(points, pointsCount, w);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Exponential combinations of rectangle placements

⚠ Quadratic Growth

Space Complexity

O(n)

Storage for tracking rectangle combinations

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~15 min Avg. Time

340 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler