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.

Description Hints 2 Solution Video 18:08

2271. Maximum White Tiles Covered by a Carpet

Medium36.9% acceptance3 companies

You are given a 2D integer array tiles where tiles[i] = [l_i, r_i] represents that every tile j in the range l_i <= j <= r_i 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 * 10⁴
tiles[i].length == 2
1 <= l_i <= r_i <= 10⁹
1 <= carpetLen <= 10⁹
The tiles are non-overlapping.

Asked at 3 companies

LTIMindtree Amazon

Google

Topics

Hints open one at a time

Hint 1

Think about the potential placements of the carpet in an optimal solution.

Hint 2

Can we use Prefix Sum and Binary Search to determine how many tiles are covered for a given placement?

18:08

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution