MediumDynamic ProgrammingUpdated Sep 2026

790. Domino and Tromino Tiling

Asked at Goldman Sachs

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Dynamic Programming

Companies

1

Problem

You are tiling a board that is 2 rows tall and n columns wide. You have two kinds of tiles: a domino, which covers a 2 x 1 rectangle (two squares), and a tromino, which is an L-shape covering three squares. You may rotate either tile in any direction.

Count how many different ways you can cover the whole board with these tiles, with no gaps and no overlaps. Two tilings count as different if there is at least one pair of touching squares where one tiling covers both squares with a single tile and the other tiling does not.

Because the count can get huge, return it modulo 10^9 + 7.

Tiles and the board

2 x 3 board01201??????Every cell must be covered by exactly one tiledomino = 2 squares (2x1 or 1x2)tromino = 3 squares in an L shaperotations are allowed
A 2 x n board must be fully covered by 2x1 dominoes and L-shaped trominoes, which may be rotated.

Constraints

  • ●1 <= n <= 1000
  • ●Return the answer modulo 10^9 + 7

Examples

Example 1
Inputn = 3
Output5
WhyA 2 x 3 board can be covered in exactly 5 distinct ways: three dominoes standing up, one horizontal domino pair plus one more, and several arrangements that use an L-shaped tromino.
Example 2
Inputn = 1
Output1
WhyA 2 x 1 board is just one vertical domino. There is no other option, so the answer is 1.

Asked At

1 companies
CompanyDifficulty
Goldman SachsMediumView all Goldman Sachs questions →

How to Think About It

1

With dominoes only, the answer is Fibonacci. Trominoes add tilings where the right edge is jagged, so you need to track more than "fully tiled up to column i".

2

Two-state DP: full[i] = ways to completely tile the first i columns; part[i] = ways to tile the first i columns plus one extra cell sticking out in column i + 1 (either top or bottom — symmetric, so count one side and double it).

3

Transitions: full[i] = full[i-1] + full[i-2] + 2 * part[i-2] and part[i] = part[i-1] + full[i-1].

4

These collapse into the well-known recurrence dp[i] = 2 * dp[i-1] + dp[i-3], with dp[0] = 1, dp[1] = 1, dp[2] = 2.

5

Check: dp[3] = 2 * 2 + 1 = 5, which matches the five tilings of a 2x3 board.

Optimal Approach

Step 1: Handle small n: dp[0] = 1, dp[1] = 1, dp[2] = 2.
Step 2: For i from 3 to n: dp[i] = (2 * dp[i-1] + dp[i-3]) % MOD.
Step 3: Return dp[n].

Time: O(n). Space: O(1) if you keep only the last three values.

DP recurrence dp[i] = 2*dp[i-1] + dp[i-3]

dp11251101234dp[0]=1, dp[1]=1, dp[2]=2, then dp[3] = 2*2 + 1 = 5dp[i] = (2*dp[i-1] + dp[i-3]) % MODdp[3] = 2*2 + 1 = 5dp[4] = 2*5 + 2 = 12? no, 2*5+2=12
Each new column either extends the previous tiling or pairs with a jagged edge two columns back.
ComplexityTime O(n)Space O(1)We loop once from 3 to n, and each step only needs the previous three values.

What Trips People Up in Real Interviews

1

Using Fibonacci. That ignores trominoes entirely.

2

Stating 2 * dp[i-1] + dp[i-3] with no derivation. Show the full/partial state transitions and then simplify — interviewers want to see where it comes from.

3

Forgetting the modulo or applying it only at the end, which overflows in fixed-width languages.

4

Wrong base cases. dp[0] = 1 (the empty tiling) matters for the recurrence.

Solution Code

O(n) time
def numTilings(n):
    MOD = 10**9 + 7
    dp = [1, 1, 2]
    if n < 3:
        return dp[n]
    for i in range(3, n + 1):
        dp.append((2 * dp[i - 1] + dp[i - 3]) % MOD)
    return dp[n]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Domino and Tromino Tiling problem?

Domino and Tromino Tiling asks how many ways you can tile a `2 x n` board using 2x1 dominoes and L-shaped trominoes, modulo `10^9 + 7`. It is a DP problem where the challenge is setting up states correctly — the L-shapes create partially filled columns that plain Fibonacci-style tiling does not have.

How do you solve Domino and Tromino Tiling?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Domino and Tromino Tiling?

Domino and Tromino Tiling is asked at Goldman Sachs. It is a medium difficulty problem.

What are common mistakes on Domino and Tromino Tiling?
  • Using Fibonacci. That ignores trominoes entirely.
  • Stating `2 * dp[i-1] + dp[i-3]` with no derivation. Show the full/partial state transitions and then simplify — interviewers want to see where it comes from.
  • Forgetting the modulo or applying it only at the end, which overflows in fixed-width languages.
  • Wrong base cases. `dp[0] = 1` (the empty tiling) matters for the recurrence.