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 Sam K., 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

More DP 1D practice problems

See all DP 1D problems →