LeetCode 2271 - Maximum White Tiles Covered by a Carpet

LeetCode Problem 2271

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Greedy, Sliding Window, Sorting, Prefix Sum

Solution

That is a long-form reference guide request. To avoid truncation and keep the formatting exact, I will provide the complete solution guide for LeetCode 2271 in a single structured response.

Problem Understanding

The problem gives us a collection of disjoint white tile intervals and a carpet of fixed length. Each interval [li, ri] means every tile position from li through ri is white. The carpet can be placed anywhere on the number line and covers a continuous segment of length carpetLen.

Our goal is to determine the maximum number of white tiles that can be covered by placing the carpet optimally.

A key detail is that tiles are represented as intervals, not individual positions. Since coordinates can be as large as 10^9, we cannot construct an explicit array of tiles. Instead, we must reason about intervals mathematically.

For example, if an interval is [10, 15], it contains:

15 - 10 + 1 = 6

white tiles.

The carpet also covers an interval. If the carpet starts at position x, it covers:

[x, x + carpetLen - 1]

We want to maximize how many white tiles overlap with this carpet range.

The input constraints strongly influence the solution design:

• There can be up to 5 * 10^4 tile intervals.
• Tile coordinates can reach 10^9.
• Intervals are guaranteed to be non-overlapping.

The guarantee that intervals do not overlap simplifies the problem because coverage calculations become independent between intervals.

The large coordinate range makes brute force impossible. We cannot simulate every tile position or every carpet placement.

There are several important edge cases to consider:

• The carpet may fully cover multiple intervals.
• The carpet may partially cover the last interval it reaches.
• The carpet may be longer than an entire cluster of intervals.
• The best placement may begin inside a tile interval rather than exactly at its start.
• Since intervals are non-overlapping but not necessarily sorted, sorting is necessary.

Approaches

Brute Force Approach

A brute force strategy would try every possible carpet placement and calculate how many white tiles are covered.

One reasonable interpretation of brute force is to place the carpet at every meaningful starting position, such as every tile start point, then scan all intervals to compute overlap.

For every interval start tiles[i][0], we could:

1. Compute carpet ending position.
2. Iterate through every tile interval.
3. Add overlap between the carpet range and each interval.

The overlap formula between:

[a, b]

and

[c, d]

is:

max(0, min(b, d) - max(a, c) + 1)

This gives the correct answer because every candidate placement is evaluated exactly.

However, this becomes too slow.

If we test every interval start and scan every interval again:

O(n²)

With n = 5 * 10^4, this is far too expensive.

Key Insight for an Optimal Solution

The important observation is that intervals are non-overlapping and can be sorted.

If we place the carpet starting at the beginning of an interval, then as we move to the next interval, the valid coverage region only shifts forward.

This makes the problem suitable for a sliding window approach.

We can think of the carpet as covering:

[start, start + carpetLen - 1]

For each starting interval:

• Some consecutive intervals are fully covered.
• At most one interval is partially covered.

Since intervals never overlap and coverage only moves forward, we can maintain a moving window instead of recomputing everything from scratch.

The sliding window efficiently tracks:

• Fully covered intervals.
• Partial coverage of the next interval.

This reduces the complexity to:

O(n log n)

because sorting dominates the runtime.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Try every interval start and scan all intervals for overlap
Optimal	O(n log n)	O(1)	Sort intervals and use a sliding window

Algorithm Walkthrough

Optimal Sliding Window Algorithm

1. Sort the intervals by starting position

Since the intervals are non-overlapping but not guaranteed to be sorted, we first sort them. This ensures we can process intervals in increasing order and move pointers only forward. 2. Initialize two pointers

We maintain:

• left, the interval where the carpet starts
• right, the farthest interval fully covered

We also maintain:

• covered_tiles, total fully covered tiles inside the current window
• max_covered, best answer seen so far

3. Fix the carpet start at tiles[left][0]

The carpet spans:

[tiles[left][0], tiles[left][0] + carpetLen - 1]

4. Expand the right pointer

While an interval is fully inside the carpet range:

tiles[right][1] <= carpet_end

add its entire length to covered_tiles.

Interval length is:

tiles[right][1] - tiles[right][0] + 1

5. Handle partial overlap

Once we reach an interval that is not fully covered, it may still overlap partially.

The overlap is:

carpet_end - tiles[right][0] + 1

but only if:

carpet_end >= tiles[right][0]

6. Update the maximum

The total coverage equals:

covered_tiles + partial_overlap

Update the best answer. 7. Move the left pointer

Before advancing:

• Remove the fully covered contribution of tiles[left].

This keeps the sliding window consistent. 8. Repeat until all intervals are processed

Why it works

The key invariant is that the window always contains intervals fully covered by the carpet starting at tiles[left][0]. Because intervals are sorted and non-overlapping, once an interval stops being fully covered, no later interval can suddenly become fully covered. Therefore, the right pointer only moves forward.

At every position, we evaluate all possible fully covered intervals and exactly one partially covered interval. Since any optimal carpet placement can be shifted to begin at a tile start without losing optimality, checking each interval start guarantees correctness.

Python Solution

from typing import List

class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        tiles.sort()

        n = len(tiles)
        left = 0
        right = 0

        covered_tiles = 0
        max_covered = 0

        while left < n:
            carpet_end = tiles[left][0] + carpetLen - 1

            while right < n and tiles[right][1] <= carpet_end:
                covered_tiles += (
                    tiles[right][1] - tiles[right][0] + 1
                )
                right += 1

            partial_cover = 0

            if right < n and tiles[right][0] <= carpet_end:
                partial_cover = (
                    carpet_end - tiles[right][0] + 1
                )

            max_covered = max(
                max_covered,
                covered_tiles + partial_cover
            )

            covered_tiles -= (
                tiles[left][1] - tiles[left][0] + 1
            )

            left += 1

        return max_covered

The implementation begins by sorting the intervals so the sliding window can move monotonically from left to right.

The left pointer determines the carpet start position. For every left, we compute the carpet ending coordinate.

The right pointer expands while intervals are fully covered. Their lengths are accumulated in covered_tiles.

When the next interval is not fully covered, we compute any partial overlap. Since intervals do not overlap, only one interval can be partially covered.

We update the maximum answer using:

fully covered tiles + partially covered tiles

Finally, before moving left, we subtract its interval length from covered_tiles, keeping the sliding window accurate.

Because both pointers only move forward, the traversal remains linear after sorting.

Go Solution

package main

import "sort"

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)

	left := 0
	right := 0

	coveredTiles := 0
	maxCovered := 0

	for left < n {
		carpetEnd := tiles[left][0] + carpetLen - 1

		for right < n && tiles[right][1] <= carpetEnd {
			coveredTiles += tiles[right][1] -
				tiles[right][0] + 1
			right++
		}

		partialCover := 0

		if right < n &&
			tiles[right][0] <= carpetEnd {
			partialCover =
				carpetEnd -
					tiles[right][0] + 1
		}

		current := coveredTiles +
			partialCover

		if current > maxCovered {
			maxCovered = current
		}

		coveredTiles -=
			tiles[left][1] -
				tiles[left][0] + 1

		left++
	}

	return maxCovered
}

The Go implementation follows the same logic as Python. The primary difference is sorting, which uses sort.Slice.

Go does not have Python's dynamic list behavior, so interval lengths and pointer updates are handled explicitly.

Integer overflow is not an issue because the largest coordinate is 10^9, which safely fits inside Go's int on LeetCode environments.

Slices are used naturally for interval storage, and empty versus nil slices are irrelevant here because the constraints guarantee at least one interval.

Worked Examples

Example 1

Input:

tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]]
carpetLen = 10

Sorted tiles are unchanged.

Left	Carpet Range	Fully Covered	Partial	Total
0	[1,10]	[1,5] = 5	[10,11] contributes 1	6
1	[10,19]	[10,11],[12,18] = 9	none	9
2	[12,21]	[12,18] = 7	[20,25] contributes 2	9
3	[20,29]	[20,25] = 6	none	6
4	[30,39]	[30,32] = 3	none	3

Maximum:

9

Example 2

Input:

tiles = [[10,11],[1,1]]
carpetLen = 2

After sorting:

[[1,1],[10,11]]

Left	Carpet Range	Fully Covered	Partial	Total
0	[1,2]	[1,1] = 1	none	1
1	[10,11]	[10,11] = 2	none	2

Maximum:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting costs O(n log n), sliding window traversal is O(n)
Space	O(1)	Only a few variables are used beyond sorting

The sorting step dominates the runtime. After sorting, both pointers move monotonically from left to right, meaning each interval is processed at most once. This makes the sliding window portion linear.

The algorithm uses constant extra memory because it only tracks pointer positions and coverage counts.

Test Cases

sol = Solution()

assert sol.maximumWhiteTiles(
    [[1,5],[10,11],[12,18],[20,25],[30,32]],
    10
) == 9  # Provided example 1

assert sol.maximumWhiteTiles(
    [[10,11],[1,1]],
    2
) == 2  # Provided example 2

assert sol.maximumWhiteTiles(
    [[1,10]],
    5
) == 5  # Partial cover of one interval

assert sol.maximumWhiteTiles(
    [[1,10]],
    20
) == 10  # Carpet longer than interval

assert sol.maximumWhiteTiles(
    [[1,2],[5,6],[9,10]],
    100
) == 6  # Carpet covers all intervals

assert sol.maximumWhiteTiles(
    [[1,5],[10,15]],
    5
) == 5  # Exactly one interval covered

assert sol.maximumWhiteTiles(
    [[1,5],[6,10]],
    7
) == 7  # Carpet spans multiple touching intervals

assert sol.maximumWhiteTiles(
    [[1,1000000000]],
    1000000000
) == 1000000000  # Maximum coordinate range

assert sol.maximumWhiteTiles(
    [[1,2],[100,200]],
    50
) == 50  # Best placement inside large interval

assert sol.maximumWhiteTiles(
    [[1,3],[5,8],[10,15]],
    6
) == 6  # Partial overlap with last interval

Test	Why
Example 1	Validates standard mixed coverage
Example 2	Ensures sorting works correctly
Single interval partial	Tests partial overlap logic
Single interval full	Carpet exceeds interval size
Very large carpet	Covers every interval
Exact interval size	Verifies exact boundary handling
Adjacent intervals	Ensures multi-interval coverage works
Maximum coordinates	Validates large-number handling
Sparse intervals	Tests optimal placement choice
Partial last interval	Confirms partial overlap calculation

Edge Cases

Carpet Longer Than All Tiles

If the carpet length exceeds the total white tile span, a naive implementation might overcount empty gaps between intervals. Since this implementation only counts overlap with white intervals, gaps contribute nothing. The algorithm correctly returns the total number of white tiles.

Partial Coverage of the Last Interval

A common bug occurs when the carpet reaches into an interval but does not fully cover it. An implementation may accidentally ignore the partial overlap or count too much.

This solution explicitly computes:

carpet_end - interval_start + 1

for the next interval after fully covered ones, ensuring accurate partial coverage.

Unsorted Input

The problem guarantees intervals are non-overlapping but does not guarantee ordering. A naive sliding window on unsorted data would fail because pointer movement assumes increasing coordinates.

This implementation sorts the intervals first, ensuring correctness regardless of input order.

Single Interval Input

When only one interval exists, pointer logic can sometimes break due to boundary conditions. This solution handles the case naturally because the window logic still applies, and partial or full coverage is computed correctly.

Large Coordinate Values

Coordinates may reach 10^9, making tile-by-tile simulation impossible. Since the algorithm works entirely with interval arithmetic rather than explicit positions, it remains efficient and memory-safe even at the largest limits.