Number of Ways to Paint N × 3 Grid

Number of Ways to Paint N × 3 Grid

What is this problem about?

The Number of Ways to Paint N × 3 Grid problem asks you to count the ways to color an N×3 grid with 3 colors such that no two adjacent cells (horizontally or vertically) share the same color. Return the count modulo 10^9+7. This hard DP problem uses the observation that valid row patterns and compatible row pairs can be precomputed.

Why is this asked in interviews?

Intuit and Fortinet ask this because it tests DP with row-pattern transitions. There are only 12 valid color patterns for a row of 3 cells (no two adjacent same color with 3 colors). These 12 patterns fall into two structural types: "ABA" style (3 patterns) and "ABC" style (many more). The dynamic programming interview pattern is demonstrated through pattern-based row DP.

Algorithmic pattern used

Mathematical observation. The 12 valid row patterns split into two types:

• Type 1 (ABA patterns, like 121): 3 valid patterns (choose middle from remaining, then end must equal middle... actually ABA: choose A (3), choose B≠A (2) = 6 ABA patterns).
• Type 2 (ABC patterns, like 123): 3! = 6 ways. Total: 12 patterns.

Transitions: an ABA row can be followed by certain ABA and ABC rows (count = 3 and 6 respectively). Define a[n] = count using ABA patterns, b[n] = count using ABC. Recurrences: a[n] = 3*a[n-1] + 2*b[n-1], b[n] = 2*a[n-1] + 2*b[n-1]. Answer = a[n] + b[n].

Example explanation

n=1: a[1]=6 (ABA patterns), b[1]=6 (ABC patterns). Total=12. n=2: a[2]=36+26=30, b[2]=26+26=24. Total=54. n=3: a[3]=330+224=138, b[3]=230+224=108. Total=246.

Common mistakes candidates make

• Brute-forcing all row patterns for large N.
• Incorrectly counting compatible transitions between rows.
• Not recognizing the two structural types of row patterns.
• Missing the recurrence: ABA followed by different ABA and ABC patterns.

Interview preparation tip

Color grid DP problems with small row widths always benefit from precomputing the transition matrix. With 3 colors and 3 cells, there are only 12 valid patterns — small enough to enumerate manually. The recurrence captures all valid inter-row transitions. Practice similar "color grid with k colors" problems — the same structural decomposition of row patterns and their transitions applies.