Scale Engineer

Maximum White Tiles Covered by a Carpet

Med
#2069Time: O(N^2), where N is the number of tiles. Sorting takes O(N log N), but it is dominated by the nested loops which take O(N^2) time.Space: O(log N) or O(N), depending on the space complexity of the sorting algorithm used.1 company
Patterns
Sliding WindowGreedyPrefix Sum
Algorithms
Binary SearchSorting
Data structures
Array
Companies
LTI

Prompt

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 * 104
  • tiles[i].length == 2
  • 1 <= li <= ri <= 109
  • 1 <= carpetLen <= 109
  • The tiles are non-overlapping.

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward approach is to test every possible optimal starting position for the carpet. An optimal placement will always have the carpet's start aligned with the start of a tile. If a carpet starts in a gap between tiles, we can slide it rightwards without losing any coverage until it hits the start of the next tile. Therefore, we only need to consider N possible starting positions, where N is the number of tiles.

Algorithm

  1. Sort the tiles array based on their starting positions l_i.
  2. Initialize a variable maxCoverage to 0.
  3. Iterate through each tile i from 0 to n-1, where n is the number of tiles.
  4. For each i, consider a carpet starting at tiles[i][0]. The carpet's range will be [tiles[i][0], tiles[i][0] + carpetLen - 1].
  5. Initialize currentCoverage to 0 for this placement.
  6. Start a nested loop, iterating through each tile j from i to n-1.
  7. For each tile j, calculate the number of its white tiles that fall within the carpet's range.
  8. The overlap is calculated as max(0, min(carpetEnd, tileEnd) - max(carpetStart, tileStart) + 1).
  9. Add this overlap to currentCoverage.
  10. If a tile j starts beyond the carpet's end, we can break the inner loop since the tiles are sorted.
  11. After the inner loop finishes, update maxCoverage = max(maxCoverage, currentCoverage).
  12. After iterating through all possible start positions, return maxCoverage.

Walkthrough

The algorithm first sorts the tiles based on their starting positions. This helps to prune the search space in the inner loop. It then iterates through each tile i and considers placing the carpet starting at tiles[i][0]. The carpet will cover the range [tiles[i][0], tiles[i][0] + carpetLen - 1]. For each such placement, it iterates through all subsequent tiles j (from i onwards) to calculate the total number of white tiles covered. For each tile j, it calculates the length of the intersection between the tile's range [tiles[j][0], tiles[j][1]] and the carpet's range. The sum of these intersection lengths gives the total coverage for the current carpet placement. The algorithm keeps track of the maximum coverage found across all possible starting positions.

import java.util.Arrays; class Solution {    public int maximumWhiteTiles(int[][] tiles, int carpetLen) {        Arrays.sort(tiles, (a, b) -> Integer.compare(a[0], b[0]));        int n = tiles.length;        int maxCoverage = 0;         if (carpetLen == 0) {            return 0;        }         for (int i = 0; i < n; i++) {            long carpetStart = tiles[i][0];            long carpetEnd = carpetStart + carpetLen - 1;            int currentCoverage = 0;             for (int j = i; j < n; j++) {                long tileStart = tiles[j][0];                long tileEnd = tiles[j][1];                 if (tileStart > carpetEnd) {                    break;                }                 long overlapStart = Math.max(carpetStart, tileStart);                long overlapEnd = Math.min(carpetEnd, tileEnd);                 if (overlapStart <= overlapEnd) {                    currentCoverage += (int)(overlapEnd - overlapStart + 1);                }            }            maxCoverage = Math.max(maxCoverage, currentCoverage);        }        return maxCoverage;    }}

Complexity

Time

O(N^2), where N is the number of tiles. Sorting takes O(N log N), but it is dominated by the nested loops which take O(N^2) time.

Space

O(log N) or O(N), depending on the space complexity of the sorting algorithm used.

Trade-offs

Pros

  • Relatively simple to understand and implement.

Cons

  • The O(N^2) time complexity makes it too slow for the given constraints, likely resulting in a 'Time Limit Exceeded' error on most platforms.

Solutions

class Solution {public  int maximumWhiteTiles(int[][] tiles, int carpetLen) {    Arrays.sort(tiles, (a, b)->a[0] - b[0]);    int n = tiles.length;    int s = 0, ans = 0;    for (int i = 0, j = 0; i < n; ++i) {      while (j < n && tiles[j][1] - tiles[i][0] + 1 <= carpetLen) {        s += tiles[j][1] - tiles[j][0] + 1;        ++j;      }      if (j < n && tiles[i][0] + carpetLen > tiles[j][0]) {        ans = Math.max(ans, s + tiles[i][0] + carpetLen - tiles[j][0]);      } else {        ans = Math.max(ans, s);      }      s -= (tiles[i][1] - tiles[i][0] + 1);    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem