Maximum White Tiles Covered by a Carpet solution and explanation
Google
7 more videos on this problem
Maximum White Tiles Covered by a Carpet | 2271 LeetCode| Binary Search |Leetcode Biweekly Contest 78CodeWithSunny · 18:08 · 4K views
2271. Maximum White Tiles Covered by a Carpet (Leetcode Medium)Programming Live with Larry · 14:05 · 2K views
2271. Maximum White Tiles Covered by a Carpet || Leetcode biweekly 78 || Leetcode Medium || LeetcodeBinaryMagic · 21:06 · 1K views
Leetcode Biweekly contest 78 Medium -Maximum White Tiles Covered by a CarpetPrakhar Agrawal · 16:47 · 1K views
BiWeekly Contest 78 | 2271. Maximum White Tiles Covered by a CarpetcodingMohan · 23:46 · 1K views
【每日一题】LeetCode 2271. Maximum White Tiles Covered by a CarpetHuifeng Guan · 18:46 · 719 views
Leetcode 2271. Maximum White Tiles Covered by a CarpetAlgo Forces · 22:22 · 76 views
Leetcode 2271. Maximum White Tiles Covered by a Carpet (same as 3413)LetsCode · 26:16 · 37 views
The problem
You are given a 2D integer array tiles where tiles[i] = [li, ri] represents that every tile j in the range li <= j <= ri is colored white.
You are also given an integer carpetLen, the length of a single carpet that can be placed anywhere.
Return the maximum number of white tiles that can be covered by the carpet.
Example 1:
Input: tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10 Output: 9 Explanation: Place the carpet starting on tile 10. It covers 9 white tiles, so we return 9. Note that there may be other places where the carpet covers 9 white tiles. It can be shown that the carpet cannot cover more than 9 white tiles.
Example 2:
Input: tiles = [[10,11],[1,1]], carpetLen = 2 Output: 2 Explanation: Place the carpet starting on tile 10. It covers 2 white tiles, so we return 2.
Constraints:
1 <= tiles.length <= 5 * 104tiles[i].length == 21 <= li <= ri <= 1091 <= carpetLen <= 109- The
tilesare non-overlapping.
Approach overview
Problem Overview: You receive several intervals representing white tiles on a floor and a carpet of fixed length. The goal is to place the carpet so it covers the maximum number of white tiles. Intervals may be far apart, so the solution must account for both fully covered tiles and partially covered segments.
Approach 1: Prefix Array with Sliding Window (O(n log n) time, O(n) space)
Start by sorting the tile intervals by their starting position using sorting. Build a prefix array where each entry stores the cumulative count of white tiles up to that interval. For each interval i, treat its start as the carpet's left boundary and compute the carpet's right boundary start + carpetLen - 1. Use binary search to find the last interval that lies fully within this range. The prefix array instantly gives the number of tiles covered by complete intervals, while a small adjustment handles the partially covered interval at the boundary. This approach is reliable and easy to reason about because the prefix array avoids repeatedly summing tile lengths.
Approach 2: Two-Pointer Technique (O(n) time after sorting, O(1) extra space)
This method treats the intervals like a sliding window over a sorted array. Maintain two pointers: left marks the first interval currently under consideration and right expands the window while intervals remain fully covered by the carpet starting at tiles[left][0]. As the window expands, accumulate the total number of fully covered tiles. If the next interval extends beyond the carpet's limit, compute the partial coverage of that interval and update the maximum result. When the window moves forward, subtract the tile length at left and advance the pointer. Each interval enters and leaves the window once, producing a linear scan after sorting. The technique follows a classic greedy sliding window pattern where coverage is maximized locally.
Recommended for interviews: Interviewers usually expect the sliding window or two-pointer solution. It demonstrates strong understanding of interval processing, greedy reasoning, and window management. Starting with the prefix + binary search method shows structured thinking, while the optimized two-pointer technique highlights deeper algorithmic skill and achieves near-linear runtime.
Approach 1: Prefix Array with Sliding Window
This approach involves sorting the tiles by their starting position and then using a prefix sum array to store the cumulative white tiles covered up to each position. By simulating placing the carpet at several positions using a sliding window technique, we can efficiently determine the maximum coverage.
def maxWhiteTiles(tiles, carpetLen):
tiles.sort()
prefix, coverage, max_covered = [0], 0, 0
for l, r in tiles:
coverage += r - l + 1
prefix.append(coverage)
j = 0
for i in range(len(tiles)):
start, end = tiles[i][0], tiles[i][0] + carpetLen - 1
while j < len(tiles) and tiles[j][1] < end:
j += 1
covered = prefix[j] - prefix[i]
if j < len(tiles):
covered += max(0, end - tiles[j][0] + 1)
max_covered = max(max_covered, covered)
return max_coveredfunction maxWhiteTiles(tiles, carpetLen) {
tiles.sort((a, b) => a[0] - b[0]);
let prefix = [0], coverage = 0, maxCovered = 0;
for(let [l, r] of tiles) {
coverage += r - l + 1;
prefix.push(coverage);
}
let j = 0;
for(let i = 0; i < tiles.length; i++) {
let start = tiles[i][0], end = tiles[i][0] + carpetLen - 1;
while(j < tiles.length && tiles[j][1] < end) {
j++;
}
let covered = prefix[j] - prefix[i];
if(j < tiles.length) {
covered += Math.max(0, end - tiles[j][0] + 1);
}
maxCovered = Math.max(maxCovered, covered);
}
return maxCovered;
}The solution sorts the tiles first and maintains a prefix sum array to track cumulative tile coverage. It uses a sliding window approach to simulate placing the carpet starting at each tile beginning, calculating the covered tiles using the prefix sum, and adjusting for partial overlaps.
Time Complexity: O(n log n) due to sorting, where n is the number of tile blocks. Space Complexity: O(n) for the prefix array.
Approach 2: Two-Pointer Technique
The two-pointer method efficiently handles finding maximum coverage by using one pointer to denote the start of the carpet and another to extend it. By iterating over possible start positions and adjusting the end position based on carpet length, the maximum coverage is determined dynamically.
import java.util.*;
class Solution {
public int maxWhiteTiles(int[][] tiles, int carpetLen) {
Arrays.sort(tiles, (a, b) -> Integer.compare(a[0], b[0]));
int maxCovered = 0, coverage = 0;
int j = 0, start = 0;
while (j < tiles.length) {
while (j < tiles.length && tiles[j][0] < start + carpetLen) {
coverage += Math.min(start + carpetLen - tiles[j][0], tiles[j][1] - tiles[j][0] + 1);
maxCovered = Math.max(maxCovered, coverage);
j++;
}
coverage -= Math.max(0, Math.min(carpetLen, tiles[start][1] - tiles[start][0] + 1));
start++;
}
return maxCovered;
}
}#include<vector>
#include<algorithm>
using namespace std;
int maxWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {
sort(tiles.begin(), tiles.end());
int maxCovered = 0, coverage = 0;
int j = 0, start = 0;
while (j < tiles.size()) {
while (j < tiles.size() && tiles[j][0] < start + carpetLen) {
coverage += min(start + carpetLen - tiles[j][0], tiles[j][1] - tiles[j][0] + 1);
maxCovered = max(maxCovered, coverage);
j++;
}
coverage -= max(0, min(carpetLen, tiles[start][1] - tiles[start][0] + 1));
start++;
}
return maxCovered;
}The Java solution similarly uses two pointers to navigate start and end points of the carpet, calculating overlapping tile coverage dynamically. Arrays.sort is used for initial ordering, and logical checks ensure efficient computation.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1), as it maintains a fixed overhead irrespective of input.
Approach 3: Default Approach
func maximumWhiteTiles(tiles [][]int, carpetLen int) int {
sort.Slice(tiles, func(i, j int) bool { return tiles[i][0] < tiles[j][0] })
n := len(tiles)
s, ans := 0, 0
for i, j := 0, 0; i < n; i++ {
for j < n && tiles[j][1]-tiles[i][0]+1 <= carpetLen {
s += tiles[j][1] - tiles[j][0] + 1
j++
}
if j < n && tiles[i][0]+carpetLen > tiles[j][0] {
ans = max(ans, s+tiles[i][0]+carpetLen-tiles[j][0])
} else {
ans = max(ans, s)
}
s -= (tiles[i][1] - tiles[i][0] + 1)
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Array with Sliding Window | Time Complexity: O(n log n) due to sorting, where n is the number of tile blocks. Space Complexity: O(n) for the prefix array. |
| Two-Pointer Technique | Time Complexity: O(n log n) due to sorting. Space Complexity: O(1), as it maintains a fixed overhead irrespective of input. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Array + Binary Search Sliding Window | O(n log n) | O(n) | When you want a clear interval coverage calculation using prefix sums and binary search |
| Two-Pointer Technique | O(n) after sorting | O(1) | Best for interviews and optimal performance with a greedy sliding window |
Frequently asked questions
Is Maximum White Tiles Covered by a Carpet easy or hard?
Maximum White Tiles Covered by a Carpet is classified as a Medium problem on LeetCode. The difficulty comes from correctly handling partially covered intervals and choosing an efficient sliding window or prefix-based strategy.
Maximum White Tiles Covered by a Carpet Python/Java solution
Python implementations commonly use prefix sums with binary search or a sliding window loop over sorted intervals. Java solutions often implement the two-pointer approach with variables tracking the current window coverage and partial overlaps.
How to solve Maximum White Tiles Covered by a Carpet in O(n)?
After sorting the tile intervals, use a two-pointer sliding window. Expand the right pointer while intervals remain fully covered by the carpet starting at the left interval. Track the sum of covered tile lengths and compute partial coverage when the carpet overlaps only part of the next interval.
What is the best approach for Maximum White Tiles Covered by a Carpet?
The two-pointer sliding window approach is typically the best solution. After sorting the tile intervals, maintain a window of intervals fully covered by the carpet and calculate partial coverage when the boundary cuts through a tile. This runs in O(n) time after sorting and uses O(1) extra space.
Is Maximum White Tiles Covered by a Carpet asked at Google/Amazon/Meta?
Interval coverage and sliding window problems like this appear frequently in interviews at companies such as Amazon, Google, and Meta. The problem tests sorting, greedy reasoning, and efficient window management across interval ranges.
What data structure is used in Maximum White Tiles Covered by a Carpet?
The solution primarily uses arrays of intervals combined with sorting and sliding window pointers. Some implementations also use prefix sum arrays and binary search to quickly compute how many tiles are fully covered within a range.
What is the time complexity of Maximum White Tiles Covered by a Carpet?
The optimal algorithm runs in O(n log n) time overall because the intervals must be sorted first. After sorting, the sliding window or two-pointer scan processes each interval once, which takes O(n). Space complexity ranges from O(1) to O(n) depending on whether prefix arrays are used.