Domino and Tromino Tiling - Solution & Explanation
Problem Statement
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 109 + 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 show above.
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 1000
Approach Overview
Problem Overview: Given a 2 x n board, count the number of ways to completely tile it using dominoes (2x1 or 1x2) and L-shaped trominoes. The challenge is handling partial shapes created by tromino placements and counting all valid tilings efficiently.
Approach 1: Dynamic Programming Recurrence (O(n) time, O(1) space)
This problem becomes manageable once you observe how the board grows from smaller widths. Let dp[i] represent the number of ways to tile a 2 x i board. Domino placements extend the board by one column, while tromino placements create configurations that connect across multiple columns. Careful enumeration of these transitions leads to the recurrence dp[i] = 2 * dp[i-1] + dp[i-3]. The intuition: one vertical domino extends dp[i-1], horizontal domino pairs or mirrored tromino shapes contribute additional combinations. Iterate from 1..n while storing only the last three states, reducing memory to constant space. This technique is a classic use of dynamic programming where each state builds directly from smaller solved subproblems.
Approach 2: Matrix Exponentiation (O(log n) time, O(1) space)
The recurrence dp[i] = 2*dp[i-1] + dp[i-3] is linear, which means it can be expressed as a matrix transition. By representing the state vector as [dp[i], dp[i-1], dp[i-2]], you can construct a fixed 3x3 transformation matrix that advances the sequence by one step. Raising this matrix to the (n-2) power using fast exponentiation computes the result in logarithmic time. Each multiplication combines previous tiling counts according to the recurrence relation. This approach relies on matrix exponentiation to accelerate linear recurrences and is useful when n becomes extremely large.
Recommended for interviews: The dynamic programming recurrence is what most interviewers expect. It demonstrates that you can analyze tile placements, derive a recurrence, and implement an efficient O(n) solution with constant memory. Matrix exponentiation is rarely required during interviews but shows deeper understanding of linear recurrences and optimization techniques often discussed in advanced dynamic programming problems.
Approach 1: Dynamic Programming Approach
This problem can be solved using dynamic programming by considering the number of ways to tile smaller sections of the board and building up to solve for larger sections.
Define a DP array where dp[i] represents the number of ways to tile a 2 x i board.
The recurrence relation involves using domino and tromino tiles:
dp[i] = dp[i-1] + dp[i-2] + 2 * sum[dp[j-2] for j in 3 to i]This relation stems from the ways to construct tilings using the previous configurations.
The above code uses dynamic programming to solve the problem, leveraging an array dp[] to keep track of ways to tile boards of increasing lengths.
Initial conditions are dp[0] = 1, dp[1] = 1, and dp[2] = 2. The recurrence relationship derives from placing tiles in ways that affect the size n.
Complexity
Time Complexity: O(n).
Space Complexity: O(n).
Approach 2: Matrix Exponentiation Approach
This solution uses matrix exponentiation to derive the result by considering the recurrence relation characteristic equation derived earlier. This approach is efficient for large n due to the optimization from reducing the problem to matrix multiplications.
The Matrix Exponentiation approach arranges the problem in terms of a transform matrix based on the transition relations derived from examining the problem.
The matrix is exponentiated using fast exponentiation (squaring technique) to efficiently compute powers.
Complexity
Time Complexity: O(log n).
Space Complexity: O(1).
Approach 3: Dynamic Programming
First, we need to understand the problem. The problem is essentially asking us to find the number of ways to tile a 2 times n board, where each square on the board can only be covered by one tile.
There are two types of tiles: 2 x 1 and L shapes, and both types of tiles can be rotated. We denote the rotated tiles as 1 x 2 and L' shapes.
We define f[i][j] to represent the number of ways to tile the first 2 times i board, where j represents the state of the last column. The last column has 4 states:
- The last column is fully covered, denoted as
0 - The last column has only the top square covered, denoted as
1 - The last column has only the bottom square covered, denoted as
2 - The last column is not covered, denoted as
3
The answer is f[n][0]. Initially, f[0][0] = 1 and the rest f[0][j] = 0.
We consider tiling up to the i-th column and look at the state transition equations:
When j = 0, the last column is fully covered. It can be transitioned from the previous column's states 0, 1, 2, 3 by placing the corresponding tiles, i.e., f[i-1][0] with a 1 x 2 tile, f[i-1][1] with an L' tile, f[i-1][2] with an L' tile, or f[i-1][3] with two 2 x 1 tiles. Therefore, f[i][0] = sum_{j=0}^3 f[i-1][j].
When j = 1, the last column has only the top square covered. It can be transitioned from the previous column's states 2, 3 by placing a 2 x 1 tile or an L tile. Therefore, f[i][1] = f[i-1][2] + f[i-1][3].
When j = 2, the last column has only the bottom square covered. It can be transitioned from the previous column's states 1, 3 by placing a 2 x 1 tile or an L' tile. Therefore, f[i][2] = f[i-1][1] + f[i-1][3].
When j = 3, the last column is not covered. It can be transitioned from the previous column's state 0. Therefore, f[i][3] = f[i-1][0].
We can see that the state transition equations only involve the previous column's states, so we can use a rolling array to optimize the space complexity.
Note that the values of the states can be very large, so we need to take modulo 10^9 + 7.
The time complexity is O(n), and the space complexity is O(1). Where n is the number of columns of the board.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n). |
| Matrix Exponentiation Approach | Time Complexity: O(log n). |
| Dynamic Programming | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming Recurrence | O(n) | O(1) | Standard solution for interview settings and typical constraints |
| Matrix Exponentiation | O(log n) | O(1) | Useful when n is extremely large and recurrence can be expressed as matrix transitions |
Video Solution
Tiling Dominoes and Trominoes (Leetcode 790) | Dynamic Programming • WilliamFiset • 47,390 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Domino and Tromino Tiling easy or hard?
Domino and Tromino Tiling Python/Java solution
How to solve Domino and Tromino Tiling in O(n)?
What is the best approach for Domino and Tromino Tiling?
Is Domino and Tromino Tiling asked at Google/Amazon/Meta?
What data structure is used in Domino and Tromino Tiling?
What is the time complexity of Domino and Tromino Tiling?
Ready to solve this problem?
Practice Domino and Tromino Tiling with our built-in code editor and test cases.
Practice on FleetCode