Domino and Tromino Tiling — Solution in Python, Java & C++
Domino and Tromino Tiling solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Domino and Tromino Tiling is a medium coding problem on dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have two tile shapes: a 2×1 domino and an L-shaped tromino (three squares). Both may be rotated.
Return the number of ways to tile a 2 × n board, modulo 10^9 + 7. Two tilings differ if some pair of 4-directionally adjacent cells is covered by the same tile in one tiling and not the other.
Example 1
Input: n = 3
Output: 5
Example 2
Input: n = 1
Output: 1
Example 3
Input: n = 4
Output: 11
Constraints
1 <= n <= 1000
Hints for Domino and Tromino Tiling
Hint 1
Work out the first few values by hand: 1, 2, 5, 11, 24, …
Hint 2
The clean recurrence is
f(n) = 2·f(n-1) + f(n-3).Hint 3
Seed it with
f(0) = 1,f(1) = 1andf(2) = 2.
How to solve Domino and Tromino Tiling
Deriving the state machine over partially filled columns leads to a surprisingly compact closed recurrence: f(n) = 2·f(n-1) + f(n-3).
Approach
- Handle
n = 1andn = 2directly. - Set
f[0] = 1,f[1] = 1,f[2] = 2. - For
ifrom 3 ton, computef[i] = (2·f[i-1] + f[i-3]) mod (10^9+7). - Return
f[n].
Why it works
The 2·f(n-1) term covers extending a full tiling with a vertical domino and the mirror-image tromino continuations; the f(n-3) term accounts for the two-tromino block that spans three columns without being decomposable. Working the identity out from the two-state (full / jagged) formulation gives exactly this.
Complexity
- Time —
O(n) - Space —
O(n), reducible to O(1)
Pitfalls
- Forgetting the modulus overflows well before
n = 1000. - Seeding
f[0] = 0breaks the recurrence — the empty board has exactly one tiling. - The naive
f(n) = f(n-1) + f(n-2)(dominoes only) misses every tromino tiling.
Reference solution
Python
def numTilings(n: int) -> int:
MOD = 1000000007
if n == 1:
return 1
if n == 2:
return 2
f = [0] * (n + 1)
f[0], f[1], f[2] = 1, 1, 2
for i in range(3, n + 1):
f[i] = (2 * f[i - 1] + f[i - 3]) % MOD
return f[n]Java
public static int numTilings(int n) {
long MOD = 1000000007L;
if (n == 1) return 1;
if (n == 2) return 2;
long[] f = new long[n + 1];
f[0] = 1; f[1] = 1; f[2] = 2;
for (int i = 3; i <= n; i++) {
f[i] = (2 * f[i - 1] + f[i - 3]) % MOD;
}
return (int) f[n];
}C++
int numTilings(int n) {
const long long MOD = 1000000007LL;
if (n == 1) return 1;
if (n == 2) return 2;
vector<long long> f(n + 1, 0);
f[0] = 1; f[1] = 1; f[2] = 2;
for (int i = 3; i <= n; i++) {
f[i] = (2 * f[i - 1] + f[i - 3]) % MOD;
}
return (int) f[n];
}JavaScript
var numTilings = function(n) {
const MOD = 1000000007;
if (n === 1) return 1;
if (n === 2) return 2;
const f = new Array(n + 1).fill(0);
f[0] = 1; f[1] = 1; f[2] = 2;
for (let i = 3; i <= n; i++) {
f[i] = (2 * f[i - 1] + f[i - 3]) % MOD;
}
return f[n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming