Skip to main content

Binary Search

Maximum White Tiles Covered by a Carpet Solution in C++/Java/Python/JS

maximum-white-tiles-covered-by-a-carpet-problem-description
maximum-white-tiles-covered-by-a-carpet-problem-description

Maximum White Tiles Covered by a Carpet Problem Description:

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.
maximum-white-tiles-covered-by-a-carpet-problem-description
maximum-white-tiles-covered-by-a-carpet-problem-description

Examples:

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.

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

Brute Force Approach

We are given several tile segments where each segment represents a range of white tiles on a floor. We also have a carpet of fixed length that can be placed anywhere, and our goal is to maximize the number of white tiles covered by the carpet.

The challenge is to efficiently determine the best placement of the carpet so that it covers the most tiles.

Imagine you place the carpet at the start of a tile segment. You now need to quickly find how many tiles it covers.
A brute-force approach would check each individual tile position, which is inefficient because the numbers can be very large (up to 10⁹).

To efficiently determine how many tiles are covered when we place the carpet at a given position, we need a quick way to sum up tiles within a range.

If we manually count tiles for every possible carpet placement, it would be slow.

Instead, we need a way to quickly get the total number of white tiles between any two points. This is where prefix sum helps us!

A prefix sum is a running total of tile counts up to each segment. It allows us to find the sum of tiles in a given range in constant time (O(1)), instead of recalculating every time.

For example, if we have tile segments:

  • tiles = [[1, 5], [10, 11], [12, 18]]
  • The prefix sum will store:
    • Total tiles from start to 1st segment
    • Total tiles from start to 2nd segment
    • Total tiles from start to 3rd segment, etc.

Using this, we can instantly compute the number of tiles between any two indices in just one step, instead of looping through them again and again.

Where to place the carpet in a tile segment?

The carpet can be placed anywhere along the tiles, but checking every single position is inefficient. Instead, we only consider placing it at the start of each tile segment.

Tiles are already grouped into segments (e.g., [1,5], [10,11]). If we place the carpet anywhere inside a segment, the result will be the same as placing it at the start.
By restricting our placement to just the segment starts, we greatly reduce unnecessary calculations while still covering all possibilities.

For example:

  • Placing the carpet at position 1 will give the same coverage as placing it at 2, 3, 4, or 5.
  • So instead of checking every number, we just check 1.
  • Similarly, for [10, 11], we only check 10 instead of 10 & 11 separately.

This means fewer calculations, but no loss of accuracy!

Once we place the carpet at tiles[i][0], we need to find how far it stretches.
The carpet will end at:

end = tiles[i][0] + carpetLen − 1

This gives us the maximum range that the carpet can cover when placed at this position.

For example, if carpetLen = 10 and we place it at tile[0] = 1:

  • It will end at 1 + 10 - 1 = 10.
  • We now need to find all tiles that fall within [1,10].

Once we know the carpet’s end position, we need to find the last tile segment that partially or fully falls within the range.

We start from tiles[i] and move forward until we find the last tile segment that intersects with the carpet’s range.

  • If a tile segment starts beyond the carpet’s end, we stop.
  • Otherwise, we keep adding the tiles from fully covered segments.
  • If a tile segment is only partially covered, we take only the portion within the carpet’s range.

This ensures we don’t overcount tiles while still covering as many as possible.

Now that we know which tiles are fully covered and which ones are partially covered, we compute the total count:

  1. Sum up fully covered segments using the prefix sum.
  2. For the last partially covered segment, add only the part within the carpet range.

For every carpet placement, we compare the tiles covered with our current maximum.

  • If we find a placement that covers more tiles than before, we update our maximum.
  • By the end, we will have the best possible placement for the carpet.
💡
Try it Yourself!

Let's understand with an example:

Maximum White Tiles Covered by a Carpet Example:

Let's say we have:
tiles = [[1, 5], [10, 11], [12, 18], [20, 25], [30, 32]]
carpetLen = 10

  1. Consider placing the carpet at tile 1
    • Carpet reaches till 10
    • Covers [1,5] + [10] → Total = 6 tiles
  3. Consider placing the carpet at tile 10
    • Carpet reaches till 19
    • Covers [10,11] + [12,18] → Total = 9 tiles
  5. Consider placing the carpet at tile 12
    • Carpet reaches till 21
    • Covers [12,18] + part of [20,25] → Total = 9 tiles
  7. Consider placing the carpet at tile 20
    • Carpet reaches till 29
    • Covers [20,25] → Total = 6 tiles

The best placement is at tile 10 or 12, covering 9 tiles.

Steps to Implement the Solution:

  • Sort the Tiles
    • Since we need to consider tiles in a sequential manner, sorting ensures we process them in increasing order.
  • Create a Prefix Sum Array
    • Compute the total count of white tiles up to each index.
    • This allows quick range sum calculations in O(1) time.
  • Iterate Over Each Tile as a Possible Carpet Start
    • The carpet can only be placed starting from the beginning of a tile segment.
  • Calculate the Carpet's End Position
    • The end position is determined by adding carpetLen - 1 to the start position.
  • Find the Last Tile the Carpet Covers Using Linear Search
    • Traverse forward to find the last tile that is at least partially covered.
  • Compute the Total Number of Covered Tiles
    • Use prefix sum to get the count of fully covered tiles.
    • If the last tile is only partially covered, add the covered portion.
  • Update the Maximum Covered Tiles
    • Keep track of the highest number of tiles covered in any configuration.
  • Return the Maximum Covered Tiles
    • The answer is the highest count obtained in the above process.

Maximum White Tiles Covered by a Carpet Leetcode Solution

Maximum White Tiles Covered by a Carpet solution / Code Implementation
1. Maximum White Tiles Covered by a Carpet solution in C++ Try on Compiler 
class Solution {
    // Function to get the sum of tiles in a given range using prefix sum
    int sumOfTiles(vector<int> &prefixSum, int i, int j) {

        // If the range is invalid, return 0
        if (j < 0) return 0;

        // Return the sum of tiles from index i to j
        return prefixSum[j] - (i <= 0 ? 0 : prefixSum[i - 1]);
    }

public:
    int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {
        // Get the number of tile segments
        int n = tiles.size();

        // Sort tiles based on their starting position
        sort(tiles.begin(), tiles.end());

        // Create a prefix sum array to store the total tile count up to each index
        vector<int> prefixSum(n, 0);
        
        // Fill the prefix sum array
        for (int i = 0; i < n; i++) {
            
            // Compute the number of tiles in the current segment
            int tileCount = tiles[i][1] - tiles[i][0] + 1;

            // Compute the prefix sum
            prefixSum[i] = (i == 0 ? tileCount : tileCount + prefixSum[i - 1]);
        }

        // Variable to keep track of the maximum number of tiles covered
        int maxCovered = 0;

        // Iterate through each tile segment to consider it as a carpet start position
        for (int i = 0; i < n; i++) {

            // Compute the starting position of the carpet
            int start = tiles[i][0];
            
            // Compute the ending position of the carpet
            int end = start + carpetLen - 1;

            // Find the last tile segment that the carpet covers using linear search
            int j = i;
            while (j < n && tiles[j][1] < end) {
                j++;
            }

            // Compute the total covered tiles
            int covered = sumOfTiles(prefixSum, i, j - 1);

            // If the last segment is partially covered, add only the covered part
            if (j < n && tiles[j][0] <= end) {
                covered += (end - tiles[j][0] + 1);
            }

            // Update the maximum tiles covered if the current coverage is greater
            maxCovered = max(maxCovered, covered);
        }

        // Return the maximum number of white tiles that can be covered
        return maxCovered;
    }
};

2. Maximum White Tiles Covered by a Carpet solution in Java Try on Compiler 
import java.util.Arrays;

class Solution {
    // Function to get the sum of tiles in a given range using prefix sum
    private int sumOfTiles(int[] prefixSum, int i, int j) {
        // If the range is invalid, return 0
        if (j < 0) return 0;
        // Return the sum of tiles from index i to j
        return prefixSum[j] - (i <= 0 ? 0 : prefixSum[i - 1]);
    }

    public int maximumWhiteTiles(int[][] tiles, int carpetLen) {
        // Get the number of tile segments
        int n = tiles.length;

        // Sort tiles based on their starting position
        Arrays.sort(tiles, (a, b) -> Integer.compare(a[0], b[0]));

        // Create a prefix sum array to store the total tile count up to each index
        int[] prefixSum = new int[n];

        // Fill the prefix sum array
        for (int i = 0; i < n; i++) {
            // Compute the number of tiles in the current segment
            int tileCount = tiles[i][1] - tiles[i][0] + 1;
            // Compute the prefix sum
            prefixSum[i] = (i == 0 ? tileCount : tileCount + prefixSum[i - 1]);
        }

        // Variable to keep track of the maximum number of tiles covered
        int maxCovered = 0;

        // Iterate through each tile segment to consider it as a carpet start position
        for (int i = 0; i < n; i++) {
            // Compute the starting position of the carpet
            int start = tiles[i][0];
            // Compute the ending position of the carpet
            int end = start + carpetLen - 1;

            // Find the last tile segment that the carpet covers using linear search
            int j = i;
            while (j < n && tiles[j][1] < end) {
                j++;
            }

            // Compute the total covered tiles
            int covered = sumOfTiles(prefixSum, i, j - 1);

            // If the last segment is partially covered, add only the covered part
            if (j < n && tiles[j][0] <= end) {
                covered += (end - tiles[j][0] + 1);
            }

            // Update the maximum tiles covered if the current coverage is greater
            maxCovered = Math.max(maxCovered, covered);
        }

        // Return the maximum number of white tiles that can be covered
        return maxCovered;
    }
}

3. Maximum White Tiles Covered by a Carpet solution in Python Try on Compiler 
from bisect import bisect_right

class Solution:
    def maximumWhiteTiles(self, tiles, carpetLen):
        
        # Sort tiles based on their starting position
        tiles.sort()

        # Create a prefix sum array to store the total tile count up to each index
        prefixSum = []
        total = 0

        for l, r in tiles:
            total += (r - l + 1)
            prefixSum.append(total)

        # Variable to keep track of the maximum number of tiles covered
        maxCovered = 0

        # Iterate through each tile segment to consider it as a carpet start position
        for i, (start, _) in enumerate(tiles):
            # Compute the ending position of the carpet
            end = start + carpetLen - 1

            # Find the last tile segment that the carpet covers using linear search
            j = i
            while j < len(tiles) and tiles[j][1] < end:
                j += 1

            # Compute the total covered tiles
            covered = prefixSum[j - 1] - (prefixSum[i - 1] if i > 0 else 0)

            # If the last segment is partially covered, add only the covered part
            if j < len(tiles) and tiles[j][0] <= end:
                covered += (end - tiles[j][0] + 1)

            # Update the maximum tiles covered if the current coverage is greater
            maxCovered = max(maxCovered, covered)

        # Return the maximum number of white tiles that can be covered
        return maxCovered

4. Maximum White Tiles Covered by a Carpet solution in Javascript Try on Compiler 
var maximumWhiteTiles = function(tiles, carpetLen) {
    
    // Sort tiles based on their starting position
    tiles.sort((a, b) => a[0] - b[0]);

    // Create a prefix sum array to store the total tile count up to each index
    let prefixSum = [];
    let total = 0;

    for (let [l, r] of tiles) {
        total += (r - l + 1);
        prefixSum.push(total);
    }

    // Variable to keep track of the maximum number of tiles covered
    let maxCovered = 0;

    // Iterate through each tile segment to consider it as a carpet start position
    for (let i = 0; i < tiles.length; i++) {
        let start = tiles[i][0];
        let end = start + carpetLen - 1;

        // Find the last tile segment that the carpet covers using linear search
        let j = i;
        while (j < tiles.length && tiles[j][1] < end) {
            j++;
        }

        // Compute the total covered tiles
        let covered = prefixSum[j - 1] - (i > 0 ? prefixSum[i - 1] : 0);

        // If the last segment is partially covered, add only the covered part
        if (j < tiles.length && tiles[j][0] <= end) {
            covered += (end - tiles[j][0] + 1);
        }

        // Update the maximum tiles covered if the current coverage is greater
        maxCovered = Math.max(maxCovered, covered);
    }

    // Return the maximum number of white tiles that can be covered
    return maxCovered;
};

Maximum White Tiles Covered by a Carpet Complexity Analysis (brute force)

Time Complexity: O(n²)

  1. We analyze each step of the solution:

1. Sorting the Tiles

  • The sorting step sorts the tiles based on their start position.
  • Sorting takes O(n log n).

2. Creating the Prefix Sum Array

  • We iterate over the n tile segments once and compute the prefix sum.
  • This takes O(n).

3. Iterating Over Each Tile as a Carpet Start

  • We iterate through each tile once, considering it as a possible starting point for the carpet.
  • For each tile, we perform a linear search to find the last tile segment that can be covered.
  • The worst-case scenario is that for each starting tile, the search traverses all remaining tiles O(n).
  • This results in a nested loop, leading to an O(n²) worst-case complexity.

4. Computing Covered Tiles Using Prefix Sum

  • The sum of covered tiles is retrieved in O(1) per iteration using prefix sum.

Final Complexity with Linear Search

  • O(n log n) (sorting) + O(n) (prefix sum) + O(n²) (nested loop from linear search) = O(n²).
  • Since O(n²) dominates, the solution is indeed O(n²) in its current form.

Space Complexity: O(n)

  1. Auxiliary Space Complexity: O(n)
    The algorithm uses a few integer variables. The extra space used is O(n) for the prefixSum vector.
    Therefore, the auxiliary space complexity is O(n).
  2. Total Space Complexity: O(n)
    The total space complexity of the approach is O(n), accounting for the input storage of the tiles array and the additional prefixSum array.
    Therefore, the total space complexity is O(n).

Will Brute Force Work Against the Given Constraints? 

For the current solution, the time complexity is O(n²), where n is the number of tile segments (tiles.length), with an upper limit of 5 × 10⁴.

In the worst-case scenario, when n is at its maximum constraint (5 × 10⁴), the total number of operations can be as large as (5 × 10⁴)² = 2.5 × 10⁹.

This time complexity becomes highly inefficient for large values of n, particularly when n = 5 × 10⁴, leading to billions of operations. While this may work for small test cases, it could cause time limit exceeded (TLE) errors for large inputs due to excessive computations.

In competitive programming, the typical acceptable time complexity limit is around 10⁶ operations per test case. Since this solution may perform significantly more operations (10⁹ in the worst case), it is highly impractical for large inputs and needs optimization.

How to optimize it?

In the previous approach, we iterated through each tile segment and checked every possible placement of the carpet by linearly searching for the last tile segment that the carpet could cover. This resulted in O(n²) complexity, where n is the number of tile segments (tiles.length).

Now, let’s think about improving this approach.
Since we checked every segment one-by-one for every starting tile, we ended up with a lot of redundant operations. This inefficiency became a major bottleneck, especially when n was large (5 × 10⁴).

The main issue was that for each starting tile, we performed a linear search to determine the farthest tile the carpet could reach. That means if we start from tile segment i, we keep moving one-by-one to the next segment until we find the first segment that exceeds the carpet’s range.

But wait! Do we need to check every segment linearly?
Not really! We are essentially trying to find the farthest tile that can be covered starting from each segment. Instead of going step by step, can we jump directly to the right place?

Yes!
Since we are searching for a tile within a sorted range, binary search comes to the rescue.

First, we need to ensure that our tiles array is sorted based on the starting positions. Sorting allows us to search in a structured way instead of going through the entire list blindly.

Once sorted, the main idea is simple:

  • Instead of linearly iterating through tile segments to find where the carpet ends, we can directly jump to the right tile using binary search.
  • Since the carpet covers tiles from start position to start + carpetLen - 1, we need to find the last tile segment where the start of the segment is within this range.

Now that we have a sorted tile list and need to efficiently find the last tile segment within range, can we apply binary search?

Can Binary Search Works Here?

Let’s check whether binary search conditions are met:

  1. Is the data sorted?
    • Yes! We first sort the tiles array based on the starting position.
  2. Is the search space monotonic?
    • Yes! If a tile segment’s start position is within the carpet’s range, then all previous tile segments are also within the range.
    • If a tile segment’s start position is out of range, then all subsequent tile segments will also be out of range.
  3. Can the middle element help minimize/maximize the search space?
    • Yes! By checking if the carpet covers the middle tile segment, we can determine whether to search further to the right (expand coverage) or move left (reduce range).

Thus, binary search perfectly fits the problem!

Maximum White Tiles Covered by a Carpet Binary Search Algorithm

Now that we know binary search is applicable, let's break it down step by step:

  1. Sort the tiles array based on li (starting tile of each segment).
  2. For each tile segment as the starting position of the carpet:
    • Define low = i, high = n - 1, endIndex = i.
    • Perform binary search to find the last segment that the carpet can fully or partially cover:
      • Compute mid = low + (high - low) / 2.
      • If tiles[mid][0] ≤ end, update endIndex = mid and search further right (low = mid + 1).
      • Otherwise, move left (high = mid - 1).
  3. Calculate the number of tiles covered:
    • Use a prefix sum array to quickly compute the total number of tiles in all fully covered segments.
    • Add the partial tiles from the last covered segment (if applicable).
  4. Update the maximum covered tiles found so far.

By applying binary search, we reduce the linear searching step from O(n) to O(log n), drastically improving performance.

💡
How binary search works?

Once we find the rightmost tile segment that can be covered by the carpet using binary search, we need to determine:

  1. How many tiles are covered in the completely included segments?
    • This can be computed using a prefix sum array, where prefixSum[j] - prefixSum[i - 1] gives the total tiles covered from index i to j.
  2. How many tiles are covered in the partially included segment?
    • If the carpet ends in the middle of a tile segment, we only count the portion that is covered.

Finally, we compare this coverage with the maximum covered so far, and update the maximum.

Let us understand this with a video.

0:00
/2:46

maximum-white-tiles-covered-by-a-carpet-optimal-approach-animation

💡
Try it Yourself!

Let's understand with an example:

Maximum White Tiles Covered by a Carpet Example:

Input: tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10

1st Iteration (Starting at [1,5])

  • Carpet covers range: [1, 10]
  • Binary search for endIndex: Finds endIndex = 1 (last covered segment).
  • Tiles fully covered: [1,5]
  • Partial tiles: [10]
  • Total covered: 6

2nd Iteration (Starting at [10,11])

  • Carpet covers range: [10, 19]
  • Binary search for endIndex: Finds endIndex = 2.
  • Tiles fully covered: [10,11], [12,18]
  • Total covered: 9 (New max)

3rd Iteration (Starting at [12,18])

  • Carpet covers range: [12, 21]
  • Binary search for endIndex: Finds endIndex = 3.
  • Tiles fully covered: [12,18]
  • Partial tiles: [20,21]
  • Total covered: 9 (No improvement)

4th Iteration (Starting at [20,25])

  • Carpet covers range: [20, 29]
  • Binary search for endIndex: Finds endIndex = 3.
  • Tiles fully covered: [20,25]
  • Total covered: 6 (No improvement)

5th Iteration (Starting at [30,32])

  • Carpet covers range: [30, 39]
  • Binary search for endIndex: Finds endIndex = 4.
  • Tiles fully covered: [30,32]
  • Total covered: 3 (No improvement)

Final Answer: 9

How to code it up:

Here’s a concise step-by-step breakdown of how to implement the optimized solution:

  1. Sort the tiles array
    Sort based on the starting position of each tile segment.
  2. Build a prefix sum array
    Compute the cumulative number of tiles up to each segment for quick range sum calculations.
  3. Iterate through each tile segment as a potential starting position for the carpet
    Define the carpet’s start position and calculate its end position.
  4. Apply Binary Search to find the last tile segment the carpet can fully or partially cover.
    Use binary search to locate the rightmost tile segment within the carpet’s reach.
  5. Compute the number of covered tiles
    Use the prefix sum array to quickly get the number of fully covered tiles.
    If the last segment is only partially covered, add those tiles manually.
  6. Update the maximum number of tiles covered
    Track the maximum white tiles covered across all placements.
  7. Return the final result
    The maximum tiles covered is the final answer.

Maximum White Tiles Covered by a Carpet Leetcode Solution

Maximum White Tiles Covered by a Carpet solution / Code Implementation
1. Maximum White Tiles Covered by a Carpet solution in C++ Try on Compiler 
class Solution {
    // Function to compute the sum of tiles covered between indices i and j using prefix sum
    int sumOfTiles(vector<int> &prefixSum, int i, int j) {
        // If j is out of bounds, return 0 (invalid case)
        if (j < 0) return 0;

        // Calculate the sum of tiles from index i to j
        return prefixSum[j] - (i <= 0 ? 0 : prefixSum[i - 1]);
    }

public:
    int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {
        // Get the number of tile segments
        int n = tiles.size();

        // Sort the tiles based on the starting index to ensure sequential processing
        sort(tiles.begin(), tiles.end());

        // Create a prefix sum array to store cumulative tile counts
        vector<int> prefixSum(n, 0);
        
        // Fill the prefix sum array
        for (int i = 0; i < n; i++) {
            int tileCount = tiles[i][1] - tiles[i][0] + 1;
            prefixSum[i] = (i == 0 ? tileCount : tileCount + prefixSum[i - 1]);
        }

        // Variable to store the maximum number of covered white tiles
        int maxCovered = 0;

        // Iterate through each tile segment as the starting position of the carpet
        for (int i = 0; i < n; i++) {
            // Determine the carpet's starting and ending positions
            int start = tiles[i][0];
            int end = start + carpetLen - 1;

            // Apply binary search to find the last tile segment that the carpet covers
            int low = i, high = n - 1, endIndex = i;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                
                // Check if the current segment is within the carpet's reach
                if (tiles[mid][0] <= end) {
                    endIndex = mid;
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }

            // Compute the fully covered tiles using the prefix sum array
            int covered = sumOfTiles(prefixSum, i, endIndex - 1);
            
            // Compute partially covered tiles in the last segment, if applicable
            if (tiles[endIndex][0] <= end) {
                covered += min(tiles[endIndex][1], end) - tiles[endIndex][0] + 1;
            }

            // Update the maximum covered tiles found so far
            maxCovered = max(maxCovered, covered);
        }

        // Return the maximum number of white tiles covered by the carpet
        return maxCovered;
    }
};

2. Maximum White Tiles Covered by a Carpet solution in Java Try on Compiler 
import java.util.*;

class Solution {
    // Function to compute the sum of tiles covered using prefix sum
    private int sumOfTiles(int[] prefixSum, int i, int j) {
        if (j < 0) return 0;
        return prefixSum[j] - (i <= 0 ? 0 : prefixSum[i - 1]);
    }

    public int maximumWhiteTiles(int[][] tiles, int carpetLen) {
        // Get the number of tile segments
        int n = tiles.length;

        // Sort the tiles based on the starting index
        Arrays.sort(tiles, Comparator.comparingInt(a -> a[0]));

        // Create a prefix sum array to store cumulative tile counts
        int[] prefixSum = new int[n];

        // Fill the prefix sum array
        for (int i = 0; i < n; i++) {
            int tileCount = tiles[i][1] - tiles[i][0] + 1;
            prefixSum[i] = (i == 0 ? tileCount : tileCount + prefixSum[i - 1]);
        }

        // Variable to store the maximum number of covered white tiles
        int maxCovered = 0;

        // Iterate through each tile segment as the starting position of the carpet
        for (int i = 0; i < n; i++) {
            // Determine the carpet's starting and ending positions
            int start = tiles[i][0];
            int end = start + carpetLen - 1;

            // Apply binary search to find the last tile segment that the carpet covers
            int low = i, high = n - 1, endIndex = i;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (tiles[mid][0] <= end) {
                    endIndex = mid;
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }

            // Compute the fully covered tiles using the prefix sum array
            int covered = sumOfTiles(prefixSum, i, endIndex - 1);

            // Compute partially covered tiles in the last segment, if applicable
            if (tiles[endIndex][0] <= end) {
                covered += Math.min(tiles[endIndex][1], end) - tiles[endIndex][0] + 1;
            }

            // Update the maximum covered tiles found so far
            maxCovered = Math.max(maxCovered, covered);
        }

        // Return the maximum number of white tiles covered by the carpet
        return maxCovered;
    }
}

3. Maximum White Tiles Covered by a Carpet solution in Python Try on Compiler 
from bisect import bisect_right

class Solution:
    def maximumWhiteTiles(self, tiles, carpetLen):
        # Sort the tiles based on the starting index
        tiles.sort()
        
        # Create a prefix sum array to store cumulative tile counts
        prefixSum = [0] * len(tiles)
        
        # Fill the prefix sum array
        for i in range(len(tiles)):
            tileCount = tiles[i][1] - tiles[i][0] + 1
            prefixSum[i] = tileCount if i == 0 else tileCount + prefixSum[i - 1]
        
        # Function to compute the sum of tiles covered using prefix sum
        def sumOfTiles(i, j):
            if j < 0:
                return 0
            return prefixSum[j] - (prefixSum[i - 1] if i > 0 else 0)

        maxCovered = 0

        # Iterate through each tile segment as the starting position of the carpet
        for i in range(len(tiles)):
            start = tiles[i][0]
            end = start + carpetLen - 1

            # Apply binary search to find the last tile segment that the carpet covers
            low, high, endIndex = i, len(tiles) - 1, i
            while low <= high:
                mid = (low + high) // 2
                if tiles[mid][0] <= end:
                    endIndex = mid
                    low = mid + 1
                else:
                    high = mid - 1

            # Compute the fully covered tiles using the prefix sum array
            covered = sumOfTiles(i, endIndex - 1)

            # Compute partially covered tiles in the last segment, if applicable
            if tiles[endIndex][0] <= end:
                covered += min(tiles[endIndex][1], end) - tiles[endIndex][0] + 1

            # Update the maximum covered tiles found so far
            maxCovered = max(maxCovered, covered)

        return maxCovered

4. Maximum White Tiles Covered by a Carpet solution in Javascript Try on Compiler 
/**
 * @param {number[][]} tiles
 * @param {number} carpetLen
 * @return {number}
 */
// Function to compute the sum of tiles covered between indices i and j using prefix sum
var sumOfTiles = function (prefixSum, i, j) {

    // If j is out of bounds, return 0 (invalid case)
    if (j < 0) return 0;

    // Calculate the sum of tiles from index i to j
    return prefixSum[j] - (i <= 0 ? 0 : prefixSum[i - 1]);
};

var maximumWhiteTiles = function (tiles, carpetLen) {
    // Get the number of tile segments
    let n = tiles.length;

    // Sort the tiles based on the starting index to ensure sequential processing
    tiles.sort((a, b) => a[0] - b[0]);

    // Create a prefix sum array to store cumulative tile counts
    let prefixSum = new Array(n).fill(0);

    // Fill the prefix sum array
    for (let i = 0; i < n; i++) {
        let tileCount = tiles[i][1] - tiles[i][0] + 1;
        prefixSum[i] = (i === 0 ? tileCount : tileCount + prefixSum[i - 1]);
    }

    // Variable to store the maximum number of covered white tiles
    let maxCovered = 0;

    // Iterate through each tile segment as the starting position of the carpet
    for (let i = 0; i < n; i++) {
        
        // Determine the carpet's starting and ending positions
        let start = tiles[i][0];
        let end = start + carpetLen - 1;

        // Apply binary search to find the last tile segment that the carpet covers
        let low = i, high = n - 1, endIndex = i;
        while (low <= high) {
            let mid = Math.floor(low + (high - low) / 2);

            // Check if the current segment is within the carpet's reach
            if (tiles[mid][0] <= end) {
                endIndex = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        // Compute the fully covered tiles using the prefix sum array
        let covered = sumOfTiles(prefixSum, i, endIndex - 1);

        // Compute partially covered tiles in the last segment, if applicable
        if (tiles[endIndex][0] <= end) {
            covered += Math.min(tiles[endIndex][1], end) - tiles[endIndex][0] + 1;
        }

        // Update the maximum covered tiles found so far
        maxCovered = Math.max(maxCovered, covered);
    }

    // Return the maximum number of white tiles covered by the carpet
    return maxCovered;
};

Time Complexity: O(n log n)

The given algorithm consists of three main operations:

  1. Sorting the Tiles Array
    • The tiles array is sorted based on the starting position.
    • Sorting takes O(n log n) time.
  3. Building the Prefix Sum Array
    • The prefix sum array is constructed in a single pass.
    • This takes O(n) time.
  5. Processing Each Tile Segment
    • The outer loop iterates over each tile segment O(n) times.
    • Inside the loop, binary search is used to find the last segment the carpet can cover.
    • Binary search takes O(log n) time for each tile segment.

Thus, the total time complexity can be expressed as:

O(n log⁡n)+O(n)+O(n log⁡n)=O(n log⁡n)

Final Complexity: O(n log n)

Space Complexity: O(n)

  1. Auxiliary Space Complexity: O(n)
    The algorithm uses a few integer variables. The extra space used is O(n) for the prefixSum vector.
    Therefore, the auxiliary space complexity is O(n).
  2. Total Space Complexity: O(n)
    The total space complexity of the approach is O(n), accounting for the input storage of the tiles array and the additional prefixSum array.
    Therefore, the total space complexity is O(n).

Is there any scope for further optimizations?

Alright, let’s take a step back and think. Our initial approach was straightforward:

  1. We tried every possible starting position for the carpet (by iterating through each tile segment).
  2. For each starting position, we checked how many tiles could be covered by iterating forward until the carpet’s limit was exceeded.
  3. At each step, we updated the maximum number of covered tiles.

This was a brute-force sliding window approach, where for every tile segment, we performed a linear scan to determine coverage. That gave us a time complexity of O(n²) in the worst case, which is too slow!

Yes! We noticed that we are repeatedly resetting the second pointer (j) for every new starting position (i). That’s inefficient because we are redoing work that was already done.

How Are We Redoing Work?
Let’s break it down with an example:

  • We start with i = 0, place the carpet, and move j forward to check how far it can reach.
  • We count the covered tiles and store the maximum.

Now, instead of continuing from where we left off, we reset j back to i+1 and start the process again!

For every new i, we:

  1. Move j forward from scratch, even though we just found where the carpet should end.
  2. Recount covered tiles manually, even though most of them were already counted in the previous step.
  3. Recompute everything, even though only a few tiles at the start change.

This means that instead of a single pass over the array, we are repeating our work from the beginning for each new i, making it unnecessarily slow.

Where’s the Waste?

Think of it like dragging a physical carpet over the tiles:

  • Instead of lifting and re-laying it from scratch, you slide it forward and just adjust its endpoint as needed.
  • The carpet always moves in one direction, so we never waste effort looking at past tiles again.
  • We keep track of how many tiles we’re covering at any given moment, ensuring we always know the best possible placement.

The key inefficiency is that we are not taking advantage of the fact that the tiles are sorted. If we already pushed j forward for one starting position, why should we reset it?

This is why a true sliding window approach works better—we reuse our previous work by keeping j where it was and only moving it forward when necessary.

Transforming It Into a Sliding Window Approach: Why and How?

Okay, so we’ve identified the main inefficiency in our brute-force approach: we keep restarting our search for every new carpet position, which means we’re repeating a lot of work. Instead of that, we can use a two-pointer (or sliding window) approach to make our solution much faster. Let’s go step by step and understand how this works.

First things first, we sort the tile segments by their starting positions. Why?

  • This ensures that as we move the carpet forward, we are always checking tiles in the correct order.
  • Sorting allows us to process tiles sequentially, which is crucial for our sliding window approach to work efficiently.

Now, let’s introduce two pointers to efficiently track the range of tiles covered by the carpet.

Two Pointers - Expanding the Carpet Coverage Efficiently

Instead of restarting the search for every i, we introduce j to track the farthest segment the carpet can cover.

  • Pointer i represents the starting tile of the carpet.
  • Pointer j represents the last tile segment that still fits under the carpet.

Here’s how we make it efficient:

  1. Start with i at the first tile.
  2. Move j forward as much as possible without exceeding the carpet’s length.
  3. Count the number of tiles covered between i and j.
  4. Update the maximum covered tiles.
  5. Move i forward and repeat (but do not reset j—just adjust it if needed).

Why This Works Efficiently

This sliding window approach ensures that:

  1. Each tile segment is only processed once.
  • In the brute-force approach, we checked the same tile multiple times because we restarted the search for every i.
  • Now, each tile is checked once, making our approach much faster.
  1. We never recheck tiles unnecessarily.
  • The second pointer j never moves backward. It only moves forward when necessary.
  • This prevents redundant work and speeds up the solution significantly.
  1. We reuse previous results instead of searching from scratch.
  • When moving i forward, we don’t restart j—instead, we continue from where j left off.
  • This prevents an extra O(n) search for every i, reducing the complexity from O(n²) to O(n).

By doing this, we eliminate redundant calculations and reduce our time complexity from O(n²) to O(n)!

💡
Try it Yourself!

Let's understand with an example:

Maximum White Tiles Covered by a Carpet Example:

Given Input:

tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10

Step 1: Sorting Tiles (Already Sorted)

Sorted tiles: [[1,5], [10,11], [12,18], [20,25], [30,32]]

Step 2: Sliding Window Approach

We use two pointers (i, j) to find the maximum tiles covered by the carpet.

  1. i = 0 (Carpet starts at tile 1)
    • Extend j to cover as much as possible → j stops at tile [10,11] (because tile [12,18] exceeds carpet reach).
    • Tiles covered: 5 (from [1,5]) + 1 (from [10,11]) = 6
    • Max covered so far: 7
  3. i = 1 (Carpet starts at tile 10)
    • Extend j to cover more → j stops at tile [12,18] (because tile [20,25] exceeds carpet reach).
    • Tiles covered: 2 (from [10,11]) + 7 (from [12,18]) = 9
    • Max covered so far: 9
  5. i = 2 (Carpet starts at tile 12)
    • Extend j → j stops at tile [20,25].
    • Tiles covered: 7 (from [12,18]) + 3 (partial from [20,25]) = 10 (exceeds limit).
    • So, we consider only the valid portion: 9
    • Max covered remains: 9
  7. i = 3 (Carpet starts at tile 20)
    • Extend j → j stops at tile [30,32].
    • Tiles covered: 6 (from [20,25]) + 3 (from [30,32]) = 9
    • Max covered remains: 9
  9. i = 4 (Carpet starts at tile 30)
    • Extend j → Carpet only covers tile [30,32].
    • Tiles covered: 3
    • Max covered remains: 9

Final Answer: 9

Steps to Implement the Solution:

Step 1: Sort the Tiles

  • Since the input tile segments are unsorted, start by sorting them based on their starting position.
  • This ensures that when we iterate, the tiles appear in sequential order.

Step 2: Compute Prefix Sum Array

  • Create a prefix sum array to store cumulative tile counts.
  • This helps efficiently compute the number of tiles covered within any range.

Step 3: Use a Two-Pointer Sliding Window

  • Initialize two pointers:
    • i (starting position of the carpet)
    • j (expanding pointer for the farthest position the carpet can reach)
  • Iterate over i and try to extend j as far as possible without exceeding the carpet length.

Step 4: Compute the Covered Tiles

  • Use the prefix sum array to quickly compute the number of tiles covered between i and j.
  • If the last segment (j-th segment) is only partially covered, add the additional tiles manually.

Step 5: Update Maximum Coverage

  • Keep track of the maximum number of tiles covered by the carpet.

Step 6: Return the Result

  • After iterating through all possible starting positions, return the maximum tiles covered.

Maximum White Tiles Covered by a Carpet leetcode solution

Maximum White Tiles Covered by a Carpet solution / Code Implementation
1. Maximum White Tiles Covered by a Carpet solution in c++ Try on Compiler 
class Solution {
    // Function to compute the sum of tiles covered between indices i and j using prefix sum
    int sumOfTiles(vector<int> &prefixSum, int i, int j) {
        // If j is out of bounds, return 0 (invalid case)
        if (j < 0) return 0;
        
        // Calculate the sum of tiles from index i to j
        return prefixSum[j] - (i <= 0 ? 0 : prefixSum[i - 1]);
    }

public:
    int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {
        // Get the number of tile segments
        int n = tiles.size();

        // Sort the tiles based on the starting index to ensure sequential processing
        sort(tiles.begin(), tiles.end());

        // Create a prefix sum array to store cumulative tile counts
        vector<int> prefixSum(n, 0);
        
        // Fill the prefix sum array
        for (int i = 0; i < n; i++) {
            // Calculate the number of tiles in the current segment
            int tileCount = tiles[i][1] - tiles[i][0] + 1;
            
            // Store cumulative sum of tiles
            prefixSum[i] = (i == 0 ? tileCount : tileCount + prefixSum[i - 1]);
        }

        // Variable to store the maximum number of covered white tiles
        int maxCovered = 0;
        
        // Two-pointer approach: j represents the end of the carpet's coverage
        int j = 0;

        // Iterate through each tile segment as the starting position of the carpet
        for (int i = 0; i < n; i++) {
            // Determine the carpet's starting and ending positions
            int start = tiles[i][0];
            int end = start + carpetLen - 1;

            // Expand j to find the last tile segment within the carpet's reach
            while (j < n && tiles[j][1] < end) {
                j++;
            }

            // Compute the fully covered tiles using the prefix sum array
            int covered = sumOfTiles(prefixSum, i, j - 1);
            
            // Compute partially covered tiles in the last segment, if applicable
            if (j < n && tiles[j][0] <= end) {
                covered += (end - tiles[j][0] + 1);
            }

            // Update the maximum covered tiles found so far
            maxCovered = max(maxCovered, covered);
        }

        // Return the maximum number of white tiles covered by the carpet
        return maxCovered;
    }
};

2. Maximum White Tiles Covered by a Carpet solution in Java Try on Compiler 
import java.util.*;

class Solution {
    // Function to compute the sum of tiles covered between indices i and j using prefix sum
    private int sumOfTiles(int[] prefixSum, int i, int j) {
        // If j is out of bounds, return 0 (invalid case)
        if (j < 0) return 0;
        
        // Calculate the sum of tiles from index i to j
        return prefixSum[j] - (i <= 0 ? 0 : prefixSum[i - 1]);
    }

    public int maximumWhiteTiles(int[][] tiles, int carpetLen) {
        // Get the number of tile segments
        int n = tiles.length;
        
        // Sort the tiles based on the starting index to ensure sequential processing
        Arrays.sort(tiles, (a, b) -> Integer.compare(a[0], b[0]));
        
        // Create a prefix sum array to store cumulative tile counts
        int[] prefixSum = new int[n];
        
        // Fill the prefix sum array
        for (int i = 0; i < n; i++) {
            int tileCount = tiles[i][1] - tiles[i][0] + 1;
            prefixSum[i] = (i == 0 ? tileCount : tileCount + prefixSum[i - 1]);
        }
        
        // Variable to store the maximum number of covered white tiles
        int maxCovered = 0;
        
        // Initialize the second pointer (end of the sliding window)
        int j = 0;
        
        // Iterate through each tile segment as the starting position of the carpet
        for (int i = 0; i < n; i++) {
            // Determine the carpet's starting and ending positions
            int start = tiles[i][0];
            int end = start + carpetLen - 1;
            
            // Expand j as far as possible while staying within the carpet's range
            while (j < n && tiles[j][1] < end) {
                j++;
            }
            
            // Compute the fully covered tiles using the prefix sum array
            int covered = sumOfTiles(prefixSum, i, j - 1);
            
            // Compute partially covered tiles in the last segment, if applicable
            if (j < n && tiles[j][0] <= end) {
                covered += (end - tiles[j][0] + 1);
            }
            
            // Update the maximum covered tiles found so far
            maxCovered = Math.max(maxCovered, covered);
        }
        
        // Return the maximum number of white tiles covered by the carpet
        return maxCovered;
    }
}

3. Maximum White Tiles Covered by a Carpet solution in Python Try on Compiler 
from bisect import bisect_right

class Solution:
    def maximumWhiteTiles(self, tiles, carpetLen):
        
        # Sort tiles based on their starting position
        tiles.sort()

        # Create a prefix sum array to store the total tile count up to each index
        prefixSum = []
        total = 0

        for l, r in tiles:
            total += (r - l + 1)
            prefixSum.append(total)

        # Variable to keep track of the maximum number of tiles covered
        maxCovered = 0
        j = 0

        # Iterate through each tile segment to consider it as a carpet start position
        for i, (start, _) in enumerate(tiles):
            # Compute the ending position of the carpet
            end = start + carpetLen - 1

            # Move the second pointer j to find the furthest tile still within carpet reach
            while j < len(tiles) and tiles[j][1] < end:
                j += 1

            # Compute the total covered tiles
            covered = prefixSum[j - 1] - (prefixSum[i - 1] if i > 0 else 0)

            # If the last segment is partially covered, add only the covered part
            if j < len(tiles) and tiles[j][0] <= end:
                covered += (end - tiles[j][0] + 1)

            # Update the maximum tiles covered if the current coverage is greater
            maxCovered = max(maxCovered, covered)

        # Return the maximum number of white tiles that can be covered
        return maxCovered

4. Maximum White Tiles Covered by a Carpet solution in Javascript Try on Compiler 
var maximumWhiteTiles = function(tiles, carpetLen) {
    
    // Sort tiles based on their starting position
    tiles.sort((a, b) => a[0] - b[0]);

    // Create a prefix sum array to store the total tile count up to each index
    let prefixSum = [];
    let total = 0;

    for (let [l, r] of tiles) {
        total += (r - l + 1);
        prefixSum.push(total);
    }

    // Variable to keep track of the maximum number of tiles covered
    let maxCovered = 0;
    let j = 0;

    // Iterate through each tile segment to consider it as a carpet start position
    for (let i = 0; i < tiles.length; i++) {
        let start = tiles[i][0];
        let end = start + carpetLen - 1;

        // Expand j to the furthest segment within carpet reach
        while (j < tiles.length && tiles[j][1] < end) {
            j++;
        }

        // Compute the total covered tiles
        let covered = prefixSum[j - 1] - (i > 0 ? prefixSum[i - 1] : 0);

        // If the last segment is partially covered, add only the covered part
        if (j < tiles.length && tiles[j][0] <= end) {
            covered += (end - tiles[j][0] + 1);
        }

        // Update the maximum tiles covered if the current coverage is greater
        maxCovered = Math.max(maxCovered, covered);
    }

    // Return the maximum number of white tiles that can be covered
    return maxCovered;
};

Maximum White Tiles Covered by a Carpet Complexity Analysis (two pointers)

Time Complexity: O(n log n)

Step 1: Sorting the Tiles → O(n log n)

  • Sorting the tiles array based on their starting position takes O(n log n) time.
  • Since sorting dominates the complexity, this is the most expensive step.

Step 2: Building the Prefix Sum Array → O(n)

  • We iterate over the tiles array once to compute the cumulative prefix sum, which takes O(n) time.

Step 3: Sliding Window (Two-Pointer Approach) → O(n)

  • The i-pointer iterates through all n tiles.
  • The j-pointer only moves forward, never backward.
  • Since both pointers traverse at most n elements in total, this step runs in O(n) time.

Final Complexity: O(n log n)

  • Sorting is O(n log n) and dominates the other O(n) operations.
  • Thus, the overall time complexity is O(n log n).

Space Complexity: O(n)

  1. Auxiliary Space Complexity: O(n)
    The algorithm uses a few integer variables. The extra space used is O(n) for the prefixSum vector.
    Therefore, the auxiliary space complexity is O(n).
  2. Total Space Complexity: O(n)
    The total space complexity of the approach is O(n), accounting for the input storage of the tiles array and the additional prefixSum array.
    Therefore, the total space complexity is O(n).

Similar Problems

Many array problems on Leetcode can be efficiently solved using techniques like Binary Search, Greedy, Sliding Window, Sorting, and Prefix Sum. Sorting often helps in structuring the data for optimized searching, while Binary Search is useful for problems where we need to find an optimal value within a range. The Sliding Window technique is great for handling subarray problems efficiently, especially when dealing with constraints on sum or length. Prefix Sum is particularly helpful when we need to compute cumulative values quickly, reducing the need for repeated calculations. In many optimization problems, a Greedy approach helps in making local decisions that lead to a globally optimal solution. Combining these techniques strategically allows us to solve complex array problems efficiently.

Now we have successfully tackled this problem, let's try these similar problems.

1. Maximum Number of Vowels in a Substring of Given Length

Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.

2. Successful Pairs of Spells and Potions

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

3. Maximum Matching of Players With Trainers

You are given a 0-indexed integer array players, where players[i] represents the ability of the ith player. You are also given a 0-indexed integer array trainers, where trainers[j] represents the training capacity of the jth trainer.

The ith player can match with the jth trainer if the player's ability is less than or equal to the trainer's training capacity. Additionally, the ith player can be matched with at most one trainer, and the jth trainer can be matched with at most one player.

Return the maximum number of matchings between players and trainers that satisfy these conditions

💡
Showcase your skills by joining LearnYard Technologies FZ-LLC as a Technical Content Writer. Apply now and inspire the next generation of learners—fill out the form: https://forms.gle/CGDsbGkcapSfvXKM8