Skip to main content
Talentd

Minimum Rectangles to Cover Points - Solution & Explanation

MediumArrayGreedySorting18 min readAsked at: Microsoft
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given coordinates of points on a 2D plane and a rectangle width w. Each rectangle spans vertically but only covers an x-range of length w. The goal is to place the minimum number of rectangles so every point falls within at least one rectangle.

The key observation: the y-coordinate does not affect coverage. A rectangle extends vertically, so only the x-coordinate determines whether a point is covered. The problem reduces to covering x-values with the minimum number of intervals of length w.

Approach 1: Greedy with Sorting (O(n log n) time, O(1) extra space)

Sort the points by their x-coordinate using a standard sorting step. Start with the leftmost point and place a rectangle whose left boundary begins at that point's x-coordinate. This rectangle covers the interval [x, x + w]. Iterate through the sorted list and skip every point whose x-value lies within that range. When a point falls outside the current rectangle, start a new rectangle from that point and repeat the process. This greedy strategy works because placing the rectangle as far left as possible maximizes the number of points covered by each placement.

This solution relies on a classic greedy decision: always cover the earliest uncovered point with the widest possible valid interval. Each point is processed once after sorting, so the dominant cost is the sort operation.

Approach 2: Sliding Window over Sorted Points (O(n log n) time, O(1) space)

Another way to frame the same idea is with a array traversal using a sliding window. After sorting points by x-coordinate, maintain a window that represents the current rectangle's coverage. The left pointer marks the first uncovered point. Extend the right pointer while points remain within x[left] + w. Once the window exceeds that boundary, you finalize the rectangle count and move the left pointer to the first uncovered point.

The sliding window interpretation helps visualize the coverage range and is often easier to reason about during interviews. Both pointers move monotonically across the sorted array, so the scan itself is linear after sorting.

Recommended for interviews: The greedy sorting approach is what interviewers typically expect. It demonstrates recognition that the problem reduces to interval coverage on the x-axis. A quick brute-force attempt might show initial reasoning, but identifying the greedy invariant and sorting the points signals strong algorithmic intuition. The optimal complexity is O(n log n) due to sorting, with O(1) extra space if sorting in place.

Approach 1: Greedy Approach with Sorting

This approach involves sorting the points by their x-coordinates and then using a greedy method to cover as many points as possible with each rectangle. Once the points are sorted, iterate through them and keep a running count of rectangles by checking if a new rectangle is needed to cover uncovered points.

The function minRectangles starts by sorting the points based on their x-coordinates using qsort and a comparison function. Then, it iterates through the sorted list of points, using a greedy approach to determine the minimum number of rectangles required. Each rectangle begins at a position x_start and attempts to cover as many points as possible within the width w. The process is repeated until all points are covered.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to the sorting step, where n is the number of points. Space Complexity: O(1) since no additional data structures are used outside the input sorting.

Try this approach in the editor →

Approach 2: Sliding Window Approach

Another efficient way to solve the problem is using a sliding window. By maintaining a window of x-coordinates, stretch it to cover maximum points within the constraint and move it optimally as points are covered. This is particularly beneficial when handling constraints efficiently.

In this sliding window technique for C, after sorting, we use two pointers: i iterates through each point, and start tracks the point where the current rectangle started. If the x-coordinate for i surpasses start + w, a new rectangle is counted, and start is updated.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting operation. Space Complexity: O(1) for the pointers, requiring constant space.

Try this approach in the editor →

Approach 3: Greedy + Sorting

According to the problem description, we do not need to consider the height of the rectangles, only the width.

We can sort all the points by their x-coordinates and use a variable x_1 to record the rightmost x-coordinate that the current rectangle can cover. Initially, x_1 = -1.

Next, we iterate through all the points. If the current point's x-coordinate x is greater than x_1, it means the existing rectangle cannot cover the current point. We need to add a new rectangle, increment the answer by one, and update x_1 = x + w.

After completing the iteration, we obtain the minimum number of rectangles needed.

The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of points.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach with Sorting

Time Complexity: O(n log n) due to the sorting step, where n is the number of points. Space Complexity: O(1) since no additional data structures are used outside the input sorting.

Sliding Window Approach

Time Complexity: O(n log n) due to sorting operation. Space Complexity: O(1) for the pointers, requiring constant space.

Greedy + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with SortingO(n log n)O(1)General case when points are unsorted. Standard interview solution.
Sliding Window on Sorted PointsO(n log n)O(1)When reasoning about coverage ranges or two-pointer traversal.

Video Solution

3111. Minimum Rectangles to Cover Points | Sorting & Greedy • Aryan Mittal • 1,766 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Minimum Rectangles to Cover Points easy or hard?
The problem is typically classified as Medium. The implementation is straightforward once you realize the y-coordinate is irrelevant and the task reduces to covering sorted x-values with intervals of fixed width using a greedy strategy.
How to solve Minimum Rectangles to Cover Points in O(n)?
An O(n) scan is possible after the points are already sorted by x-coordinate. Iterate from left to right, place a rectangle covering [x, x + w], and skip all points inside that range. If sorting is required beforehand, the overall complexity becomes O(n log n).
What is the best approach for Minimum Rectangles to Cover Points?
The optimal approach is a greedy strategy after sorting points by their x-coordinate. Place a rectangle starting at the leftmost uncovered point and cover all points within the interval [x, x + w]. Continue scanning until a point falls outside the interval, then start a new rectangle. This runs in O(n log n) time due to sorting and O(1) extra space.
What data structure is used in Minimum Rectangles to Cover Points?
The problem mainly uses arrays and sorting. After sorting the array of points by x-coordinate, a simple greedy scan or sliding window determines coverage. No advanced data structures are required.
What is the time complexity of Minimum Rectangles to Cover Points?
The optimal solution runs in O(n log n) time because the points must first be sorted by x-coordinate. After sorting, a single linear scan determines how many rectangles are required, which takes O(n). Space complexity is O(1) if the sorting is done in place.
Minimum Rectangles to Cover Points Python or Java solution approach?
Both Python and Java implementations follow the same pattern: sort the points by x-coordinate, track the current rectangle's right boundary (x + w), and increment the rectangle count when a point exceeds that boundary. The algorithm runs in O(n log n) time and uses constant extra space.
Is Minimum Rectangles to Cover Points asked at Google, Amazon, or Meta?
Greedy interval coverage problems similar to this one frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involve covering points with minimum intervals or scheduling intervals efficiently. Recognizing the greedy strategy is the key interview skill.

Ready to solve this problem?

Practice Minimum Rectangles to Cover Points with our built-in code editor and test cases.

Practice on FleetCode
Previous

K Closest Points to Origin

Next

Minimum Area Rectangle