Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A tiling can advance with a fully covered frontier or with one cell missing at its right edge. The two possible missing-cell orientations are symmetric, so one gap state is enough. Tracking this frontier shape avoids enumerating complete tilings.

Approach

Memoize solve(i, previous_full), where i is the number of columns reached and the flag distinguishes a full frontier from a frontier with one missing cell.
From a full frontier, place a vertical domino to advance one column, two horizontal dominoes to advance two, or an L-tromino to reach a gap state two columns ahead. The last choice has two orientations, giving its factor of two.
From a gap frontier, either close the gap with a tromino across the next column or extend the gap with a horizontal domino. These lead to the full and gap states one column ahead.
Count one only when exactly n columns are reached with a full frontier; overshoots and unfinished gaps contribute zero. Return the full-frontier count from zero, modulo 10^9 + 7. The reference solutions apply that modulus after computing the exact count.

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 10**9 + 7

        @cache
        def solve(i, previous_full):
            if i > n: return 0
            if i == n:
                if previous_full: return 1
                return 0
            
            if not previous_full: return solve(i + 1, True) + solve(i + 1, False)
            return solve(i + 1, True) + solve(i + 2, True) + 2 * solve(i + 2, False)
        
        return solve(0, True) % MOD

Complexity analysis

Let n be the board width. There are O(n) memoized (index, previousFull) states and O(n) recursion depth. In a unit-cost arithmetic model, time and auxiliary space are O(n); accounting for exact integers growing to Theta(n) bits before the final modulus, both implementations use O(n^2) bit-operation time and O(n^2) bits of cached-integer space. These bounds assume recursion completes: allowed large inputs can exceed Python's default recursion limit unless the runner raises it.