790. Domino and Tromino Tiling

LeetCode ↗

Problem Editor Pattern Idea Example Code Complex

Problem Description

You are given a problem related to tiling a 2 x n board with two types of shapes: a 2 x 1 domino and an L shaped tromino. The shapes can be rotated as needed to fit into the tiling of the board. The task is to find out how many different ways you can completely cover the 2 x n board using these tiles. It's important to note that two tilings are considered different only if there's at least one pair of adjacent cells in the board that is covered in one tiling and not covered in the other. Since the number of ways can be very large, the answer should be returned modulo 10^9 + 7.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dynamic Programming?

This problem maps to Dynamic Programming through a short path in the full flowchart.

Memoized DP over the two row fronts counts tilings by trying every domino and tromino placement at the boundary.

Open in Flowchart

Intuition

To solve this problem, we can use dynamic programming because the problem has an optimal substructure and overlapping subproblems. Each state in our dynamic programming represents the number of ways to tile a board up to positions (i, j), where i is the position on the upper row and j is the position on the lower row.

Starting from a fully untiled board (0, 0), we consider all possible moves we can make with either of our two types of tiles—one that takes us to (i + 1, j + 1) which represents placing a domino tile vertically, to (i + 2, j + 2) representing placing two domino tiles horizontally next to each other, to (i + 1, j + 2) or (i + 2, j + 1) representing placing a tromino tile. Every move is a transition to a new state, and the number of ways to tile the board for that state is the sum of ways of reaching it from all previous states.

The recursion ends when we consider the entire board tiled (i == n and j == n), which is our base case and we return 1 as there is exactly one way to have a whole tiled board from an entirely tiled board—do nothing.

Since there are overlapping subproblems (we could reach a state from different previous moves), memoization via the @lru_cache(None) decorator is used to avoid redundant calculations. Lastly, every addition of ways is done modulo 10^9 + 7 to prevent integer overflow and adhere to the problem constraints of returning the count of ways modulo 10^9 + 7.

Pattern Learn more about Dynamic Programming patterns.

Uses dynamic programmingNew to the pattern? This video builds dynamic programming up from scratch.

New to patterns?Most interview problems reduce to a handful of patterns. This video covers the main eight.

Solution Approach

The solution to this problem makes use of a recursive depth-first search (DFS) approach along with memoization to count the number of ways to tile the 2 x n board. The DFS function dfs(i, j) (named count_ways(first_row, second_row) in the code) is calculating the number of tilings for the board up to the point (i, j), bearing in mind that i and j represent the ending positions on the upper and lower rows, respectively.

The solution uses the @lru_cache(None) decorator to memoize intermediate results. This is because the DFS function will be called many times with the same arguments, and we want to avoid recalculating those results each time. Memoization reduces the running time from exponential to O(n), because only states where the two rows differ by at most one cell are ever reached.

Here is the step-by-step approach:

If either i or j exceeds n, we've gone beyond the board, which means this is not a valid tiling, so return 0.
If i == n and j == n, we succeeded in tiling the entire board and thus return 1.
If i == j, both rows are equally tiled thus far. We can place two horizontal dominoes (one in each row), one vertical domino, or a tromino that covers two cells in one row and one cell in the other. We accordingly call the dfs function for the following possible next steps: dfs(i + 2, j + 2), dfs(i + 1, j + 1), dfs(i + 2, j + 1), and dfs(i + 1, j + 2).
If i > j, the upper row is ahead, so we can only place a domino horizontally on the lower row or a tromino that covers two cells on the lower row and one on the upper. Thus, the new states to go to are dfs(i, j + 2) and dfs(i + 1, j + 2).
If i < j, the lower row is ahead, so we can place a domino horizontally on the upper row to reach dfs(i + 2, j) or place a tromino in a way that covers two cells on the upper row and one on the lower to reach dfs(i + 2, j + 1).

In each of these cases, we add up the counts returned by all possible step(s) taken from the current state, and this sum is then returned modulo 10^9 + 7 as required by the problem statement. This result is then used for further calculations as we backtrack through the recursion.

When the initial call to dfs(0, 0) completes, we have computed the total number of valid tilings for the entire board, and this result is returned as the final answer.

Example Walkthrough

Let's walk through a 2 x 3 board (n = 3) to illustrate the solution approach with the method dfs(i, j) (named count_ways(first_row, second_row) in the code). Here i and j are the number of cells already covered in the upper and lower rows.

Start by calling dfs(0, 0) since no tiles have been placed yet. Because i == j, there are four moves:
- Place two horizontal dominoes, one in each row: dfs(2, 2).
- Place one vertical domino: dfs(1, 1).
- Place a tromino that covers two upper cells and one lower cell: dfs(2, 1).
- Place a tromino that covers one upper cell and two lower cells: dfs(1, 2).
dfs(2, 2): i == j, so try the same four moves.
- dfs(4, 4), dfs(4, 3), and dfs(3, 4) go beyond the board and return 0.
- dfs(3, 3) is a complete tiling and returns 1.
- Result: dfs(2, 2) = 1.
dfs(1, 1): i == j, so try the four moves.
- dfs(3, 3) returns 1 (two horizontal dominoes finish the board).
- dfs(2, 2) returns 1 (already computed in step 2; memoization reuses it).
- dfs(3, 2): the upper row is ahead, so it tries dfs(3, 4) and dfs(4, 4), both beyond the board, and returns 0.
- dfs(2, 3): the lower row is ahead, so it tries dfs(4, 3) and dfs(4, 4), both beyond the board, and returns 0.
- Result: dfs(1, 1) = 1 + 1 + 0 + 0 = 2.
dfs(2, 1): the upper row is ahead (i > j), so there are two moves.
- A horizontal domino on the lower row: dfs(2, 3) returns 0 (from step 3).
- A tromino covering two lower cells and one upper cell: dfs(3, 3) returns 1.
- Result: dfs(2, 1) = 1.
dfs(1, 2): the lower row is ahead (i < j), so there are two moves.
- A horizontal domino on the upper row: dfs(3, 2) returns 0 (from step 3).
- A tromino covering two upper cells and one lower cell: dfs(3, 3) returns 1.
- Result: dfs(1, 2) = 1.
Add up the four branches of dfs(0, 0): 1 + 2 + 1 + 1 = 5, taken modulo 10^9 + 7.

The answer for the 2 x 3 board is 5: three vertical dominoes, one vertical domino followed by two horizontal dominoes, two horizontal dominoes followed by one vertical domino, and two arrangements made of two trominoes.

Solution Implementation

1import sys
2from functools import lru_cache  # Import lru_cache for memoization
3
4class Solution:
5    def numTilings(self, n: int) -> int:
6        # A helper function with memoization to count the number of ways to tile the board.
7        # i represents the tiles placed in the first row, and j represents the tiles in the second row.
8        @lru_cache(None)  # Use lru_cache for memoization to improve performance
9        def count_ways(first_row: int, second_row: int) -> int:
10            # Base case: If we exceed the board size, there's no way to tile.
11            if first_row > n or second_row > n:
12                return 0
13            # Base case: If both rows are completely tiled, we've found one valid tiling.
14            if first_row == n and second_row == n:
15                return 1
16          
17            # Initialization of possible ways to tile.
18            ways = 0 
19            # When both rows have the same number of points covered by tiles.
20            if first_row == second_row:
21                ways = (
22                    count_ways(first_row + 2, second_row + 2) +  # Place two horizontal dominoes, one in each row.
23                    count_ways(first_row + 1, second_row + 1) +  # Place one vertical domino.
24                    count_ways(first_row + 2, second_row + 1) +  # Place a 'L' shaped tromino.
25                    count_ways(first_row + 1, second_row + 2)    # Place an inverted 'L' shaped tromino.
26                )
27            elif first_row > second_row:
28                # If the first row has more tiles than the second row.
29                ways = count_ways(first_row, second_row + 2) + count_ways(first_row + 1, second_row + 2)
30            else:
31                # If the second row has more tiles than the first row.
32                ways = count_ways(first_row + 2, second_row) + count_ways(first_row + 2, second_row + 1)
33
34            # Return the ways modulo MOD, which represents the maximum number of unique tilings.
35            return ways % MOD
36
37        # Define the modulo constant to prevent large number arithmetic issues.
38        MOD = 10**9 + 7
39        # The recursion can go about n calls deep, which can exceed Python's default limit of 1000 for n near 1000.
40        sys.setrecursionlimit(10000)
41        # Call the helper function with the initial states of the board (0 tiles placed).
42        return count_ways(0, 0)
43

1class Solution {
2    public int numTilings(int n) {
3        // Initialize a DP array to store tiling counts for 4 states
4        // f[0]: full covering, f[1]: top row is missing, f[2]: bottom row is missing, f[3]: transitional state (both rows are missing)
5        long[] dp = {1, 0, 0, 0};
6      
7        // Modulo value to prevent overflow
8        int mod = (int) 1e9 + 7;
9      
10        // Iterate over the sequence from 1 to n
11        for (int i = 1; i <= n; ++i) {
12            // Temporary array to hold the new states counts
13            long[] newDp = new long[4];
14          
15            // New full covering can be achieved from any previous state
16            newDp[0] = (dp[0] + dp[1] + dp[2] + dp[3]) % mod;
17          
18            // New top missing can be achieved from state when previously bottom was missing and the transitional state
19            newDp[1] = (dp[2] + dp[3]) % mod;
20          
21            // New bottom missing can be achieved from state when previously top was missing and the transitional state
22            newDp[2] = (dp[1] + dp[3]) % mod;
23          
24            // New transitional state comes solely from previous full covering state
25            newDp[3] = dp[0];
26          
27            // Update the dp array for the next iteration
28            dp = newDp;
29        }
30      
31        // After completing all iterations, the count of fully covered tilings is in dp[0]
32        return (int) dp[0];
33    }
34}
35

1#include <cstring> // For memcpy
2
3class Solution {
4public:
5    // MOD constant to be used for taking the remainder after division.
6    static const int MOD = 1e9 + 7;
7
8    int numTilings(int n) {
9        // An array to hold the number of ways to tile for different subproblems.
10        // f[0]: full cover, f[1]: top row is missing one, f[2]: bottom row is missing one, f[3]: both top and bottom are missing one (L-shape)
11        long tilingWays[4] = {1, 0, 0, 0};
12
13        // Iterate through all subproblem sizes from 1 to n
14        for (int i = 1; i <= n; ++i) {
15            // Temporary array to compute the new number of tiling ways for the current subproblem.
16            long newTilingWays[4] = {0, 0, 0, 0};
17
18            // Full cover is obtained by adding one 2x2 tile or two 2x1 tiles to any of the four previous states.
19            newTilingWays[0] = (tilingWays[0] + tilingWays[1] + tilingWays[2] + tilingWays[3]) % MOD;
20            // Top row missing one can be obtained by adding a 2x1 tile to the previous state of bottom row missing one or both top and bottom missing one.
21            newTilingWays[1] = (tilingWays[2] + tilingWays[3]) % MOD;
22            // Bottom row missing one can be obtained by adding a 2x1 tile to the previous state of top row missing one or both top and bottom missing one.
23            newTilingWays[2] = (tilingWays[1] + tilingWays[3]) % MOD;
24            // Both top and bottom missing one can only be obtained by placing a 2x2 tile in the full cover state.
25            newTilingWays[3] = tilingWays[0];
26
27            // Update tilingWays array with the new computed values.
28            memcpy(tilingWays, newTilingWays, sizeof(newTilingWays));
29        }
30
31        // Return the number of ways to fully cover a 2xN board.
32        return tilingWays[0];
33    }
34};
35

1// MOD constant to be used for taking the remainder after division.
2const MOD: number = 1e9 + 7;
3
4// Calculates the number of ways to tile a 2xN board with dominoes.
5function numTilings(n: number): number {
6    // An array to hold the number of ways to tile for different subproblems:
7    // - tilingWays[0]: full cover,
8    // - tilingWays[1]: top row is missing one,
9    // - tilingWays[2]: bottom row is missing one,
10    // - tilingWays[3]: both top and bottom are missing one (in L-shape).
11    let tilingWays: number[] = [1, 0, 0, 0];
12
13    // Iterate through all subproblem sizes from 1 to n.
14    for (let i = 1; i <= n; ++i) {
15        // Temporary array to compute the new number of tiling ways for the current subproblem.
16        let newTilingWays: number[] = [0, 0, 0, 0];
17
18        // Full cover is obtained by adding one 2x2 tile or two 2x1 tiles to any of the four previous states.
19        newTilingWays[0] = (tilingWays[0] + tilingWays[1] + tilingWays[2] + tilingWays[3]) % MOD;
20        // Top row missing one can be obtained by adding a 2x1 tile to the previous state of bottom row missing one or both top and bottom missing one.
21        newTilingWays[1] = (tilingWays[2] + tilingWays[3]) % MOD;
22        // Bottom row missing one can be obtained by adding a 2x1 tile to the previous state of top row missing one or both top and bottom missing one.
23        newTilingWays[2] = (tilingWays[1] + tilingWays[3]) % MOD;
24        // Both top and bottom missing one can only be obtained by placing a 2x2 tile in the full cover state.
25        newTilingWays[3] = tilingWays[0];
26
27        // Update tilingWays array with the new computed values.
28        tilingWays = [...newTilingWays];
29    }
30
31    // Return the number of ways to fully cover a 2xN board.
32    return tilingWays[0];
33}
34
35// The numTilings function can be exported or used directly, depending on the context of the TypeScript project.
36

Time and Space Complexity

Time Complexity

Every move keeps the two rows within one cell of each other: from a state with i == j the moves lead to states with a difference of 0 or 1, and from a state with a difference of 1 the moves lead back to a difference of 0 or 1 (or past the board). So the only states (i, j) that are ever computed satisfy |i - j| ≤ 1 with 0 ≤ i, j ≤ n, plus a few states just past the board that return 0 immediately. That is O(n) states. Because of memoization, each state is computed once and makes at most 4 recursive calls, so the time complexity is O(n).

Space Complexity

The cache stores one entry per visited state, which is O(n). The recursion depth is also O(n), since every call increases i + j by at least 2 and i + j cannot exceed 2n before the base cases stop the recursion. The depth can reach about n calls, plus the wrapper frames that lru_cache adds in some Python versions, which is why the code raises Python's recursion limit with sys.setrecursionlimit(10000): the default limit of 1000 is not enough for n near 1000.

So the final analysis is:

Time Complexity: O(n)
Space Complexity: O(n), for the memoization cache and the call stack

Pattern Learn more about how to find time and space complexity quickly using problem constraints.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: