Skip to main content

790. Domino and Tromino Tiling

medium

Count the ways to tile a 2 by n board using 2x1 dominoes and L-shaped trominoes. A classic linear recurrence with a satisfying closed form.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 10^9 + 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.

Constraints

  • 1 <= n <= 1000

Examples

Example 1

Input
n = 3
Output
5

Explanation: The five different ways are show above.

Example 2

Input
n = 1
Output
1

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Define f(n) = full tilings of a 2 x n board. Look at how the rightmost column can be completed.

Hint 2

There are also partial states: one cell of the rightmost column already covered by an overhang from a tromino.

Hint 3

Solving the system gives the elegant recurrence f(n) = 2 * f(n-1) + f(n-3).

Solution approach

Reveal approach

Let f(n) be the count for a full 2 x n board. Analyzing how the rightmost column can be finished yields the linear recurrence f(n) = 2 * f(n-1) + f(n-3). Intuitively the 2 * f(n-1) covers ending in a vertical domino (1 way) or two horizontal dominoes (1 way that ends at column n-1), and f(n-3) accounts for the symmetric pair of tromino-plus-tromino completions that consume the last three columns together. Iterate bottom-up with three rolling variables modulo 10^9 + 7. Base cases f(1) = 1, f(2) = 2, f(3) = 5.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • linear-recurrence

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Domino and Tromino Tiling and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →