Jobs

Interviews

Discussions

Domino and Tromino Tiling

Medium

Amazon

10 views

Topics:

Dynamic Programming

You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.

Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 10<sup>9</sup> + 7.

In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.

Example 1:

Input: n = 3 Output: 5 Explanation: The five different ways are shown above.

Example 2:

Input: n = 1 Output: 1

Constraints:

1 <= n <= 1000

Domino and Tromino Tiling

Medium

Amazon

10 views

Topics:

Dynamic Programming

You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.

Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 10<sup>9</sup> + 7.

Example 1:

Input: n = 3 Output: 5 Explanation: The five different ways are shown above.

Example 2:

Input: n = 1 Output: 1

Constraints:

1 <= n <= 1000

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 is the maximum possible value of `n`? Are we expected to handle very large inputs?
Is `n` guaranteed to be non-negative? What should I return if n is 0?
Could you please clarify what is meant by 'completely covered cells' in the context of determining distinct tilings? Is it simply a cell occupied by any tile?
Are there any restrictions on the input data type of `n`, or can I assume it's always an integer?
Are there specific error conditions I should handle, or can I assume the input will always be a valid integer?

Brute Force Solution

Approach

For the domino and tromino tiling problem, the brute force approach means we try to fill a grid of a given length with tiles by trying all possible placements. It's like physically experimenting with the tiles to see all the ways they can fit.

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

First, consider the very first spot in the grid and try placing a domino tile either horizontally or vertically.
Next, also consider placing a tromino tile in all four possible orientations in that first spot.
For each of these initial placements, look at the next available empty spot in the grid and again try all possible domino and tromino tile placements in that spot.
Keep repeating this process of trying all possible tile placements at each available empty spot until the entire grid is filled.
Each time you find a way to completely fill the grid, count it as a valid tiling.
Once you have tried all possible placement combinations, the total number of valid tilings represents the final answer. Make sure to take into account that the total number of tilings can be a very large number, so handle this number accordingly.

Code Implementation

def domino_and_tromino_tiling_brute_force(grid_length):
    total_tilings = 0
    modulo = 10**9 + 7

    def solve(current_length):
        nonlocal total_tilings

        if current_length == grid_length:
            # Found a valid tiling, increment the count
            total_tilings = (total_tilings + 1) % modulo
            return

        if current_length > grid_length:
            return

        # Try placing a vertical domino
        solve(current_length + 1)

        # Try placing a horizontal domino
        solve(current_length + 2)

        # Try placing trominos in all four orientations
        # These cover the cases where there are L-shaped placements
        solve(current_length + 2)

        solve(current_length + 3)
        solve(current_length + 3)
        solve(current_length + 3)

    solve(0)
    return total_tilings

Big(O) Analysis

Time Complexity

O(6^n) – The brute force approach explores all possible combinations of placing dominoes and trominoes to tile a 2 x n board. At each position, there are up to 6 choices: a horizontal domino, a vertical domino, or one of the four possible tromino orientations. Because we are considering each possibility at each position, and for each position we continue to the next, we create a decision tree. The depth of the tree corresponds to the length of the board, n, with approximately 6 choices at each level. Therefore, the total number of possibilities that need to be tried scales exponentially with the board length n, resulting in a time complexity of O(6^n).

Space Complexity

O(N) – The brute force approach explores all possible placements of dominoes and trominoes through recursion. Each placement leads to a new recursive call, and in the worst case, the depth of this recursion could be proportional to the length of the grid, N. This recursive call stack consumes memory, storing function call information, including intermediate grid states and loop variables, potentially reaching a maximum depth of N. Therefore, the auxiliary space used by the recursion stack grows linearly with the grid length N, resulting in a space complexity of O(N).

Optimal Solution

Approach

This problem is about figuring out the best way to cover a board using dominoes (two squares) and trominoes (three squares). The most efficient way is to break down the problem into smaller, repeatable steps by figuring out how many ways you can cover the board for each length.

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

Consider how a board of length N can be covered by building on solutions for shorter boards.
There are a few base cases to handle directly: How many ways to cover boards of length 1, 2, and 3. These are the foundation for longer boards.
For a board of length N, recognize that the last piece placed can either be a vertical domino, a horizontal domino pair, or one of two kinds of trominoes.
If the last piece placed is a vertical domino, then the number of ways to cover the rest of the board is the same as the number of ways to cover a board of length N-1.
If the last pieces placed are a horizontal domino pair, then the number of ways to cover the rest of the board is the same as the number of ways to cover a board of length N-2.
If the last piece placed is a tromino, there are two possible orientations. These trominoes each cover the last three squares in slightly different ways. Consider the two types of Tromino configurations and for each type add the number of ways to cover the remainder of the board.
Add up all the possible ways based on the different ways the last tile could have been placed. Remember that you are not counting actual placements, you are counting *ways* to place tiles.
Since the answer can be a very large number, take the result modulo a certain value (like 10^9 + 7) to prevent overflow.

Code Implementation

def domino_and_tromino_tiling(board_length):
    modulo = 10**9 + 7

    # Handle base cases for boards of length 1, 2, and 3.
    if board_length <= 2:
        if board_length == 1:
            return 1
        return board_length

    number_of_ways = [0] * (board_length + 1)
    number_of_ways[0] = 1
    number_of_ways[1] = 1
    number_of_ways[2] = 2

    # Maintain counts of partial tromino coverings.
    partial_tromino_coverings = [0] * (board_length + 1)
    partial_tromino_coverings[0] = 0
    partial_tromino_coverings[1] = 0
    partial_tromino_coverings[2] = 2

    for i in range(3, board_length + 1):
        # Vertical domino from i-1 or horizontal domino pair from i-2.
        number_of_ways[i] = (number_of_ways[i - 1] + number_of_ways[i - 2]) % modulo

        # Add the ways trominoes cover, trominoes contribute 2*ways[i-3].
        number_of_ways[i] = (number_of_ways[i] + 2 * number_of_ways[i - 3]) % modulo

    return number_of_ways[board_length]

Big(O) Analysis

Time Complexity

O(n) – The solution utilizes dynamic programming to calculate the number of ways to tile a board of length n. It iterates from 1 to n, calculating the number of ways to tile boards of increasing lengths. For each length i, the calculation involves a constant number of operations (addition and modulo). Therefore, the time complexity is directly proportional to the input size n, resulting in O(n).

Space Complexity

O(N) – The algorithm, as described, calculates the number of ways to tile the board using dynamic programming. It implicitly requires storing the number of ways to tile boards of length 1, 2, 3, up to N. This is typically done using an array or a similar data structure of size N to store intermediate results, specifically the number of ways to tile a board of length i for all i from 1 to N. Thus, the auxiliary space is proportional to the input N, where N is the length of the board. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
n = 0	Return 1, as there's one way to tile an empty board (do nothing).
n = 1	Return 1, as a single domino can be placed vertically to fill the 2x1 board.
n = 2	Return 2, as two vertical dominoes or two horizontal dominoes can tile the 2x2 board.
Large n leading to integer overflow	Apply the modulo operator (10^9 + 7) after each calculation to prevent integer overflow.
Very large n (e.g., n > 10^6)	Ensure the solution's time complexity is O(n) or better, such as using dynamic programming or a matrix exponentiation approach to avoid timeouts.
Negative n	Return 0, since tiling a board with negative length is not possible.
All tilings are Tromino tilings	The DP solution will still consider all possibilities and correctly count such scenarios.
Edge cases in the recurrence relation calculation (e.g., indexing at n-1, n-2, n-3)	Initialize the base cases of the DP table (for n=0, n=1, n=2, n=3) to avoid out-of-bounds errors or incorrect computations.

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 is the maximum possible value of `n`? Are we expected to handle very large inputs?
Is `n` guaranteed to be non-negative? What should I return if n is 0?
Could you please clarify what is meant by 'completely covered cells' in the context of determining distinct tilings? Is it simply a cell occupied by any tile?
Are there any restrictions on the input data type of `n`, or can I assume it's always an integer?
Are there specific error conditions I should handle, or can I assume the input will always be a valid integer?

Brute Force Solution

Approach

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

First, consider the very first spot in the grid and try placing a domino tile either horizontally or vertically.
Next, also consider placing a tromino tile in all four possible orientations in that first spot.
For each of these initial placements, look at the next available empty spot in the grid and again try all possible domino and tromino tile placements in that spot.
Keep repeating this process of trying all possible tile placements at each available empty spot until the entire grid is filled.
Each time you find a way to completely fill the grid, count it as a valid tiling.
Once you have tried all possible placement combinations, the total number of valid tilings represents the final answer. Make sure to take into account that the total number of tilings can be a very large number, so handle this number accordingly.

Code Implementation

def domino_and_tromino_tiling_brute_force(grid_length):
    total_tilings = 0
    modulo = 10**9 + 7

    def solve(current_length):
        nonlocal total_tilings

        if current_length == grid_length:
            # Found a valid tiling, increment the count
            total_tilings = (total_tilings + 1) % modulo
            return

        if current_length > grid_length:
            return

        # Try placing a vertical domino
        solve(current_length + 1)

        # Try placing a horizontal domino
        solve(current_length + 2)

        # Try placing trominos in all four orientations
        # These cover the cases where there are L-shaped placements
        solve(current_length + 2)

        solve(current_length + 3)
        solve(current_length + 3)
        solve(current_length + 3)

    solve(0)
    return total_tilings

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Consider how a board of length N can be covered by building on solutions for shorter boards.
There are a few base cases to handle directly: How many ways to cover boards of length 1, 2, and 3. These are the foundation for longer boards.
For a board of length N, recognize that the last piece placed can either be a vertical domino, a horizontal domino pair, or one of two kinds of trominoes.
If the last piece placed is a vertical domino, then the number of ways to cover the rest of the board is the same as the number of ways to cover a board of length N-1.
If the last pieces placed are a horizontal domino pair, then the number of ways to cover the rest of the board is the same as the number of ways to cover a board of length N-2.
If the last piece placed is a tromino, there are two possible orientations. These trominoes each cover the last three squares in slightly different ways. Consider the two types of Tromino configurations and for each type add the number of ways to cover the remainder of the board.
Add up all the possible ways based on the different ways the last tile could have been placed. Remember that you are not counting actual placements, you are counting *ways* to place tiles.
Since the answer can be a very large number, take the result modulo a certain value (like 10^9 + 7) to prevent overflow.

Code Implementation

def domino_and_tromino_tiling(board_length):
    modulo = 10**9 + 7

    # Handle base cases for boards of length 1, 2, and 3.
    if board_length <= 2:
        if board_length == 1:
            return 1
        return board_length

    number_of_ways = [0] * (board_length + 1)
    number_of_ways[0] = 1
    number_of_ways[1] = 1
    number_of_ways[2] = 2

    # Maintain counts of partial tromino coverings.
    partial_tromino_coverings = [0] * (board_length + 1)
    partial_tromino_coverings[0] = 0
    partial_tromino_coverings[1] = 0
    partial_tromino_coverings[2] = 2

    for i in range(3, board_length + 1):
        # Vertical domino from i-1 or horizontal domino pair from i-2.
        number_of_ways[i] = (number_of_ways[i - 1] + number_of_ways[i - 2]) % modulo

        # Add the ways trominoes cover, trominoes contribute 2*ways[i-3].
        number_of_ways[i] = (number_of_ways[i] + 2 * number_of_ways[i - 3]) % modulo

    return number_of_ways[board_length]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 0	Return 1, as there's one way to tile an empty board (do nothing).
n = 1	Return 1, as a single domino can be placed vertically to fill the 2x1 board.
n = 2	Return 2, as two vertical dominoes or two horizontal dominoes can tile the 2x2 board.
Large n leading to integer overflow	Apply the modulo operator (10^9 + 7) after each calculation to prevent integer overflow.
Very large n (e.g., n > 10^6)	Ensure the solution's time complexity is O(n) or better, such as using dynamic programming or a matrix exponentiation approach to avoid timeouts.
Negative n	Return 0, since tiling a board with negative length is not possible.
All tilings are Tromino tilings	The DP solution will still consider all possibilities and correctly count such scenarios.
Edge cases in the recurrence relation calculation (e.g., indexing at n-1, n-2, n-3)	Initialize the base cases of the DP table (for n=0, n=1, n=2, n=3) to avoid out-of-bounds errors or incorrect computations.