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.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.
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.
Java
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. |
How many LeetCode problems should you solve? #leetcode #techinterview #developer #softwareengineer • CrioDo • 304,656 views views
Watch 9 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