Number of Ways to Paint N x 3 Grid

Number of Ways to Paint N x 3 Grid looks like a coloring puzzle with a huge search space, but it collapses into a tiny dynamic program: you only ever track two numbers. It teaches how to compress a problem down to its essential states.

The slow way first

The brute force is to try every color for every one of the 3n cells and check the adjacency rule. That is up to 3^(3n) combinations — astronomically slow even for small n.

The question to ask: what actually matters about a row when I paint the row below it? Not the exact colors — only the shape of the row. And there are only two shapes possible.

The idea: only two row shapes exist

Because no two horizontally adjacent cells can match, every valid row is one of exactly two families:

• Two-color (like A B A): the two ends share a color, the middle differs.
• Three-color (like A B C): all three cells differ.

So instead of tracking colorings, track counts: how many valid grids end in a two-color row, and how many end in a three-color row. Each row transitions to the next by fixed multipliers — a two-color row can sit above 3 two-color rows and 2 three-color rows; a three-color row can sit above 2 and 2.

The key insight: the multipliers 3, 2, 2, 2 never change, so we can advance one row at a time with two additions.

Walk through it

Step through the animation. We start with the base counts for a single row (two = 6, three = 6). Each new row applies the multipliers: the two running counts grow, and the total is always their sum. After n rows we return that sum.

Pseudocode

two, three = 6, 6                 # counts for a single row (n = 1)
repeat (n - 1) times:
    new_two   = 3 * two + 2 * three   # ways a row sits above a two-color row
    new_three = 2 * two + 2 * three   # ways a row sits above a three-color row
    two, three = new_two, new_three
return two + three                # total valid colorings of the n-row grid

The Python solution

def num_of_ways(n):
    two, three = 6, 6
    for _ in range(n - 1):
        # each existing row seeds the next row
        new_two = 3 * two + 2 * three
        new_three = 2 * two + 2 * three
        two, three = new_two, new_three
    return two + three

• two and three are the counts of grids ending in a two-color and three-color row; for one row both are 6.
• The loop runs n - 1 times because row 1 is already counted in the starting values.
• new_two = 3 * two + 2 * three — a two-color row can sit above 3 two-color and 2 three-color rows.
• new_three = 2 * two + 2 * three — a three-color row can sit above 2 of each.
• We reassign both counts together so the next iteration builds on the new row.
• The answer is two + three: every valid grid ends in one shape or the other. (Apply % (10**9 + 7) when the problem requires it.)

Complexity

We collapse the entire grid down to two integers and roll them forward, so we use constant extra space and linear time. Recognizing that only the row shape matters is what shrinks the state to two numbers.

When this pattern shows up

Practice