Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The grid has few rows, so an entire column coloring can be a state. A state must satisfy vertical adjacency internally; two neighboring column states must differ at every row. Once the current column is known, earlier columns impose no additional restrictions.

Approach

Enumerate all base-three masks of m digits and retain only those with unequal neighboring digits. Precompute which ordered pairs of retained masks differ at every position. Count sequences of n compatible columns using DP over the column position and current mask, reducing every transition modulo 10^9 + 7. Python memoizes suffix counts and sums over first-column choices; JavaScript evaluates compatible-state transitions with a table. Finishing all columns contributes one valid coloring, including the single-column case.

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

        valid = dict()
        for key in range(3**m):
            row = []
            mask = key
            for i in range(m):
                row.append(mask % 3)
                mask //= 3
            if not any(row[j] == row[j - 1] for j in range(1, m)):
                valid[key] = row
        
        adjacent = defaultdict(list)
        for mask1, row1 in valid.items():
            for mask2, row2 in valid.items():
                if not any(row1[i] == row2[i] for i in range(m)):
                    adjacent[mask1].append(mask2)
        
        @cache
        def dp(i, mask):
            if i == n: return 1
            count = 0
            for adj in adjacent[mask]: count = (count + dp(i + 1, adj)) % MOD
            return count
        
        res = 0
        for mask in valid: res = (res + dp(1, mask)) % MOD
        return res

Complexity analysis

Let V = 32^(m - 1) be the valid column count and E <= V^2 the compatible ordered-pair count. Time is O(3^mm + V^2*m + nE). Auxiliary space is O(Vm + E + nV), including decoded columns, compatibility lists and all cached/table DP layers. Modulo reduction at every transition keeps counts bounded. Python also has O(n) recursion depth, which can exceed the default recursion limit at the allowed large column counts unless the runner raises it sufficiently; JavaScript fills layers iteratively.