Jobs

Interviews

Discussions

Maximum White Tiles Covered by a Carpet

Medium

Asked by:

15 views

Topics:

ArraysSliding WindowsGreedy Algorithms

You are given a 2D integer array tiles where tiles[i] = [l_i, r_i] represents that every tile j in the range l_i <= j <= r_i 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 * 10⁴
tiles[i].length == 2
1 <= l_i <= r_i <= 10⁹
1 <= carpetLen <= 10⁹
The tiles are non-overlapping.

Try coding it in LeetCode

Maximum White Tiles Covered by a Carpet

Medium

Asked by:

15 views

Topics:

ArraysSliding WindowsGreedy Algorithms

You are given a 2D integer array tiles where tiles[i] = [l_i, r_i] represents that every tile j in the range l_i <= j <= r_i 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 * 10⁴
tiles[i].length == 2
1 <= l_i <= r_i <= 10⁹
1 <= carpetLen <= 10⁹
The tiles are non-overlapping.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `tiles` array and the `carpetLen`? Also, what are the maximum and minimum values for `tiles[i][0]` and `tiles[i][1]`?
Can the `tiles` array be empty? What should I return in that case?
Are the tiles guaranteed to be sorted by their starting position `tiles[i][0]`? If not, should I sort them first?
Can the tile ranges overlap? If so, how should I handle overlapping tiles when calculating the covered area?
If no tiles are covered by the carpet (e.g., carpetLen is zero or all tiles start after where the carpet can reach), what should I return?

Brute Force Solution

Approach

The brute force approach to this problem is all about trying every single possible placement of the carpet. We will check the number of white tiles covered for each of these placements. Then, we simply pick the carpet placement that covers the most white tiles.

Here's how the algorithm would work step-by-step:

Imagine placing the left edge of the carpet at the very beginning of the first tile.
Calculate how many white tiles are covered by the carpet in this position.
Now, shift the carpet slightly to the right, placing the left edge just after the beginning of the first tile.
Again, calculate the number of white tiles covered in this new position.
Continue shifting the carpet to the right, incrementing the position little by little and calculating the covered tiles each time.
Eventually, you'll have the carpet's left edge at the beginning of the second tile, then just after it, and so on.
Keep doing this until the right edge of the carpet reaches the end of the last tile.
Compare the number of tiles covered for all of these different carpet positions.
The position that gives you the maximum number of covered white tiles is your answer.

Code Implementation

def maximum_white_tiles_covered_brute_force(tiles, carpet_length):
    maximum_covered_tiles = 0
    number_of_tiles = len(tiles)

    # Iterate through all possible starting positions of the carpet.
    for carpet_start_index in range(number_of_tiles):
        carpet_start_position = tiles[carpet_start_index][0]

        # Consider all possible start positions between tiles.
        while carpet_start_position <= tiles[-1][1]:
            covered_tiles = 0

            # Iterate through all tiles and check how many are covered.
            for tile_start, tile_end in tiles:

                # Calculate the overlap between the carpet and the current tile.
                overlap_start = max(carpet_start_position, tile_start)
                overlap_end = min(carpet_start_position + carpet_length, tile_end)

                # If there is a positive overlap, add it to the count.
                overlap = max(0, overlap_end - overlap_start)
                covered_tiles += overlap

            # Update the maximum number of covered tiles.
            maximum_covered_tiles = max(maximum_covered_tiles, covered_tiles)

            # Move carpet one position to the right
            carpet_start_position += 1

    return maximum_covered_tiles

Big(O) Analysis

Time Complexity

O(n*w) – The described brute force approach iterates through each possible starting position of the carpet. In the worst case, we iterate through nearly every position within the range of the tiles array, which can be considered 'n' positions, where n is related to the length of the input tiles. For each of these positions, we calculate the number of white tiles covered by the carpet of width 'w', requiring us to potentially iterate through the tiles covered by the carpet. Therefore, the time complexity is approximately O(n*w) where n is the number of possible carpet starting positions and w is the carpet width, representing the tiles covered by the carpet in each position.

Space Complexity

O(1) – The brute force approach iterates through possible carpet placements, calculating covered tiles for each. It does not involve creation of any auxiliary data structures such as lists, hash maps, or recursion. The number of variables used (e.g., to store the current carpet position and the maximum covered tiles found so far) remains constant irrespective of the number of tiles, which we can denote as N. Thus, the space complexity is O(1).

Optimal Solution

Approach

The core idea is to efficiently determine the maximum tiles covered by the carpet by sliding it across the tiles. Instead of exhaustively checking every possible placement, we leverage a sliding window technique combined with precomputed sums to find the optimal position.

Here's how the algorithm would work step-by-step:

First, sort the tile segments by their start positions to make processing easier.
Create a list of numbers where each number is how long each tile segment is; this will let you quickly find totals for any set of tiles.
Imagine the carpet starting at the beginning of the first tile; keep track of the total tiles covered by the carpet as you move.
Slide the carpet to the right, considering each tile's start position as a potential starting point for the carpet.
While sliding the carpet, calculate how many white tiles are covered by the carpet in its current position by considering the start and end of current tile segment.
Keep track of the maximum number of white tiles covered seen so far as the carpet moves.
After considering all possible carpet starting positions, the maximum number of white tiles covered that you've tracked is the answer.

Code Implementation

def maximum_white_tiles(tiles, carpet_length):
    tiles.sort()
    
tile_lengths = [tile[1] - tile[0] + 1 for tile in tiles]

    max_covered = 0
    window_start = 0
    current_covered = 0

    for window_end in range(len(tiles)):
        current_covered += tile_lengths[window_end]

        # This loop maintains the sliding window within carpet_length.
        while tiles[window_end][1] - tiles[window_start][0] + 1 > carpet_length:
            current_covered -= tile_lengths[window_start]
            window_start += 1

        # Need to recalc the covered tiles within the carpet length
        covered_by_carpet = current_covered
        left_over_space = carpet_length - (tiles[window_end][1] - tiles[window_start][0] + 1)

        if left_over_space < 0:
            covered_by_carpet = current_covered + left_over_space

        #Keep track of maximum tiles covered
        max_covered = max(max_covered, covered_by_carpet)

    return max_covered

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this solution is the initial sorting of the tile segments, which takes O(n log n) time, where n is the number of tile segments. The subsequent sliding window process iterates through the sorted tile segments once. Calculating the covered tiles within the sliding window involves constant-time operations for each tile segment, resulting in O(n) time. Therefore, the overall time complexity is dominated by the sorting step, leading to O(n log n).

Space Complexity

O(N) – The algorithm creates a list to store the length of each tile segment. The size of this list is directly proportional to the number of tile segments, denoted as N. Therefore, the auxiliary space used by the algorithm scales linearly with the input size. Other variables used are constant space and do not affect the asymptotic space complexity. So, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty tiles array	Return 0 immediately as there are no tiles to cover.
Carpet length is 0	Return 0 immediately as no tiles can be covered with a carpet of length 0.
Carpet length is larger than the range of all tiles	Return the sum of the lengths of all tiles, since the carpet can cover everything.
Tiles array has only one tile	Return the length of the single tile, or the carpet length if it's smaller.
Tiles are very sparse (large gaps between them)	Sliding window approach will handle large gaps correctly, potentially skipping many iterations.
Tiles are clustered together (minimal gaps)	Sliding window will still work efficiently as the covered tiles will increase mostly linearly with the carpet length.
Large tile start and end values leading to integer overflow in calculations	Use long data type to store tile start and end values, and intermediate calculations, preventing overflow issues.
Tiles are not sorted by starting position	Sort the tiles array based on their starting positions before applying the sliding window algorithm.

Empty tiles array

How to Handle:

Return 0 immediately as there are no tiles to cover.

Carpet length is 0

How to Handle:

Return 0 immediately as no tiles can be covered with a carpet of length 0.

Carpet length is larger than the range of all tiles

How to Handle:

Return the sum of the lengths of all tiles, since the carpet can cover everything.

Tiles array has only one tile

How to Handle:

Return the length of the single tile, or the carpet length if it's smaller.

Tiles are very sparse (large gaps between them)

How to Handle:

Sliding window approach will handle large gaps correctly, potentially skipping many iterations.

Tiles are clustered together (minimal gaps)

How to Handle:

Sliding window will still work efficiently as the covered tiles will increase mostly linearly with the carpet length.

Large tile start and end values leading to integer overflow in calculations

How to Handle:

Use long data type to store tile start and end values, and intermediate calculations, preventing overflow issues.

Tiles are not sorted by starting position

How to Handle:

Sort the tiles array based on their starting positions before applying the sliding window algorithm.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `tiles` array and the `carpetLen`? Also, what are the maximum and minimum values for `tiles[i][0]` and `tiles[i][1]`?
Can the `tiles` array be empty? What should I return in that case?
Are the tiles guaranteed to be sorted by their starting position `tiles[i][0]`? If not, should I sort them first?
Can the tile ranges overlap? If so, how should I handle overlapping tiles when calculating the covered area?
If no tiles are covered by the carpet (e.g., carpetLen is zero or all tiles start after where the carpet can reach), what should I return?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine placing the left edge of the carpet at the very beginning of the first tile.
Calculate how many white tiles are covered by the carpet in this position.
Now, shift the carpet slightly to the right, placing the left edge just after the beginning of the first tile.
Again, calculate the number of white tiles covered in this new position.
Continue shifting the carpet to the right, incrementing the position little by little and calculating the covered tiles each time.
Eventually, you'll have the carpet's left edge at the beginning of the second tile, then just after it, and so on.
Keep doing this until the right edge of the carpet reaches the end of the last tile.
Compare the number of tiles covered for all of these different carpet positions.
The position that gives you the maximum number of covered white tiles is your answer.

Code Implementation

def maximum_white_tiles_covered_brute_force(tiles, carpet_length):
    maximum_covered_tiles = 0
    number_of_tiles = len(tiles)

    # Iterate through all possible starting positions of the carpet.
    for carpet_start_index in range(number_of_tiles):
        carpet_start_position = tiles[carpet_start_index][0]

        # Consider all possible start positions between tiles.
        while carpet_start_position <= tiles[-1][1]:
            covered_tiles = 0

            # Iterate through all tiles and check how many are covered.
            for tile_start, tile_end in tiles:

                # Calculate the overlap between the carpet and the current tile.
                overlap_start = max(carpet_start_position, tile_start)
                overlap_end = min(carpet_start_position + carpet_length, tile_end)

                # If there is a positive overlap, add it to the count.
                overlap = max(0, overlap_end - overlap_start)
                covered_tiles += overlap

            # Update the maximum number of covered tiles.
            maximum_covered_tiles = max(maximum_covered_tiles, covered_tiles)

            # Move carpet one position to the right
            carpet_start_position += 1

    return maximum_covered_tiles

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, sort the tile segments by their start positions to make processing easier.
Create a list of numbers where each number is how long each tile segment is; this will let you quickly find totals for any set of tiles.
Imagine the carpet starting at the beginning of the first tile; keep track of the total tiles covered by the carpet as you move.
Slide the carpet to the right, considering each tile's start position as a potential starting point for the carpet.
While sliding the carpet, calculate how many white tiles are covered by the carpet in its current position by considering the start and end of current tile segment.
Keep track of the maximum number of white tiles covered seen so far as the carpet moves.
After considering all possible carpet starting positions, the maximum number of white tiles covered that you've tracked is the answer.

Code Implementation

def maximum_white_tiles(tiles, carpet_length):
    tiles.sort()
    
tile_lengths = [tile[1] - tile[0] + 1 for tile in tiles]

    max_covered = 0
    window_start = 0
    current_covered = 0

    for window_end in range(len(tiles)):
        current_covered += tile_lengths[window_end]

        # This loop maintains the sliding window within carpet_length.
        while tiles[window_end][1] - tiles[window_start][0] + 1 > carpet_length:
            current_covered -= tile_lengths[window_start]
            window_start += 1

        # Need to recalc the covered tiles within the carpet length
        covered_by_carpet = current_covered
        left_over_space = carpet_length - (tiles[window_end][1] - tiles[window_start][0] + 1)

        if left_over_space < 0:
            covered_by_carpet = current_covered + left_over_space

        #Keep track of maximum tiles covered
        max_covered = max(max_covered, covered_by_carpet)

    return max_covered

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty tiles array	Return 0 immediately as there are no tiles to cover.
Carpet length is 0	Return 0 immediately as no tiles can be covered with a carpet of length 0.
Carpet length is larger than the range of all tiles	Return the sum of the lengths of all tiles, since the carpet can cover everything.
Tiles array has only one tile	Return the length of the single tile, or the carpet length if it's smaller.
Tiles are very sparse (large gaps between them)	Sliding window approach will handle large gaps correctly, potentially skipping many iterations.
Tiles are clustered together (minimal gaps)	Sliding window will still work efficiently as the covered tiles will increase mostly linearly with the carpet length.
Large tile start and end values leading to integer overflow in calculations	Use long data type to store tile start and end values, and intermediate calculations, preventing overflow issues.
Tiles are not sorted by starting position	Sort the tiles array based on their starting positions before applying the sliding window algorithm.

Empty tiles array

How to Handle:

Return 0 immediately as there are no tiles to cover.

Carpet length is 0

How to Handle:

Return 0 immediately as no tiles can be covered with a carpet of length 0.

Carpet length is larger than the range of all tiles

How to Handle:

Return the sum of the lengths of all tiles, since the carpet can cover everything.

Tiles array has only one tile

How to Handle:

Return the length of the single tile, or the carpet length if it's smaller.

Tiles are very sparse (large gaps between them)

How to Handle:

Sliding window approach will handle large gaps correctly, potentially skipping many iterations.

Tiles are clustered together (minimal gaps)

How to Handle:

Sliding window will still work efficiently as the covered tiles will increase mostly linearly with the carpet length.

Large tile start and end values leading to integer overflow in calculations

How to Handle:

Use long data type to store tile start and end values, and intermediate calculations, preventing overflow issues.

Tiles are not sorted by starting position

How to Handle:

Sort the tiles array based on their starting positions before applying the sliding window algorithm.