Abstract / Summary

Find the largest number of white tiles that can be covered by placing a carpet of given size on a grid with black and white tiles.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 36% (60k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Greedy
• Prefix Sum
• Sliding Window
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation solves the problem of placing a carpet of fixed length on a line of white-tile intervals so that the number of covered tiles is maximized. It first orders the intervals, then uses a sliding-window technique that expands the right side of the window while the carpet fully covers whole intervals, and optionally adds a partial coverage for the next interval. The window is moved leftward one interval at a time, updating the accumulated count of fully covered tiles. The algorithm stops early when the best possible result is already reached.

Sorting the intervals

tiles.sort()
size = len(tiles)

Sorting guarantees that the intervals are processed from left to right, which is essential for the sliding-window logic. After sorting, size holds the total number of intervals.

Main sliding-window loop

covered = 0
right   = 0
for left in range(size):
    last = tiles[left][0] + carpetLen - 1
    ...

The outer loop iterates over each interval as a potential leftmost start of the carpet. last is the farthest tile index that the carpet can reach when it starts at the beginning of the current left interval. The variables covered and right maintain the state of the window: covered stores the total number of tiles that are completely inside the carpet, while right points to the first interval that is not yet fully covered.

Expanding the window to include fully covered intervals

while right < size and tiles[right][1] <= last:
    start, end = tiles[right]
    covered   += 1 + end - start
    right     += 1

The while loop moves the right pointer forward as long as the end of the interval at right lies inside the carpet (tiles[right][1] <= last). For each such interval the exact number of tiles (1 + end - start) is added to covered. This step efficiently aggregates whole intervals without examining each tile individually.

Handling a partially covered interval

partially = 0
if right < size:
    start, end = tiles[right]
    if start <= last:
        partially = 1 + last - start

When the next interval extends beyond last, it may still intersect the carpet. The code checks whether the start of that interval is not beyond the carpet’s end. If it overlaps, partially receives the count of overlapped tiles (1 + last - start). This calculation correctly handles the case where the carpet ends inside an interval.

Updating the best result

result = max(result, covered + partially)

The current coverage is the sum of fully covered tiles (covered) and the possible partial coverage (partially). result retains the maximum value seen so far.

Early termination condition

if result == carpetLen or right == size:
    break

Two situations allow the loop to stop early. If result already equals the carpet length, no larger coverage is possible because the carpet cannot cover more tiles than its own length. If right has reached the end of the interval list, further left moves cannot increase coverage because there are no more intervals to add.

Shrinking the window before the next iteration

start, end = tiles[left]
covered   -= 1 + end - start

Before the outer loop proceeds to the next left index, the interval that is leaving the window is subtracted from covered. This maintains the invariant that covered always reflects the total of intervals fully inside the current carpet position.

Edge cases addressed

When the carpet starts at the very first tile of an interval, last is computed as tiles[left][0] + carpetLen - 1, ensuring that the carpet length is correctly applied even when the interval length is one.

If the carpet length is larger than the span of all intervals combined, the early exit result == carpetLen will trigger after the first full coverage, returning the total number of white tiles.

When intervals are adjacent or overlapping, sorting places them in order and the while-loop’s condition (tiles[right][1] <= last) naturally merges consecutive intervals that fit entirely under the carpet, while the partial calculation correctly caps the contribution at the carpet’s end.

If the carpet lands entirely within a single interval, the while-loop does not advance right, and the partial calculation captures the exact number of tiles covered, because start <= last holds and partially becomes 1 + last - start.

When the list contains a single interval, the outer loop runs once, the while-loop may or may not execute, and the partial logic still yields the correct coverage, after which the early exit condition stops further processing.

Performance optimizations

The algorithm avoids recomputing the sum of covered tiles from scratch on each iteration. By maintaining covered incrementally-adding whole intervals when the right pointer moves forward and subtracting the leftmost interval when it moves backward-the code achieves constant-time updates for each shift of the window.

The early exit check prevents unnecessary iterations once the optimal value is reached, which can dramatically reduce runtime for inputs where the carpet length is large relative to the total span of intervals.

Using integer arithmetic (1 + end - start) to compute interval lengths eliminates the need for additional data structures or function calls, keeping the inner loop tight and cache-friendly.

Overall, the sliding-window approach ensures that each interval is visited at most twice (once when entering the window and once when leaving), leading to a linear pass over the sorted list. This design leverages the sorted order to achieve efficient coverage calculation without auxiliary storage.

Imagine a long path made of many separate patches of white tiles scattered on the ground. You have a rectangular carpet that is a specific size, and the goal is to lay this carpet down so it covers as many white tiles as possible.

First, the patches of tiles are organized in order from the beginning of the path to the end. The carpet needs to be placed starting exactly where one of the white tile groups begins, which helps make sure the carpet is being used as effectively as possible.

A sliding window is used to keep track of the carpet. Think of this like moving the carpet forward along the path. As the carpet moves, it keeps track of all the full groups of white tiles it passes. When the carpet reaches a new group, it counts every white tile in that entire group. If the carpet hits a group that is too long to fit completely under it, it just covers as much as it can until it runs out of space.

After counting the white tiles under the carpet, the carpet slides forward by leaving the very first group of tiles behind. This allows the carpet to look at the next patch of tiles further down the path. By constantly sliding and checking, the carpet finds the best possible spot to cover the most white tiles. Once the carpet has checked all the possible spots, the highest number of tiles it managed to cover is identified.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		C++	Python	Java		TS
	WalkCCC		C++	Python	Java
	leetcode.ca		C++	Python	Java	Go
	Progiez		C++	Python	Java
github	charles-wangkai				Java
	everthis	JS
	fsq		C++
	JoshCrozier	JS
	lkwq007			Python
	muhammadfarhankt					Go
	wisdompeak		C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
muhammadfarhankt	Go
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality