Watch 8 video solutions for Maximum White Tiles Covered by a Carpet, a medium level problem involving Array, Binary Search, Greedy. This walkthrough by CodeWithSunny has 4,041 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 2D integer array tiles where tiles[i] = [li, ri] represents that every tile j in the range li <= j <= ri 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 * 104tiles[i].length == 21 <= li <= ri <= 1091 <= carpetLen <= 109tiles are non-overlapping.Problem Overview: You receive several intervals representing white tiles on a floor and a carpet of fixed length. The goal is to place the carpet so it covers the maximum number of white tiles. Intervals may be far apart, so the solution must account for both fully covered tiles and partially covered segments.
Approach 1: Prefix Array with Sliding Window (O(n log n) time, O(n) space)
Start by sorting the tile intervals by their starting position using sorting. Build a prefix array where each entry stores the cumulative count of white tiles up to that interval. For each interval i, treat its start as the carpet's left boundary and compute the carpet's right boundary start + carpetLen - 1. Use binary search to find the last interval that lies fully within this range. The prefix array instantly gives the number of tiles covered by complete intervals, while a small adjustment handles the partially covered interval at the boundary. This approach is reliable and easy to reason about because the prefix array avoids repeatedly summing tile lengths.
Approach 2: Two-Pointer Technique (O(n) time after sorting, O(1) extra space)
This method treats the intervals like a sliding window over a sorted array. Maintain two pointers: left marks the first interval currently under consideration and right expands the window while intervals remain fully covered by the carpet starting at tiles[left][0]. As the window expands, accumulate the total number of fully covered tiles. If the next interval extends beyond the carpet's limit, compute the partial coverage of that interval and update the maximum result. When the window moves forward, subtract the tile length at left and advance the pointer. Each interval enters and leaves the window once, producing a linear scan after sorting. The technique follows a classic greedy sliding window pattern where coverage is maximized locally.
Recommended for interviews: Interviewers usually expect the sliding window or two-pointer solution. It demonstrates strong understanding of interval processing, greedy reasoning, and window management. Starting with the prefix + binary search method shows structured thinking, while the optimized two-pointer technique highlights deeper algorithmic skill and achieves near-linear runtime.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Array + Binary Search Sliding Window | O(n log n) | O(n) | When you want a clear interval coverage calculation using prefix sums and binary search |
| Two-Pointer Technique | O(n) after sorting | O(1) | Best for interviews and optimal performance with a greedy sliding window |