Maximum White Tiles Covered by a Carpet — Problem & Solution
Maximum White Tiles Covered by a Carpet solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum White Tiles Covered by a Carpet is a medium coding problem on arrays, sorting and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Prefix Sum, Sliding Window
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A floor is a line of numbered cells. You are given tiles, where tiles[i] = [l, r] means every cell from l to r (inclusive) is white. The ranges do not overlap, and they are given in no particular order.
You also have one carpet that covers exactly carpetLen consecutive cells, and you may lay it anywhere.
Return the maximum number of white cells the carpet can cover.
Example 1
Input: tiles = [[3,6],[10,12],[13,15],[20,24]], carpetLen = 8
Output: 6
Explanation: Laying the carpet on cells 10–17 covers 10–12 and 13–15.
Example 2
Input: tiles = [[7,7],[1,3]], carpetLen = 5
Output: 3
Explanation: Cells 1–5 cover the whole tile `[1,3]`.
Example 3
Input: tiles = [[5,20]], carpetLen = 100
Output: 16
Constraints
1 <= tiles.length <= 5 * 10^4tiles[i].length == 21 <= l <= r <= 10^91 <= carpetLen <= 10^9The tiles are non-overlapping.
Hints for Maximum White Tiles Covered by a Carpet
Hint 1
Some optimal placement starts exactly at the left end of a tile: sliding a carpet right until its start meets a tile's left end never loses white cells.
Hint 2
Sort the tiles. For a carpet starting at
tiles[i].l, the tiles it covers completely form a runi .. j-1, and at most one more tilejis covered partially.Hint 3
As
iincreases,jonly moves forward. Keep prefix sums of tile lengths so the full tiles cost O(1), and add the partial overlap with tilej.
How to solve Maximum White Tiles Covered by a Carpet
Only placements that start at a tile's left end need checking. After sorting, the fully covered tiles for consecutive starts form a sliding window, so prefix sums plus one partial tile give each placement's coverage in O(1).
Approach
- Sort the tiles by left end and build prefix sums
preof their lengthsr - l + 1. - Keep a pointer
j(never decreasing). For eachi, letend = tiles[i].l + carpetLen - 1and setj = max(j, i). - Advance
jwhiletiles[j].r <= end— those tiles are fully covered. - Coverage is
pre[j] - pre[i]plus, ifj < nandtiles[j].l <= end, the partialend - tiles[j].l + 1. - Return the maximum coverage.
Why it works
Take an optimal placement. If its first cell is not white, slide the carpet right one cell at a time: each step drops a non-white cell and gains one cell, so coverage never falls, until the first cell reaches a tile's left end. If its first cell is white but not a tile's left end, slide it left: each step gains a white cell and loses at most one, until the start reaches that tile's left end. Either way some optimal placement starts at a left end. For those starts the carpet's last cell grows with i, so the fully covered tiles form a window whose right edge only advances.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
l + carpetLen - 1can reach about 2·10^9 — compute it in 64-bit.- The input is not sorted; sort it first.
- A carpet shorter than a single tile covers only part of that tile — the partial term handles it, with
jstaying ati.
Reference solution
Python
from typing import List
def maximumWhiteTiles(tiles: List[List[int]], carpetLen: int) -> int:
t = sorted(tiles)
n = len(t)
pre = [0] * (n + 1)
for i in range(n):
pre[i + 1] = pre[i] + t[i][1] - t[i][0] + 1
ans = 0
j = 0
for i in range(n):
end = t[i][0] + carpetLen - 1
j = max(j, i)
while j < n and t[j][1] <= end:
j += 1
cover = pre[j] - pre[i]
if j < n and t[j][0] <= end:
cover += end - t[j][0] + 1
ans = max(ans, cover)
return ansJava
public static int maximumWhiteTiles(int[][] tiles, int carpetLen) {
int[][] t = tiles.clone();
Arrays.sort(t, (a, b) -> Integer.compare(a[0], b[0]));
int n = t.length;
long[] pre = new long[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + t[i][1] - t[i][0] + 1;
long ans = 0;
int j = 0;
for (int i = 0; i < n; i++) {
long end = (long) t[i][0] + carpetLen - 1;
if (j < i) j = i;
while (j < n && t[j][1] <= end) j++;
long cover = pre[j] - pre[i];
if (j < n && t[j][0] <= end) cover += end - t[j][0] + 1;
ans = Math.max(ans, cover);
}
return (int) ans;
}C++
int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {
vector<vector<int>> t(tiles.begin(), tiles.end());
sort(t.begin(), t.end());
int n = t.size();
vector<long long> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + t[i][1] - t[i][0] + 1;
long long ans = 0;
int j = 0;
for (int i = 0; i < n; i++) {
long long end = (long long) t[i][0] + carpetLen - 1;
if (j < i) j = i;
while (j < n && t[j][1] <= end) j++;
long long cover = pre[j] - pre[i];
if (j < n && t[j][0] <= end) cover += end - t[j][0] + 1;
ans = max(ans, cover);
}
return (int) ans;
}JavaScript
var maximumWhiteTiles = function(tiles, carpetLen) {
var t = tiles.slice().sort(function(a, b) { return a[0] - b[0]; });
var n = t.length;
var pre = [0];
for (var i = 0; i < n; i++) pre.push(pre[i] + t[i][1] - t[i][0] + 1);
var ans = 0, j = 0;
for (var i = 0; i < n; i++) {
var end = t[i][0] + carpetLen - 1;
if (j < i) j = i;
while (j < n && t[j][1] <= end) j++;
var cover = pre[j] - pre[i];
if (j < n && t[j][0] <= end) cover += end - t[j][0] + 1;
if (cover > ans) ans = cover;
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms