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.
This approach involves sorting the tiles by their starting position and then using a prefix sum array to store the cumulative white tiles covered up to each position. By simulating placing the carpet at several positions using a sliding window technique, we can efficiently determine the maximum coverage.
The solution sorts the tiles first and maintains a prefix sum array to track cumulative tile coverage. It uses a sliding window approach to simulate placing the carpet starting at each tile beginning, calculating the covered tiles using the prefix sum, and adjusting for partial overlaps.
Python
JavaScript
Time Complexity: O(n log n) due to sorting, where n is the number of tile blocks. Space Complexity: O(n) for the prefix array.
The two-pointer method efficiently handles finding maximum coverage by using one pointer to denote the start of the carpet and another to extend it. By iterating over possible start positions and adjusting the end position based on carpet length, the maximum coverage is determined dynamically.
This C++ solution employs a two-pointer method where the starting point of the carpet is fixed, and the end is dynamically adjusted based on the length. The initial pointer uses inner loops to calculate coverage while the outer loop progresses the starting point.
Time Complexity: O(n log n) due to sorting tiles, and Space Complexity: O(1), meaning memory usage does not scale with input size.
| Approach | Complexity |
|---|---|
| Prefix Array with Sliding Window | Time Complexity: O(n log n) due to sorting, where n is the number of tile blocks. Space Complexity: O(n) for the prefix array. |
| Two-Pointer Technique | Time Complexity: O(n log n) due to sorting tiles, and Space Complexity: O(1), meaning memory usage does not scale with input size. |
| Default Approach | — |
| 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 |
Maximum White Tiles Covered by a Carpet | 2271 LeetCode| Binary Search |Leetcode Biweekly Contest 78 • CodeWithSunny • 4,041 views views
Watch 7 more video solutions →Practice Maximum White Tiles Covered by a Carpet with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor