Domino and Tromino Tiling — InterviewPrepKit

Solving tips

Compute f(1..4)=1,2,5,11 by hand to discover the closed recurrence f(n)=2*f(n-1)+f(n-3), or derive it with full/partial column states.
The tromino leaves a one-cell overhang, so if deriving from scratch track two states: flush edge vs one-cell jut-out.
Reduce modulo 10^9+7 at every step, not just at the end, since f(1000) is enormous.
Target O(n) time, O(1) space with rolling scalars; base f(0)=1 is what makes f(3)=5 come out right.

Problem

You have two tile shapes:

a domino: a 2 × 1 (or 1 × 2) rectangle, and
a tromino: an L-shaped tile covering three cells (a 2 × 2 square with one corner removed).

Both may be rotated. Count the number of ways to completely tile a 2 × n board, leaving no gaps and no overlaps. Because the count grows fast, return it modulo 10^9 + 7.

Examples

n = 1 → 1 — only a single vertical domino fits the 2 × 1 board.
n = 3 → 5 — the five distinct tilings of a 2 × 3 board.
n = 4 → 11.

Constraints

1 <= n <= 1000
Answer is returned modulo 10^9 + 7.

n up to 1000 means an O(n) recurrence is more than enough; the real work is finding the recurrence, because trominoes create partially-filled columns.

Think about it first

Hint 1

Try small cases by hand: `f(1)=1`, `f(2)=2`, `f(3)=5`, `f(4)=11`. The jump from a pure-domino Fibonacci-like count comes from the L-tiles leaving a "staircase" edge.

Hint 2

One clean closed recurrence is `f(n) = 2·f(n-1) + f(n-3)`. Sanity check: `f(4) = 2·5 + 1 = 11`, `f(5) = 2·11 + 2 = 24`. It captures "extend the previous board" plus the new arrangements a tromino pair unlocks.

Hint 3

If you prefer to *derive* rather than memorize, track two states per column: `full[i]` = ways to tile the first `i` columns flush, and `partial[i]` = ways to tile them with exactly one cell of column `i` jutting out. Transitions between `full` and `partial` give the same sequence. Either way, keep the last few values and reduce mod `10^9 + 7`.

TL;DR

Closed recurrence f(n) = 2·f(n-1) + f(n-3) (mod 10^9 + 7), computed with three rolling scalars — O(n) time, O(1) space.

The recurrence

Let f(n) be the number of tilings of a 2 × n board. The standard closed form is:

f(n) = 2 * f(n-1) + f(n-3)      for n >= 3
f(0) = 1,  f(1) = 1,  f(2) = 2

Intuition for the terms: 2·f(n-1) covers either extending an (n-1)-tiling with a vertical domino or the reflected family of arrangements that a tromino opens up at the new column; f(n-3) counts the tilings that finish with the two-tromino block spanning three columns. (A first-principles derivation via two states is given as Approach 4.)

Approach 1 — Brute-force recursion

Transcribe the recurrence with no caching.

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        def f(k: int) -> int:
            if k == 0 or k == 1:
                return 1
            if k == 2:
                return 2
            return (2 * f(k - 1) + f(k - 3)) % MOD
        return f(n)

Complexity: exponential (~O(2^n)) time, O(n) stack.

Why the constraints kill it: each call spawns two more; at n = 1000 the tree is astronomically large, all of it recomputing the same f(k).

Approach 2 — Top-down memoization

The insight: only n + 1 distinct values f(0) … f(n); cache them.

from functools import cache

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        @cache
        def f(k: int) -> int:
            if k == 0 or k == 1:
                return 1
            if k == 2:
                return 2
            return (2 * f(k - 1) + f(k - 3)) % MOD
        return f(n)

Complexity: O(n) time, O(n) space (cache + stack).

Approach 3 — Bottom-up tabulation

The insight: compute f(0) upward so each term’s three dependencies are ready.

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

Walkthrough (n = 4): seeds dp = [1, 1, 2, ?, ?]. dp[3] = 2·dp[2] + dp[0] = 2·2 + 1 = 5. dp[4] = 2·dp[3] + dp[1] = 2·5 + 1 = 11. Return 11. ✓

Complexity: O(n) time, O(n) space.

Approach 4 — Two-state derivation, space-optimized

The insight: to derive the count instead of quoting it, track two ways a prefix of columns can end:

full[i] = tilings of the first i columns with a flush (straight) right edge, and
part[i] = tilings of the first i columns with exactly one cell of column i filled (a one-cell overhang).

Adding tiles at the right edge gives:

full[i] = full[i-1] + full[i-2] + 2 * part[i-1]
part[i] = full[i-2] + part[i-1]
full[0] = 1, full[1] = 1
part[0] = 0, part[1] = 0

full[i-1] caps a flush edge with a vertical domino; full[i-2] caps it with two stacked horizontal dominoes; 2·part[i-1] closes a one-cell overhang with a tromino (two mirror orientations). An overhang at column i is created either by a tromino sitting on a flush edge two columns back (full[i-2]) or by extending an existing overhang with a horizontal domino (part[i-1]). Keeping only the last two values of each state gives O(1) space:

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        if n == 1:
            return 1
        full2, full1 = 1, 1                       # full[i-2], full[i-1]
        part2, part1 = 0, 0                       # part[i-2], part[i-1]
        for _ in range(2, n + 1):
            full0 = (full1 + full2 + 2 * part1) % MOD
            part0 = (full2 + part1) % MOD
            full2, full1 = full1, full0
            part2, part1 = part1, part0
        return full1

Walkthrough (n = 3): start full = (full2, full1) = (1, 1), part = (0, 0).

i=2: full0 = full1 + full2 + 2·part1 = 1 + 1 + 0 = 2; part0 = full2 + part1 = 1 + 0 = 1. Now full = (1, 2), part = (0, 1).
i=3: full0 = 2 + 1 + 2·1 = 5; part0 = 1 + 1 = 2. Now full = (2, 5).

Return full1 = 5. ✓ (And one more step, i=4: full0 = 5 + 2 + 2·2 = 11.)

Complexity: O(n) time, O(1) space. This two-state model produces exactly the same sequence as the closed form f(n) = 2·f(n-1) + f(n-3); use whichever you find easier to reproduce under pressure.

Common pitfalls

Forgetting the modulus. f(1000) is enormous; reduce mod 10^9 + 7 at every step, not just at the end.
Wrong base cases. f(0) = 1 (the empty board has one tiling) is what makes f(3) = 2·2 + 1 = 5 come out right; dropping it breaks the recurrence.
Trusting a hand-rolled two-state model without checking small n. The overhang bookkeeping (which full/part index feeds which transition) is delicate — always verify against f(1..4) = 1, 2, 5, 11 before trusting it.
Ignoring tromino rotations. Each L-tile has four orientations; the 2·part term (two of them at a given edge) is where they enter.

Pattern takeaway

Tiling counts are 1-D DP where the recurrence isn’t obvious from the problem statement — you either discover a closed linear recurrence by computing small cases (1, 2, 5, 11, 24, … → f(n) = 2f(n-1) + f(n-3)) or introduce auxiliary states (full/partial) to make the transition local. The meta-lesson: when tiles leave partially-filled boundaries, add a state per boundary shape; and always validate a guessed recurrence against a handful of brute-forced small answers before trusting it.