Tiling 2xN Board With Dominoes
01 · Problem
You have a board with 2 rows and n columns, and an unlimited supply of 1 x 2 domino tiles. Each domino may be placed horizontally (covering two cells in one row) or vertically (covering both cells of one column).
Return the number of distinct ways to cover the whole board with no overlaps and no gaps. Two tilings are different if some cell is covered by a different domino placement. Since the count grows quickly, return it modulo 10^9 + 7.
02 · Examples
n = 1
1
A 2 x 1 board fits exactly one vertical domino.
n = 3
3
The tilings are: three vertical; vertical then a stacked horizontal pair; a stacked horizontal pair then vertical.
n = 4
5
Four vertical, two horizontal pairs, or one horizontal pair in any of three positions with verticals around it: 1 + 1 + 3 = 5.
03 · Constraints
- 011 <= n <= 1000
- 02Each domino covers exactly two adjacent cells
- 03Return the answer modulo 109 + 7
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.