{ }SolveLogs
⌕
Home / Dynamic Programming / #790
LeetCode #790 Medium

Domino and Tromino Tiling

Domino and Tromino Tiling is LeetCode 790 (Medium). You have a 2 × n board and an unlimited supply of two pieces: a 2 × 1 domino and an L-shaped tromino that covers three cells. Both pieces may be rotated. Return the number of ways to cover every cell exactly once, modulo 10⁹ + 7.

  • Two tilings are different if some pair of neighbouring cells is covered by a single piece in one tiling but not in the other.
  • n goes up to 1000, so the count is far too large to build tilings one by one.
Constraints
  • 1 <= n <= 1000
  • Return the answer modulo 10⁹ + 7.
dynamic-programming
Open on LeetCode ↗
02

Intuition

Build the board from left to right and watch its right edge. With dominoes alone the edge is always flat. A tromino changes that: it can leave the last column with one cell covered and one empty.

So keep two counts for every width i:

  • full[i]: tilings of a 2 × i board with a flat right edge.
  • part[i]: tilings where column i has only its top cell covered. The version with only the bottom cell is its mirror image, so it has the same count.

Every tiling has one piece covering its last cell, and removing that piece leaves a smaller board of one of these two shapes. Adding up the choices for that last piece gives each count from smaller ones.

How to spot this pattern

Counting the ways to tile a narrow strip is dynamic programming over the strip's length. When some piece can leave a jagged boundary, add one table per boundary shape; the same idea scales up to tiling a 3 × n or 4 × n board.

03

Approach

Try it first

Before reading on: draw a 2 × 3 board and find all five tilings by hand. Then put one tromino at the left end of a long board and sketch the edge it leaves. Which counts would let you finish that board? Aim for O(n).

Two ways to solve it

Two tables: flat and ragged edgeBest
Time O(n)Space O(n)

Count boards with a flat right edge and boards with one stray cell.

  • Derivable: each term comes from one possible last piece.
  • Checkable: small widths are easy to verify by drawing.

The answer to give when you have to explain it.

Solution & demo ↓
One recurrence: f(n) = 2f(n−1) + f(n−3)
Time O(n)Space O(n)

One table and one line in the loop.

  • Short: seeds 1, 1, 2, then a single update.
  • Watch out: it is hard to justify without the two tables behind it.

Pick it once you know where it comes from.

Code ↓

Both run in O(n). The two-table version is the one you can build from scratch in an interview, so the steps, code and live demo follow it; the shorter recurrence is derived from it after the demo.

1

Seed widths 0 and 1

Set full[0] = 1 and full[1] = 1, and leave part[0] and part[1] at 0. A width-0 board has one tiling, placing nothing, and a single column fits only an upright domino. Starting from width 0 means no special case for small n.

2

Count boards with a flat edge

full[i] = full[i-1] + full[i-2] + 2 * part[i-1], sorted by the piece covering the bottom-right cell:

  • an upright domino, on top of a full board of width i-1;
  • a flat domino, which forces a second flat domino above it, on a full board of width i-2;
  • a tromino, which completes a ragged board of width i-1 whose stray cell is on the top or the bottom, hence the 2.
3

Count boards with a ragged edge

part[i] = part[i-1] + full[i-2], sorted by the piece covering the top cell of column i:

  • a flat domino across the top of columns i-1 and i, on a ragged board of width i-1 with its stray cell at the bottom;
  • a tromino filling column i-1 and the top of column i, on a full board of width i-2.
4

Take the remainder inside the loop

Apply % MOD to both entries as they are computed, then return full[n]. The counts roughly double with each column, so a 64-bit integer overflows long before width 1000.

04

Domino and Tromino Tiling solution in Python | C++ | Java

▶1class Solution:
▶2 def numTilings(self, n: int) -> int:
▶3 MOD = 10**9 + 7
▶4 full = [0] * (n + 1)
▶5 part = [0] * (n + 1)
▶6 full[0] = full[1] = 1
▶7 for i in range(2, n + 1):
▶8 full[i] = (full[i - 1] + full[i - 2] + 2 * part[i - 1]) % MOD
▶9 part[i] = (part[i - 1] + full[i - 2]) % MOD
▶10 return full[n]
width0123full11part001full 01full 1width 0 and 1: one way each
full 01the empty board
full 11one upright domino
part 0, part 10no board can end that way
Two tables, both indexed by board width. full counts boards where every cell is covered. part counts boards that are covered except the last column has only its top cell filled, the ragged shape a tromino leaves behind. A width-0 board has one tiling (place nothing), a width-1 board has one (an upright domino), and no board of width 0 or 1 can end in that ragged shape.
width0123full112part001full 1+1full 0+02 × part 1=2full 2width 2 fully covered: 2 ways
full 221 + 1 + 2 × 0
Look at the piece that covers the last cell of the bottom row. It is an upright domino on a full width-1 board (1), or a pair of flat dominoes on a full width-0 board (1), or a tromino that fills a ragged width-1 board (0). The ragged edge can stick out at the top or at the bottom, and the two are mirror images with the same count, so that term is doubled: 2.
width0123full112part0010part 1+1full 0=1part 2width 2 with one cell sticking out: 1
part 210 + 1
Now the ragged board: everything covered except the bottom cell of column 2. The piece holding its top cell is either a flat domino laid on a board that is ragged one column earlier, sticking out at the bottom (0), or a tromino laid on a full width-0 board (1). Width 3 will need this count.
width0123full1125part0012full 2+1full 1+22 × part 2=5full 3width 3 fully covered: 5 ways
full 352 + 1 + 2 × 1
Look at the piece that covers the last cell of the bottom row. It is an upright domino on a full width-2 board (2), or a pair of flat dominoes on a full width-1 board (1), or a tromino that fills a ragged width-2 board (1). The ragged edge can stick out at the top or at the bottom, and the two are mirror images with the same count, so that term is doubled: 5.
width0123full1125part00121part 2+1full 1=2part 3width 3 with one cell sticking out: 2
part 321 + 1
Now the ragged board: everything covered except the bottom cell of column 3. The piece holding its top cell is either a flat domino laid on a board that is ragged one column earlier, sticking out at the bottom (1), or a tromino laid on a full width-1 board (1). The answer does not need it, but the loop computes it anyway.
width0123full1125part0012dominoesdominoesdominoestrominoestrominoesanswer: 5
answer5full 3
The answer is 5, and here are all five boards. Three use dominoes only; the last two pair up two trominoes. Leave out the ragged state and the count stops at 3.
05

One recurrence

Write the flat-edge formula for width n and for width n − 1, and subtract:

  • the full terms leave full[n−1] − full[n−3];
  • the part terms leave 2 × (part[n−1] − part[n−2]), and the ragged-edge formula says that difference is full[n−3].

Adding up gives full[n] = 2 × full[n−1] + full[n−3], with full[0] = 1, full[1] = 1, full[2] = 2. For n = 4: 2 × 5 + 1 = 11.

▶1class Solution:
▶2 def numTilings(self, n: int) -> int:
▶3 MOD = 10**9 + 7
▶4 dp = [1, 1, 2] + [0] * n
▶5 for i in range(3, n + 1):
▶6 dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD
▶7 return dp[n]
06

Common pitfalls

Counting full boards only

✗ Wrong
full[i] = full[i - 1] + full[i - 2]
✓ Right
full[i] = full[i - 1] + full[i - 2] + 2 * part[i - 1]

This is the domino-only count, which follows the Fibonacci numbers. For n = 3 it returns 3, but the answer is 5: the two tilings made of two trominoes are never counted.

Counting one tromino orientation

✗ Wrong
full[i] = full[i - 1] + full[i - 2] + part[i - 1]
✓ Right
full[i] = full[i - 1] + full[i - 2] + 2 * part[i - 1]

part only counts boards whose stray cell is on top. The boards with the stray cell at the bottom are just as many, and a tromino completes those too. Without the 2, n = 3 returns 4.

Starting the empty board at 0

✗ Wrong
full[0] = 0
✓ Right
full[0] = 1

Width 2 is built partly from width 0: two flat dominoes on an empty board. With full[0] = 0 that tiling disappears, and n = 2 returns 1 instead of 2.

07

Complexity

Time
O(n)
Space
O(n)
The loop runs once per width and does a constant amount of work. Each step reads only the last two entries of each table, so four rolling variables would bring the space down to O(1).
08

Domino and Tromino Tiling FAQ

Can it be solved faster than O(n)?

Yes. The one-line recurrence f(n) = 2f(n−1) + f(n−3) is linear, so it can be written as a 3 × 3 matrix [[2, 0, 1], [1, 0, 0], [0, 1, 0]] applied to (f(n−1), f(n−2), f(n−3)). Raising that matrix to a power by repeated squaring gives O(log n). With n at most 1000 it is not needed here.

What if only dominoes are allowed?

Then the edge is always flat, part is always 0, and full[i] = full[i−1] + full[i−2]: the Fibonacci numbers, 1, 1, 2, 3, 5, 8 and so on. That is the same count as the number of ways to climb n stairs taking one or two steps at a time.

← Prev · #787
Cheapest Flights Within K Stops
Next · #841 →
Keys and Rooms