LeetCode 790 - Domino and Tromino Tiling

Difficulty: 🟡 Medium
Topics: Dynamic Programming

Solution

Problem Understanding

The problem asks us to compute the number of ways to completely tile a 2 x n board using two types of tiles: a domino (2 x 1) and a tromino shape. A domino covers exactly two adjacent cells either vertically or horizontally, while a tromino covers three connected cells in an L-shape. The tiles may be rotated as needed.

The input is a single integer n representing the width of the board. The output should be the total number of distinct tiling configurations modulo 10^9 + 7. Two tilings are considered different if at least one pair of adjacent squares is covered differently.

Constraints indicate 1 <= n <= 1000, which means the solution must handle relatively large board widths efficiently. A naive brute-force approach that tries all placements recursively would be infeasible because the number of possibilities grows exponentially with n. Edge cases to note include very small boards (n = 1 or n = 2) where only a few placements are possible.

Approaches

A brute-force approach would attempt to recursively place tiles on the board, exploring every valid combination of dominoes and trominoes. While correct, this method is exponential in n and would be far too slow for n up to 1000.

The key observation for an optimal solution is that this problem exhibits overlapping subproblems and optimal substructure, making it ideal for dynamic programming. We define dp[i] as the number of ways to tile a 2 x i board. We must account for two scenarios: completely filled columns and partially filled columns (due to trominoes that leave a single square in the last column uncovered). This leads to a recurrence relation involving dp[i-1], dp[i-2], and an auxiliary array for partial tilings. This transforms the problem from exponential to linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Recursively tries all placements of dominoes and trominoes
Optimal	O(n)	O(n)	Uses dynamic programming with recurrence relations for complete and partial tilings

Algorithm Walkthrough

Initialize a dp array of size n+1 to store the number of ways to fully tile a 2 x i board, and another array dp2 to store the number of ways to partially tile 2 x i leaving one square hanging.
Set base cases: dp[0] = 1 (empty board has one trivial tiling), dp[1] = 1 (one vertical domino), dp[2] = 2 (two vertical dominoes or two horizontal dominoes).
Loop from i = 3 to n. For each i, calculate the number of complete tilings:

Use the recurrence dp[i] = dp[i-1] + dp[i-2] + 2 * dp2[i-1] to account for placing a vertical domino, two horizontal dominoes, or adding trominoes to partial configurations.
Update the partial tilings: dp2[i] = dp2[i-1] + dp[i-2].

Return dp[n] % (10^9 + 7) to handle large numbers.

Why it works: The recurrence correctly counts all configurations by considering all valid ways to extend smaller tilings to a larger board. The partial tiling array ensures trominoes are properly incorporated.

Python Solution

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 10**9 + 7
        if n == 1:
            return 1
        if n == 2:
            return 2
        
        dp = [0] * (n + 1)
        dp2 = [0] * (n + 1)
        
        dp[0], dp[1], dp[2] = 1, 1, 2
        dp2[2] = 1
        
        for i in range(3, n + 1):
            dp[i] = (dp[i-1] + dp[i-2] + 2 * dp2[i-1]) % MOD
            dp2[i] = (dp2[i-1] + dp[i-2]) % MOD
        
        return dp[n]

The implementation initializes the dynamic programming arrays with base cases. The main loop fills dp and dp2 according to the recurrence. We use modulo arithmetic at each step to prevent overflow.

Go Solution

func numTilings(n int) int {
    const MOD = 1000000007
    if n == 1 {
        return 1
    }
    if n == 2 {
        return 2
    }

    dp := make([]int, n+1)
    dp2 := make([]int, n+1)

    dp[0], dp[1], dp[2] = 1, 1, 2
    dp2[2] = 1

    for i := 3; i <= n; i++ {
        dp[i] = (dp[i-1] + dp[i-2] + 2*dp2[i-1]) % MOD
        dp2[i] = (dp2[i-1] + dp[i-2]) % MOD
    }

    return dp[n]
}

In Go, we use slices for dynamic programming arrays and define constants for modulo operations. The logic mirrors the Python implementation.

Worked Examples

Example 1: n = 3

i	dp[i]	dp2[i]	Explanation
0	1	0	empty board
1	1	0	single vertical domino
2	2	1	two vertical dominoes or two horizontal dominoes; one partial tromino
3	5	2	extend previous boards using recurrence

Result: dp[3] = 5

Example 2: n = 1

i	dp[i]	dp2[i]
0	1	0
1	1	0

Result: dp[1] = 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each dp[i] is computed once in a single pass
Space	O(n)	Two arrays of size n+1 are used

We loop once from 3 to n and compute each dp entry in constant time, giving linear time complexity. Two arrays of size n+1 yield linear space complexity.

Test Cases

# Provided examples
assert Solution().numTilings(3) == 5  # small board
assert Solution().numTilings(1) == 1  # minimum board width

# Edge cases
assert Solution().numTilings(2) == 2  # base case with two possibilities
assert Solution().numTilings(4) == 11  # slightly larger board
assert Solution().numTilings(5) == 24  # small arbitrary board
assert Solution().numTilings(1000) >= 0  # stress test for large n, result modulo 1e9+7

Test	Why
n=3	Validates standard small board with multiple tilings
n=1	Validates smallest board
n=2	Validates base case with multiple options
n=4	Tests recurrence logic beyond base cases
n=5	Tests general DP accumulation
n=1000	Tests efficiency and modulo correctness

Edge Cases

The first important edge case is n = 1. The board is too small to fit a tromino, and only a single vertical domino fits. The implementation handles this explicitly with a conditional check.

The second edge case is n = 2. Both dominoes and partial placements must be correctly accounted for. We explicitly initialize dp[2] = 2 and dp2[2] = 1 to capture this scenario.

The third edge case is large n = 1000. Here, integer overflow could occur, and naive recursive approaches fail. The solution uses modulo 10^9 + 7 and dynamic programming, ensuring correct results within constraints.

These edge cases are correctly handled in the implementation and ensure robustness across the full input range.