Domino And Tromino Tiling · Interview Problem

Back to problems

Leetcode

Medium

Dynamic Programming

Combinatorics

Arrays

Domino And Tromino Tiling

Count the number of ways to fully tile a $2 \times n$ board using dominoes and trominoes.

Acceptance 0%

Start Practice

Problem Statement

You are given an integer $n$ . Consider a $2 \times n$ board. You may place the following tiles:

A $2 \times 1$ domino, which can be placed vertically.
A $1 \times 2$ domino, which can be placed horizontally.
An L-shaped tromino that covers exactly 3 cells and may be rotated in any direction.

Return the number of ways to completely cover the board with no overlaps and no uncovered cells.

Because the answer can be very large, return it modulo $10^9 + 7$ .

Input Format

A single integer $n$ representing the board width.

Output Format

Return an integer: the number of valid tilings of a $2 \times n$ board modulo $10^9 + 7$ .

Constraints

$1 \le n$
The result should be computed modulo $10^9 + 7$ .
Use an approach that scales to large $n$ rather than brute force enumeration.

Examples

Sample cases returned by the problem API.

Example 1

Input

n = 3

Output

Explanation

There are 5 tilings of a $2 \times 3$ board using the allowed tiles.

Example 2

Input

n = 4

Output

Explanation

There are 11 valid tilings of a $2 \times 4$ board.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress