LeetCode 3111 - Minimum Rectangles to Cover Points

The problem gives us a collection of 2D points, where each point is represented as (xi, yi). We must cover every point using a set of rectangles. Each rectangle has a very special form: - Its bottom edge always lies on the x-axis, meaning the rectangle starts at y = 0.

leetcodemediumarraygreedysorting

LeetCode Problem 3111

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem gives us a collection of 2D points, where each point is represented as (xi, yi). We must cover every point using a set of rectangles.

Each rectangle has a very special form:

  • Its bottom edge always lies on the x-axis, meaning the rectangle starts at y = 0.
  • The rectangle spans horizontally from x1 to x2.
  • The width constraint is x2 - x1 <= w.
  • The height can be anything large enough to include the required points.

A point (x, y) is covered if:

  • x1 <= x <= x2
  • 0 <= y <= y2

Since the rectangle always starts at y = 0, and we can choose any height y2 >= 0, the y coordinate of the points is actually not restrictive. If we decide to cover a point horizontally, we can always extend the rectangle vertically high enough to include it.

This observation is the key simplification of the entire problem.

Effectively, the task becomes:

Cover all x-coordinates using the minimum number of intervals of length at most w.

The y-values become irrelevant after this transformation.

The input size is large:

  • Up to 10^5 points
  • Coordinates up to 10^9

These constraints immediately tell us that:

  • Quadratic solutions are impossible
  • We need something around O(n log n) or better
  • Sorting is likely involved

An important detail is that multiple points may share the same x-coordinate. Since one rectangle can cover all points at the same x-position regardless of height, duplicate x-values do not increase the number of rectangles needed.

There are several important edge cases:

  • w = 0, meaning each rectangle can only cover a single x-coordinate
  • Many points sharing the same x-coordinate
  • Points already fitting into one interval
  • Very large coordinate gaps
  • Points arriving unsorted

The problem guarantees that all (xi, yi) pairs are distinct, but x-values themselves may repeat.

Approaches

Brute Force Approach

A naive approach would try to explore all possible rectangle placements.

For example, we could:

  1. Choose a starting point
  2. Try every possible rectangle that satisfies width <= w
  3. Recursively cover remaining points
  4. Track the minimum number of rectangles used

This eventually finds the optimal answer because it explores every valid grouping of points.

However, this approach is computationally infeasible. The number of possible interval groupings grows exponentially with the number of points. Even memoization would struggle because coordinates can be extremely large and the state space becomes enormous.

With 10^5 points, brute force is completely impractical.

Optimal Greedy Approach

The crucial observation is that only x-coordinates matter.

Once we sort all points by x-coordinate, the problem becomes:

Cover sorted x-values with the minimum number of intervals of length w.

This is a classic greedy interval covering problem.

Suppose we start with the leftmost uncovered x-coordinate start.

To maximize coverage, the best possible rectangle is:

  • Left boundary: start
  • Right boundary: start + w

Any smaller interval would only cover fewer points and could never improve the answer.

So the greedy strategy is:

  1. Sort x-coordinates
  2. Start from the leftmost uncovered point
  3. Create a rectangle covering [x, x + w]
  4. Skip all points inside that interval
  5. Repeat

This works because every rectangle should cover as many future points as possible.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Tries all interval combinations
Optimal Greedy O(n log n) O(1) or O(n) depending on sorting Sorts x-values and greedily covers maximum range

Algorithm Walkthrough

Step 1: Extract and sort x-coordinates

We do not actually need y-values for the solution. Extract all x-coordinates and sort them in ascending order.

Sorting allows us to process points from left to right and greedily cover consecutive ranges.

Step 2: Initialize the rectangle counter

We maintain:

  • rectangles, the number of rectangles used
  • i, the current index in the sorted array

Initially:

  • rectangles = 0
  • i = 0

Step 3: Start a new rectangle at the leftmost uncovered point

Take the current x-coordinate:

start = x_values[i]

The widest valid rectangle we can create spans:

[start, start + w]

This guarantees maximum coverage while respecting the width constraint.

Increment the rectangle count because we are placing a new rectangle.

Step 4: Skip all covered points

Move forward while points remain inside the current interval:

x_values[i] <= start + w

All these points are covered by the current rectangle.

Step 5: Repeat until all points are covered

Continue the process until every point has been processed.

The final rectangle count is the minimum answer.

Why it works

The greedy choice is always optimal because choosing the leftmost uncovered point as the start of a rectangle is unavoidable. Once that point must be covered, the best possible action is to extend the rectangle as far right as allowed, namely to start + w.

Any rectangle with a smaller right boundary would cover fewer points and could never reduce the total number of rectangles needed later.

Thus, every greedy choice is locally optimal and also globally optimal.

Python Solution

from typing import List

class Solution:
    def minRectanglesToCoverPoints(self, points: List[List[int]], w: int) -> int:
        x_values = sorted(point[0] for point in points)

        rectangles = 0
        i = 0
        n = len(x_values)

        while i < n:
            start = x_values[i]
            end = start + w

            rectangles += 1

            while i < n and x_values[i] <= end:
                i += 1

        return rectangles

The implementation begins by extracting and sorting all x-coordinates. This transforms the geometric problem into a one-dimensional interval covering problem.

The variable i tracks the current uncovered point. Each iteration of the outer loop creates one rectangle starting at the leftmost uncovered x-coordinate.

The rectangle covers the interval [start, start + w]. After placing the rectangle, the inner loop skips every point whose x-coordinate falls inside that range.

Because the points are sorted, all covered points appear consecutively, which makes the scan efficient.

The algorithm finishes once every point has been covered.

Go Solution

package main

import "sort"

func minRectanglesToCoverPoints(points [][]int, w int) int {
	xValues := make([]int, len(points))

	for i, point := range points {
		xValues[i] = point[0]
	}

	sort.Ints(xValues)

	rectangles := 0
	n := len(xValues)

	for i := 0; i < n; {
		start := xValues[i]
		end := start + w

		rectangles++

		for i < n && xValues[i] <= end {
			i++
		}
	}

	return rectangles
}

The Go implementation follows the same logic as the Python version.

A slice of x-coordinates is created and sorted using sort.Ints. The algorithm then scans through the sorted slice greedily.

Go integers are sufficient because the maximum coordinate is 10^9, and adding w still remains safely inside the 32-bit signed integer range. Since Go's int is typically 64-bit on modern platforms, overflow is not an issue here.

Worked Examples

Example 1

Input:

points = [[2,1],[1,0],[1,4],[1,8],[3,5],[4,6]]
w = 1

Extract and sort x-values:

[1, 1, 1, 2, 3, 4]

Iteration Trace

Step Current Start Rectangle Range Covered Points Rectangles
1 1 [1, 2] 1,1,1,2 1
2 3 [3, 4] 3,4 2

Final answer:

2

Example 2

Input:

points = [[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6]]
w = 2

Sorted x-values:

[0,1,2,3,4,5,6]

Iteration Trace

Step Current Start Rectangle Range Covered Points Rectangles
1 0 [0,2] 0,1,2 1
2 3 [3,5] 3,4,5 2
3 6 [6,8] 6 3

Final answer:

3

Example 3

Input:

points = [[2,3],[1,2]]
w = 0

Sorted x-values:

[1,2]

Iteration Trace

Step Current Start Rectangle Range Covered Points Rectangles
1 1 [1,1] 1 1
2 2 [2,2] 2 2

Final answer:

2

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(n) Stores extracted x-coordinates

The sorting step requires O(n log n) time. After sorting, the greedy scan processes each point exactly once, which costs O(n) time.

The algorithm stores all x-coordinates in a separate array, requiring O(n) extra space.

Test Cases

from typing import List

class Solution:
    def minRectanglesToCoverPoints(self, points: List[List[int]], w: int) -> int:
        x_values = sorted(point[0] for point in points)

        rectangles = 0
        i = 0

        while i < len(x_values):
            start = x_values[i]
            end = start + w

            rectangles += 1

            while i < len(x_values) and x_values[i] <= end:
                i += 1

        return rectangles

sol = Solution()

# Example 1
assert sol.minRectanglesToCoverPoints(
    [[2,1],[1,0],[1,4],[1,8],[3,5],[4,6]], 1
) == 2  # Two intervals cover all points

# Example 2
assert sol.minRectanglesToCoverPoints(
    [[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6]], 2
) == 3  # Greedy grouping into width-2 ranges

# Example 3
assert sol.minRectanglesToCoverPoints(
    [[2,3],[1,2]], 0
) == 2  # Width zero means one x-coordinate per rectangle

# Single point
assert sol.minRectanglesToCoverPoints(
    [[5,10]], 100
) == 1  # One point always needs one rectangle

# All points share same x-coordinate
assert sol.minRectanglesToCoverPoints(
    [[3,1],[3,5],[3,9]], 0
) == 1  # Same x can share one rectangle

# Large width covers everything
assert sol.minRectanglesToCoverPoints(
    [[1,1],[5,5],[10,10]], 20
) == 1  # Entire range fits into one rectangle

# Points far apart
assert sol.minRectanglesToCoverPoints(
    [[1,1],[100,2],[200,3]], 10
) == 3  # No overlap possible

# Unsorted input
assert sol.minRectanglesToCoverPoints(
    [[10,1],[1,2],[5,3],[2,4]], 3
) == 2  # Sorting is required

# Duplicate x-values with different y-values
assert sol.minRectanglesToCoverPoints(
    [[1,1],[1,2],[1,3],[4,4]], 0
) == 2  # Same x grouped together

# Maximum grouping chain
assert sol.minRectanglesToCoverPoints(
    [[0,0],[2,2],[4,4],[6,6]], 2
) == 2  # Consecutive coverage

Test Case Summary

Test Why
Example 1 Validates standard grouping behavior
Example 2 Tests repeated greedy interval placement
Example 3 Verifies width zero handling
Single point Smallest valid input
Same x-coordinate Ensures y-values are irrelevant
Large width Checks full coverage in one rectangle
Far apart points Ensures separate rectangles are created
Unsorted input Confirms sorting is necessary
Duplicate x-values Tests grouping of repeated x-coordinates
Consecutive chain Verifies optimal interval packing

Edge Cases

One important edge case occurs when w = 0. In this situation, rectangles have zero width and can only cover a single x-coordinate. A buggy implementation might incorrectly assume each point needs its own rectangle, but multiple points sharing the same x-coordinate can still be covered together because the rectangle may have arbitrary height. The implementation handles this correctly because it groups all identical x-values into the same interval [x, x].

Another critical edge case is when all points already fit inside one valid interval. For example, if the smallest x-coordinate is 1, the largest is 10, and w = 20, then a single rectangle is sufficient. The greedy algorithm naturally handles this because the first rectangle covers every point, causing the inner loop to consume the entire array.

A third important case involves unsorted input with large coordinate gaps. Since points may arrive in arbitrary order, failing to sort would break the greedy strategy entirely. The implementation explicitly sorts x-values before processing, ensuring the left-to-right interval covering logic remains valid.

A subtle edge case involves many points sharing the same x-coordinate but having different y-values. Since rectangle height is unrestricted, all such points should always be grouped together. The implementation ignores y-values entirely because horizontal coverage alone determines feasibility.