Problem
You have a grid with n rows and 3 columns. You need to paint each cell with one of three colors: Red, Yellow, or Green. No two adjacent cells (sharing an edge — up, down, left, right) can have the same color.
Return the number of ways to paint the grid, modulo 10^9 + 7.
Input: n = 1
Output: 12
Input: n = 2
Output: 54
Input: n = 5000
Output: 30228214
Intuition
Starting simple — what's actually going on?
Let's forget the whole grid for a moment and just think about one row. A single row has 3 cells, and each cell gets a color: Red (R), Yellow (Y), or Green (G). The only rule within a row is that neighbors can't share a color.
How many ways can we color one row? Let's list them all:
RYR RYG RGR RGY
YRY YRG YGR YGY
GRY GRG GYR GYG
That's 12 patterns. But look more closely — they naturally fall into two families:
Family 1 — "ABA" patterns (two colors, ends match):
RYR RGR YRY YGY GRG GYG → 6 patterns
Family 2 — "ABC" patterns (all three colors different):
RYG RGY YRG YGR GRY GYR → 6 patterns
This split is the entire key to the problem. Every valid row is either ABA or ABC. No exceptions.
Why these two families matter
Here's the insight: we don't actually care which specific colors are in a row. We only care whether the row uses the ABA or ABC pattern. Why? Because every ABA row behaves identically when we ask "how many valid next rows can follow?" — and every ABC row also behaves identically.
This means instead of tracking 12 different row states, we only need to track 2 numbers: how many ABA rows and how many ABC rows we have at each level.
Building row by row — the transitions
Now the real question: if we know the pattern of the current row, how many valid patterns can the next row have?
Remember, the next row must satisfy two rules:
- No two horizontally adjacent cells share a color (within the row)
- No cell shares a color with the cell directly above it (between rows)
Let's work this out by hand.
From an ABC row (say R, Y, G):
We need the next row where position 1 ≠ R, position 2 ≠ Y, position 3 ≠ G, and no two adjacent cells in the new row share a color.
Let's enumerate systematically:
Position 1 can be: Y or G (not R)
If pos1 = Y:
pos2 can be: R or G (not Y from above, not Y from left)
If pos2 = R:
pos3 can be: Y (not G from above, not R from left) → YRY ✓ (ABA)
If pos2 = G:
pos3 can be: R or Y (not G from above, not G from left)
→ YGR ✓ (ABC)
→ YGY ✓ (ABA)
If pos1 = G:
pos2 can be: R (not Y from above, not G from left)
If pos2 = R:
pos3 can be: Y (not G from above, not R from left) → GRY ✓ (ABC)
Results from ABC: YRY, YGR, YGY, GRY → 2 ABA + 2 ABC
From an ABA row (say R, Y, R):
Same process — position 1 ≠ R, position 2 ≠ Y, position 3 ≠ R:
Position 1 can be: Y or G (not R)
If pos1 = Y:
pos2 can be: R or G (not Y from above, not Y from left)
If pos2 = R:
pos3 can be: Y or G (not R from above, not R from left)
→ YRY ✓ (ABA)
→ YRG ✓ (ABC)
If pos2 = G:
pos3 can be: Y (not R from above, not G from left) → YGY ✓ (ABA)
If pos1 = G:
pos2 can be: R (not Y from above, not G from left)
If pos2 = R:
pos3 can be: Y or G (not R from above, not R from left)
→ GRY ✓ (ABC)
→ GRG ✓ (ABA)
Results from ABA: YRY, YRG, YGY, GRY, GRG → 3 ABA + 2 ABC
The recurrence
Now we have our transition rules:
| Current row | → Next ABA | → Next ABC |
|---|---|---|
| ABC | 2 | 2 |
| ABA | 3 | 2 |
This gives us two simple recurrences:
aba(n) = 3 × aba(n-1) + 2 × abc(n-1)
abc(n) = 2 × aba(n-1) + 2 × abc(n-1)
Starting with aba(1) = 6 and abc(1) = 6.
The answer for any n is aba(n) + abc(n).
Verifying with n = 2
aba(2) = 3 × 6 + 2 × 6 = 18 + 12 = 30
abc(2) = 2 × 6 + 2 × 6 = 12 + 12 = 24
Total = 30 + 24 = 54 ✓
That matches the expected output.
Why this is O(n) and not O(3^n)
Without this observation, you'd need to try every possible coloring for every row and check validity — exponential time. But by recognizing that all ABA rows behave the same and all ABC rows behave the same, we collapsed the state space from 12 row patterns down to 2 counters. Each step is just two multiplications and additions. That's the power of finding the right abstraction for your DP state.
Solution
function numOfWays(n) {
const MOD = 1e9 + 7;
// aba = count of rows using ABA pattern (two colors)
// abc = count of rows using ABC pattern (three colors)
let aba = 6;
let abc = 6;
for (let i = 2; i <= n; i++) {
const newAba = (3 * aba + 2 * abc) % MOD;
const newAbc = (2 * aba + 2 * abc) % MOD;
aba = newAba;
abc = newAbc;
}
return (aba + abc) % MOD;
}Walking through n = 5
Row 1: aba = 6, abc = 6 → total = 12
Row 2: aba = 30, abc = 24 → total = 54
Row 3: aba = 138, abc = 108 → total = 246
Row 4: aba = 630, abc = 492 → total = 1122
Row 5: aba = 2874, abc = 2244 → total = 5118
Each step is constant work — just arithmetic on two numbers.
Why we need modular arithmetic
For large n (up to 5000), the counts grow astronomically. Without the modulo, aba and abc would overflow any number type. JavaScript handles big integers natively, but using % MOD at each step keeps numbers manageable and matches the problem's requirement.
One subtle point: we apply % MOD after each multiplication and addition, not just at the end. This prevents intermediate values from getting too large during computation.
Complexity
- Time: O(n) — single loop from 2 to n with constant work per step
- Space: O(1) — only two variables tracked at any time
Key Takeaway
When a DP problem has too many states, look for symmetry to collapse them. Here, 12 distinct row colorings collapse into just 2 categories because all rows of the same pattern family have identical transition behavior. The moment you spot that ABA and ABC rows are interchangeable within their families, the problem transforms from "scary combinatorics" into "two-variable recurrence."