Domino and Tromino Tiling

Medium
576.

Domino and Tromino Tiling

Domino and Tromino Tiling is a medium coding problem on dynamic programming, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var numTilings = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Work out the first few values by hand: 1, 2, 5, 11, 24, …

  2. Hint 2

    The clean recurrence is f(n) = 2·f(n-1) + f(n-3).

  3. Hint 3

    Seed it with f(0) = 1, f(1) = 1 and f(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

  1. Handle n = 1 and n = 2 directly.
  2. Set f[0] = 1, f[1] = 1, f[2] = 2.
  3. For i from 3 to n, compute f[i] = (2·f[i-1] + f[i-3]) mod (10^9+7).
  4. 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] = 0 breaks 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