Painting a Grid With Three Different Colors: Column-State DP
You are given an m x n grid. Paint every cell with one of three colors so that no two adjacent cells (horizontally or vertically) share the same color. Return the total number of valid colorings modulo 10^9 + 7.
This is LeetCode 1931: Painting a Grid With Three Different Colors. The constraint that makes it interesting is m is at most 5, while n can be up to 1000. That asymmetry is the key to the whole approach: treat each column as a single "state" and use DP across columns.
The approach: column-state dynamic programming
The brute-force way to color an m x n grid would enumerate 3^(m*n) possibilities, which is completely impractical. But notice the constraint: m is tiny (at most 5). That means the number of valid colorings for a single column is small. For a column of height m, each cell can be one of 3 colors, and adjacent rows must differ. The number of valid column states is at most 3 * 2^(m-1), which is 48 when m = 5.
The core insight is to think column by column. Two adjacent columns are compatible if, for every row, the colors in the left column and the right column are different. You precompute all valid column states, precompute which pairs of states are compatible, and then run DP across the n columns.
Define dp[col][state] as the number of valid colorings of columns 0..col where column col uses a particular state. The recurrence is:
dp[col][state] = sum of dp[col-1][prev] for all prev that are compatible with state.
The base case is dp[0][state] = 1 for every valid state. The answer is the sum of dp[n-1][state] over all valid states.
Since m is at most 5, you can encode each column state as a tuple of m color values (0, 1, 2). Enumerate all 3^m tuples, keep only those where no two adjacent entries match, and you have your state space. For m=5 there are only 48 valid states.
The code
def colorTheGrid(m, n):
MOD = 10 ** 9 + 7
states = []
def gen(col):
if len(col) == m:
states.append(tuple(col))
return
for c in range(3):
if not col or col[-1] != c:
col.append(c)
gen(col)
col.pop()
gen([])
compatible = {s: [] for s in states}
for s1 in states:
for s2 in states:
if all(a != b for a, b in zip(s1, s2)):
compatible[s1].append(s2)
dp = {s: 1 for s in states}
for _ in range(1, n):
new_dp = {}
for s in states:
new_dp[s] = sum(dp[prev] for prev in compatible[s]) % MOD
dp = new_dp
return sum(dp.values()) % MOD
- Generate valid states. The
genfunction recursively builds all column colorings of heightmwhere no two consecutive rows share a color. - Build the compatibility map. For every pair of valid states, check whether they can sit in adjacent columns (no row has the same color in both columns).
- DP across columns. Start with
dp[state] = 1for each state (one column, one way). For each subsequent column, sum up contributions from all compatible predecessors. - Return the total. Sum all values in
dpafter processing allncolumns, modulo10^9 + 7.
Visual walkthrough
The following diagrams walk through the column-state DP approach using a small example: m = 2 rows and n = 3 columns. With 2 rows and 3 colors, there are 6 valid column states. The steps show how to enumerate states, determine valid transitions, trace a concrete transition calculation, and fill in the DP table.
Step 1: Enumerate valid column states
For m=2 rows and 3 colors, there are 6 valid column states. Each state is a tuple of colors for rows 0 and 1, with no two adjacent rows sharing a color.
Step 2: Find valid transitions between column states
From state S0 = (R,G), we can only transition to columns where no row shares the same color. S0 and S1 are invalid because row 0 stays Red. S2, S3, S4, S5 are all valid transitions.
Step 3: Transition detail for dp[1][S2]
To compute dp[1][(G,R)], sum dp[0][prev] for all valid predecessors. (R,G), (R,B), and (B,G) each contribute 1, giving dp[1][(G,R)] = 3.
Step 4: Build the DP table column by column
dp[col][state] = total valid colorings for columns 0..col ending in that state. Each cell sums up dp[col-1][prev] for all valid predecessors. Final answer for m=2, n=3: sum of last column = 54.
The final answer for m = 2, n = 3 is the sum of the last column in the DP table. Each cell in the table represents the number of valid colorings of all columns up to that point, ending in a specific column state.
Complexity analysis
| Metric | Value |
|---|---|
| Time | O(n * S^2) where S = number of valid column states |
| Space | O(S^2) for the compatibility map, O(S) for the DP row |
The number of valid column states S grows as 3 * 2^(m-1). For m = 5, S = 48, so each column transition involves checking up to 48 * 48 = 2304 pairs. With n up to 1000, the total work is roughly 2.3 million operations, which is very fast. You can also precompute the compatibility lists to avoid checking all S^2 pairs every column, reducing the constant factor.
Building blocks
Column-state DP (profile DP)
When one dimension of a grid is small (typically m is at most 5 or 6), you can encode the entire column (or row) as a discrete state and run DP across the other dimension. This collapses a 2D problem into a 1D DP over "profiles." The key is that the number of valid profiles stays manageable even though the grid itself can be very large.
This pattern appears in:
- Domino and Tromino Tiling (LeetCode 790): Tile a 2xN board using dominoes and trominoes. Each column profile is a bitmask of which cells are already covered.
- Number of Ways to Paint N x 3 Grid (LeetCode 1411): A simpler version of this exact problem with
mfixed at 3. The same column-state enumeration and transition logic applies.
Precomputed transition graph
Instead of checking compatibility on the fly, you precompute a graph where nodes are valid states and edges connect compatible state pairs. Then the DP transition at each column is just "sum over neighbors." This turns the problem into a graph traversal combined with DP, and it generalizes to any situation where you have a fixed set of states and a fixed compatibility relation.
This pattern appears in:
- Minimum Cost to Cut a Stick (LeetCode 1547): Precompute which subproblems feed into each other before running DP, so each transition is a simple lookup.
- Strange Printer (LeetCode 664): The DP over intervals uses precomputed transition points to decide where to split, following the same "build the graph, then DP over it" structure.
Edge cases
m = 1, n = 1: The grid is a single cell. The answer is 3, since any of the three colors is valid.
m = 1, any n: With a single row, each column is just one cell. Adjacent cells must differ, so the answer is 3 * 2^(n-1). The DP still works here, but you can also compute it directly.
m = 5, n = 1000: This is the largest input. With 48 states and 1000 columns, the algorithm completes well within time limits. Make sure to apply the modulo at every step to prevent integer overflow in languages with fixed-width integers.
Large n, small m: The time complexity depends far more on n than on m. Even when n = 1000, the bottleneck is the n * S^2 loop, and S never exceeds 48.
From understanding to recall
Column-state DP is one of those patterns that feels confusing the first time you see it, but once you get it, the same template works for a whole family of grid problems. The hard part is not the code itself. It is recognizing that the small dimension should be compressed into a state, and that you should precompute transitions before looping.
The best way to lock this in is to practice it on a few variants: this problem, the N x 3 grid version, and domino tiling. Each one uses the same skeleton (enumerate states, build transition graph, DP across columns) with minor differences in the state encoding and compatibility check. Drilling them with spaced repetition turns the pattern into something you can reproduce from memory, not just something you once read about.
Related posts
- Climbing Stairs - The simplest linear DP problem, and a good foundation before tackling column-state DP
- House Robber - Another DP problem where each position has a "use it or skip it" decision, building toward the transition-graph thinking used here