Scale Engineer

Domino and Tromino Tiling

Med
#0744Time: O(N) - Each state `f(i)` and `p(i)` for `i` from 1 to `n` is computed once.Space: O(N) - For the memoization arrays and the recursion stack depth.1 company
Patterns
Dynamic Programming
Companies
WinZO

Prompt

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 shown above.

Example 2:

Input: n = 1
Output: 1

 

Constraints:

  • 1 <= n <= 1000

Approaches

4 approaches with complexity analysis and trade-offs.

A brute-force recursive approach would explore every possible way to place tiles, which is highly inefficient. We can significantly improve this by using memoization to store the results of subproblems, which turns the solution into a top-down dynamic programming approach. We define two states: one for a fully tiled 2 x n board and another for a 2 x n board with a single corner cell in the last column left uncovered. By deriving recurrence relations for these states, we can solve the problem recursively while storing intermediate results to avoid redundant calculations.

Algorithm

  1. Define two recursive functions, f(n) and p(n):
    • f(n): returns the number of ways to fully tile a 2 x n board.
    • p(n): returns the number of ways to tile a 2 x n board with one of the corners in column n uncovered (a 'partial' tiling). By symmetry, the number of ways is the same whether the top or bottom corner is uncovered.
  2. Establish the recurrence relations:
    • To get a fully tiled 2 x n board (f(n)):
      • Start with a fully tiled 2 x (n-1) board and add a vertical domino. This gives f(n-1) ways.
      • Start with a fully tiled 2 x (n-2) board and add two horizontal dominoes. This gives f(n-2) ways.
      • Start with a partially tiled 2 x (n-1) board (top corner uncovered) and add an L-tromino to complete the board. This gives p(n-1) ways.
      • Start with a partially tiled 2 x (n-1) board (bottom corner uncovered) and add an L-tromino. This also gives p(n-1) ways.
      • So, f(n) = f(n-1) + f(n-2) + 2 * p(n-1).
    • To get a partially tiled 2 x n board (p(n)):
      • Start with a fully tiled 2 x (n-2) board and add an L-tromino that leaves a corner of column n uncovered. This gives f(n-2) ways.
      • Start with a 2 x (n-1) board with the opposite corner uncovered and add a horizontal domino. This gives p(n-1) ways.
      • So, p(n) = p(n-1) + f(n-2).
  3. Define the base cases:
    • f(0) = 1 (one way to tile a 2x0 board: do nothing).
    • f(1) = 1 (one vertical domino).
    • p(0) = 0, p(1) = 0 (no way to have these partial shapes for n=0 or n=1).
  4. Implement the recursive functions using memoization (e.g., arrays memo_f and memo_p) to store and reuse the results of subproblems, avoiding recomputation. All calculations should be done modulo 10^9 + 7.

Walkthrough

Let f(n) be the number of ways to fully tile a 2 x n board, and p(n) be the number of ways to tile a 2 x (n-1) board plus one cell in column n (creating a shape with a single uncovered cell in the corner of the 2 x n area). By analyzing the ways to place the last tile(s), we can establish recurrence relations.

  • For a fully tiled 2 x n board (f(n)): We can arrive at this state from:

    1. A fully tiled 2 x (n-1) board by adding a vertical domino.
    2. A fully tiled 2 x (n-2) board by adding two horizontal dominoes.
    3. A partially tiled 2 x (n-1) board by adding an L-tromino to fill the remaining shape. Since there are two symmetric partial states (top or bottom corner uncovered), this adds 2 * p(n-1) ways. The recurrence is: f(n) = f(n-1) + f(n-2) + 2 * p(n-1).

  • For a partially tiled 2 x n board (p(n)): We can arrive at this state from:

    1. A fully tiled 2 x (n-2) board by adding an L-tromino.
    2. A partially tiled 2 x (n-1) board (with the opposite corner uncovered) by adding a horizontal domino. The recurrence is: p(n) = p(n-1) + f(n-2).

We use two memoization arrays, memo_f and memo_p, to store the computed values and avoid re-computation. The final answer is f(n).

class Solution {    long MOD = 1_000_000_007;    long[] memo_f;    long[] memo_p;     public int numTilings(int n) {        if (n <= 2) {            return n;        }        memo_f = new long[n + 1];        memo_p = new long[n + 1];        return (int) f(n);    }     // Ways to fully tile a 2 x i board    private long f(int i) {        if (i == 0) return 1;        if (i == 1) return 1;        if (i == 2) return 2;        if (memo_f[i] != 0) return memo_f[i];         memo_f[i] = (f(i - 1) + f(i - 2) + 2 * p(i - 1)) % MOD;        return memo_f[i];    }     // Ways to tile a 2 x (i-1) board with one extra cell in column i    private long p(int i) {        if (i <= 1) return 0;        if (i == 2) return 1;        if (memo_p[i] != 0) return memo_p[i];         memo_p[i] = (p(i - 1) + f(i - 2)) % MOD;        return memo_p[i];    }}

Complexity

Time

O(N) - Each state `f(i)` and `p(i)` for `i` from 1 to `n` is computed once.

Space

O(N) - For the memoization arrays and the recursion stack depth.

Trade-offs

Pros

  • Relatively intuitive to derive from the problem's recursive nature.

  • Correctly solves the problem within the time limits.

Cons

  • May lead to a stack overflow for very large n if the recursion depth limit is exceeded.

  • Generally has higher constant-factor overhead compared to the iterative bottom-up approach due to function calls.

Solutions

class Solution {public  int numTilings(int n) {    long[] f = {1, 0, 0, 0};    int mod = (int)1 e9 + 7;    for (int i = 1; i <= n; ++i) {      long[] g = new long[4];      g[0] = (f[0] + f[1] + f[2] + f[3]) % mod;      g[1] = (f[2] + f[3]) % mod;      g[2] = (f[1] + f[3]) % mod;      g[3] = f[0];      f = g;    }    return (int)f[0];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem