Number of Ways to Paint N x 3 Grid: Row State DP

You are given an n x 3 grid. You need to paint each cell with one of three colors (red, yellow, green) such that no two adjacent cells (sharing a horizontal or vertical edge) have the same color. Return the number of ways to paint the grid, modulo 10^9 + 7.

This is LeetCode 1411: Number of Ways to Paint N x 3 Grid, and it is one of the cleanest examples of state-compression DP. Instead of tracking every possible grid configuration, you can reduce the problem to tracking just two numbers per row.

Why this problem matters

At first glance, this problem looks like it could require enumerating all possible colorings of an n x 3 grid. With 3 color choices per cell and 3n cells total, the brute force space is enormous. But the grid is only 3 columns wide, and that narrow width is the key. It means each row has a small, fixed number of valid patterns, and the only constraint between rows is that vertically adjacent cells differ in color.

This "compress the row state" technique appears in many grid DP problems. Whenever the grid has a small fixed width, you can enumerate valid row configurations, figure out which pairs of configurations are compatible between adjacent rows, and then run a simple DP across the rows. The same idea powers problems involving tiling dominoes on a board, placing non-attacking rooks, and filling grids under constraints.

Once you see that row states collapse into just two categories here, the problem becomes almost trivial. That collapse is the real insight.

The key insight

Each row of 3 cells must be painted so that no two horizontally adjacent cells share a color. There are exactly 12 valid patterns for a single row. These 12 patterns fall into two categories:

• 3-color patterns (like R-Y-G): all three colors appear in the row. There are 6 of these, corresponding to the 6 permutations of 3 colors.
• 2-color patterns (like R-Y-R): only two colors appear, with the first and third cells matching. There are also 6 of these (3 choices for the repeated color times 2 choices for the middle color).

Now the critical observation: when you place a new row below an existing one, how many valid followers does each category have? By checking all compatible pairs, you find a clean recurrence:

• Each 3-color row can be followed by 2 three-color rows and 2 two-color rows.
• Each 2-color row can be followed by 2 three-color rows and 3 two-color rows.

So you only need to track two values: the total count of 3-color arrangements and the total count of 2-color arrangements. Each row, you apply the transition and move on.

The solution

def num_of_ways(n: int) -> int:
    MOD = 10**9 + 7
    three = 6
    two = 6

    for _ in range(1, n):
        new_three = (2 * three + 2 * two) % MOD
        new_two = (2 * three + 3 * two) % MOD
        three = new_three
        two = new_two

    return (three + two) % MOD

Let's break this down.

We start with three = 6 and two = 6 because for the first row (n = 1), there are 6 valid 3-color patterns and 6 valid 2-color patterns.

The loop runs from row 2 through row n. At each step, new_three is the number of 3-color arrangements for the current row. Each existing 3-color arrangement from the previous row spawns 2 new 3-color followers, and each existing 2-color arrangement spawns 2 new 3-color followers. That gives 2 * three + 2 * two.

Similarly, new_two counts 2-color arrangements: 2 followers from each 3-color predecessor and 3 followers from each 2-color predecessor, giving 2 * three + 3 * two.

After processing all rows, the answer is three + two, the total count of valid complete grid colorings.

Visual walkthrough

Let's trace through the two pattern types and how they transition row by row. The key is seeing that every valid row fits neatly into one of two buckets, and the transition rules between buckets are constant.

Notice that the recurrence is purely linear. You do not need to store any grid or enumerate any configurations at runtime. The entire problem reduces to iterating two variables n times. This is the payoff of recognizing that row states compress into categories.

Complexity analysis

Time is O(n). You iterate through n rows, doing a constant amount of work per row (two multiplications and two additions). There is no inner loop over columns or patterns.

Space is O(1). You only store two integers (three and two) plus their updated values. No arrays, no matrices, no memoization tables.

The building blocks

1. Row state classification

The technique of enumerating all valid configurations for a fixed-width row and grouping them by structure:

three = 6
two = 6

For a 3-column row with 3 colors and an adjacency constraint, there are exactly 12 valid patterns. Grouping them into "3-color" and "2-color" categories lets you track aggregate counts instead of individual configurations. This classification step is the foundation of any state-compression DP on a grid with small width.

2. Transition recurrence

The pattern of computing next-row counts from current-row counts using fixed coefficients:

new_three = (2 * three + 2 * two) % MOD
new_two = (2 * three + 3 * two) % MOD

This is a linear recurrence, similar in spirit to Fibonacci. You could even express it as matrix exponentiation to solve in O(log n) time, though for the constraint n <= 5000 that is unnecessary. The same recurrence pattern shows up whenever you have a small number of state categories with fixed transition counts between them.

Edge cases

Before submitting, think through these scenarios:

• n = 1: The answer is 12. There are 6 three-color and 6 two-color valid patterns for a single row.
• n = 2: The answer is 54. Each 3-color row has 4 followers and each 2-color row has 5 followers: 6 * 4 + 6 * 5 = 54.
• Large n (n = 5000): The loop runs 4999 times with modular arithmetic. The values stay bounded by 10^9 + 7, so there is no overflow risk in Python.
• Modular arithmetic: Every intermediate result must be taken mod 10^9 + 7. Forgetting the mod on the final sum three + two is a common mistake.

From understanding to recall

You now see how a grid coloring problem with exponential brute-force complexity collapses into a two-variable linear recurrence. The logic is elegant: classify row patterns into two types, count transitions between types, and iterate. The code is six lines long.

But writing those six lines under interview pressure requires you to remember the exact transition coefficients. Is it 2-2-2-3 or 2-3-2-2? Does new_three use 3 * two or 2 * two? These details feel obvious when you are reading an explanation, but they slip away when you are staring at a blank editor.

Spaced repetition closes that gap. You practice deriving the row state categories, computing the transition counts, and writing the recurrence from scratch. After a few sessions spaced over days, the pattern is locked in. You see "paint a grid with adjacency constraints" and the two-state DP template flows out automatically.

Related posts

• Climbing Stairs - The classic introduction to linear recurrence DP, where you track one variable instead of two
• Decode Ways - Another DP problem where you classify the current state and transition with fixed rules
• House Robber - A linear DP that tracks two choices (rob or skip) at each step, similar to tracking two pattern types

CodeBricks breaks Number of Ways to Paint N x 3 Grid into its row state classification and transition recurrence building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a state-compression DP problem shows up in your interview, you do not think about it. You just write it.