# Maximum White Tiles Covered by a Carpet
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-white-tiles-covered-by-a-carpet)
Canonical: https://scaleengineer.com/dsa/problems/maximum-white-tiles-covered-by-a-carpet
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [LTI](https://scaleengineer.com/companies/lti)
---
## Problem
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:**

![](https://assets.glich.co/dsa/maximum-white-tiles-covered-by-a-carpet/image0.png) 

**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:**

![](https://assets.glich.co/dsa/maximum-white-tiles-covered-by-a-carpet/image1.png) 

**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
## Brute Force by Iterating Through Tile Starts
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Optimized Sliding Window
A more efficient solution uses the sliding window technique. This approach avoids the nested loops of the brute-force method. After sorting the tiles by their start positions, we can iterate through the tiles with a "window" that expands from the right and shrinks from the left. This allows us to find the maximum coverage in a single pass through the tiles, leading to a significantly better time complexity.
**Time:** O(N log N), where N is the number of tiles. The complexity is dominated by the initial sorting step. The subsequent sliding window traversal is O(N). · **Space:** O(log N) or O(N) for sorting. The sliding window itself uses O(1) auxiliary space.
**Pros:** Highly efficient with a time complexity of O(N log N), which is optimal as sorting is required.; Space-efficient, using only O(1) extra space apart from sorting.
**Cons:** The logic is more complex than the brute-force approach and requires careful implementation to handle the window shrinking and partial coverage calculation correctly.
### Explanation
The algorithm begins by sorting the `tiles` array based on their start positions. It uses two pointers, `i` (left) and `j` (right), to define a "window" of tiles `[i, j]`. A variable `currentCover` tracks the sum of the lengths of all tiles currently in the window. The right pointer `j` iterates from the first to the last tile, expanding the window. For each `j`, we add the length of `tiles[j]` to `currentCover`. The key insight is to consider the optimal carpet placement for the current window `[i, j]`. To cover as much of `tiles[j]` as possible, we align the carpet's end with `tiles[j][1]`. This means the carpet starts at `carpetStart = tiles[j][1] - carpetLen + 1`. With this carpet placement, the total span of tiles from `tiles[i][0]` to `tiles[j][1]` might exceed `carpetLen`. So, we have a `while` loop that shrinks the window from the left: as long as the span is greater than `carpetLen`, we remove `tiles[i]` from the window (subtracting its length from `currentCover`) and increment `i`. After the window is valid, `currentCover` holds the sum of lengths of tiles from `i` to `j`. However, the carpet might not start exactly at `tiles[i][0]`. It might start later, cutting off a portion of `tiles[i]`. We calculate this `cutOff` amount and subtract it from `currentCover` to get the true coverage for this window configuration. The maximum coverage found across all windows is the answer.

```java
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 maxCover = 0;
        long currentCover = 0;
        int i = 0; // Left pointer of the sliding window

        for (int j = 0; j < n; j++) { // Right pointer of the sliding window
            currentCover += (long)tiles[j][1] - tiles[j][0] + 1;

            // Shrink window from the left if its span is wider than the carpet
            while (i <= j && (long)tiles[j][1] - tiles[i][0] + 1 > carpetLen) {
                currentCover -= (long)tiles[i][1] - tiles[i][0] + 1;
                i++;
            }

            // At this point, the span of tiles[i..j] is <= carpetLen.
            // However, the carpet can be placed optimally for this window.
            // Consider a carpet ending at tiles[j][1]. It starts at tiles[j][1] - carpetLen + 1.
            // This might cut off a part of the first tile in the window, tiles[i].
            long carpetStart = (long)tiles[j][1] - carpetLen + 1;
            long cutOff = 0;
            if (tiles[i][0] < carpetStart) {
                cutOff = carpetStart - tiles[i][0];
            }
            
            maxCover = Math.max(maxCover, (int)(currentCover - cutOff));
        }
        return maxCover;
    }
}
```
### Algorithm
1. Sort the `tiles` array based on their start positions `l_i`.
2. Initialize two pointers, `i = 0` (left) and `j = 0` (right), to define a sliding window of tiles. Also, initialize `maxCover = 0` and `currentCover = 0` (sum of lengths of tiles in the window).
3. Iterate with the right pointer `j` from `0` to `n-1`:
    a. Add the length of `tiles[j]` to `currentCover` to expand the window.
    b. The span of the current window of tiles `[i, j]` is `tiles[j][1] - tiles[i][0] + 1`. If this span exceeds `carpetLen`, the window is too wide.
    c. Shrink the window from the left: while `tiles[j][1] - tiles[i][0] + 1 > carpetLen`, subtract the length of `tiles[i]` from `currentCover` and increment `i`.
    d. After shrinking, the window `[i, j]` is valid. Now, consider the best placement of the carpet for this window. To maximize coverage, we align the carpet's right end with `tiles[j][1]`. The carpet starts at `carpetStart = tiles[j][1] - carpetLen + 1`.
    e. This placement might not cover `tiles[i]` fully if `tiles[i][0]` is less than `carpetStart`. Calculate the uncovered part of `tiles[i]` as `cutOff = max(0, carpetStart - tiles[i][0])`.
    f. The total coverage for this configuration is `currentCover - cutOff`.
    g. Update `maxCover = max(maxCover, currentCover - cutOff)`.
4. Return `maxCover`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumWhiteTiles(vector<vector<int>> &tiles, int carpetLen) {
    sort(tiles.begin(), tiles.end());
    int s = 0, ans = 0, n = tiles.size();
    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 = max(ans, s + tiles[i][0] + carpetLen - tiles[j][0]);
      } else {
        ans = max(ans, s);
      }
      s -= (tiles[i][1] - tiles[i][0] + 1);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int: tiles . sort() n = len(tiles) s = ans = j = 0 for i, (li, ri) in enumerate(tiles): while j < n and tiles[j][1] - li + 1 <= carpetLen: s += tiles[j][1] - tiles[j][0] + 1 j += 1 if j < n and li + carpetLen > tiles[j][0]: ans = max(ans, s + li + carpetLen - tiles[j][0]) else: ans = max(ans, s) s -= ri - li + 1 return ans

```