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.To solve #2271 Maximum White Tiles Covered by a Carpet, the key idea is to efficiently determine how many white tiles can be covered by a carpet of fixed length. Since tiles are given as intervals, the first step is to sort the intervals by their starting positions. This ordering allows you to evaluate coverage ranges more efficiently.
A common strategy combines prefix sums with either binary search or a two-pointer / sliding window technique. Prefix sums help quickly compute how many tiles are fully covered within a range, while binary search can locate the farthest tile segment that fits under the carpet. For the last partially covered interval, calculate only the overlapping portion.
The algorithm iterates through possible starting tiles and evaluates the total coverage the carpet can achieve from that position. With sorting and efficient range queries, the approach avoids brute-force checks and keeps the solution scalable for large inputs.
Time Complexity: typically O(n log n) due to sorting and binary search. Space Complexity: O(n) for prefix sums.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Prefix Sum + Binary Search | O(n log n) | O(n) |
| Sorting + Sliding Window (Two Pointers) | O(n log n) due to sorting, O(n) scanning | O(1) to O(n) depending on implementation |
CrioDo
Use these hints if you're stuck. Try solving on your own first.
Think about the potential placements of the carpet in an optimal solution.
Can we use Prefix Sum and Binary Search to determine how many tiles are covered for a given placement?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting the intervals by their starting positions allows efficient range evaluation. Once sorted, techniques like sliding window or binary search can quickly determine which intervals fall within the carpet's coverage range.
Yes, variations of interval coverage and sliding window problems are common in FAANG-style interviews. This problem tests sorting, greedy thinking, and efficient range queries, which are frequently assessed in coding interviews.
The optimal approach sorts the tile intervals and then evaluates coverage using prefix sums with binary search or a sliding window. This allows you to quickly compute how many tiles are fully or partially covered by a carpet starting at each interval. The goal is to maximize coverage without checking every tile individually.
Prefix sums are commonly used to store cumulative tile counts, enabling fast range calculations. Combined with arrays and binary search, they help compute how many tiles are fully covered without iterating through every tile repeatedly.