Maximum White Tiles Covered by a Carpet

Medium
1363.

Maximum White Tiles Covered by a Carpet

Maximum White Tiles Covered by a Carpet is a medium coding problem on arrays, sorting and prefix sum, asked in Amazon and Google interviews.

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^4
  • tiles[i].length == 2
  • 1 <= l <= r <= 10^9
  • 1 <= carpetLen <= 10^9
  • The tiles are non-overlapping.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} tiles
 * @param {number} carpetLen
 * @return {number}
 */
var maximumWhiteTiles = function(tiles, carpetLen) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^4
  • tiles[i].length == 2
  • 1 <= l <= r <= 10^9
  • 1 <= carpetLen <= 10^9
  • The tiles are non-overlapping.

Hints for Maximum White Tiles Covered by a Carpet

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

  2. Hint 2

    Sort the tiles. For a carpet starting at tiles[i].l, the tiles it covers completely form a run i .. j-1, and at most one more tile j is covered partially.

  3. Hint 3

    As i increases, j only moves forward. Keep prefix sums of tile lengths so the full tiles cost O(1), and add the partial overlap with tile j.

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

  1. Sort the tiles by left end and build prefix sums pre of their lengths r - l + 1.
  2. Keep a pointer j (never decreasing). For each i, let end = tiles[i].l + carpetLen - 1 and set j = max(j, i).
  3. Advance j while tiles[j].r <= end — those tiles are fully covered.
  4. Coverage is pre[j] - pre[i] plus, if j < n and tiles[j].l <= end, the partial end - tiles[j].l + 1.
  5. 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 - 1 can 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 j staying at i.

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 ans

Java

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