DSA problem
Number of Ways to Paint N × 3 Grid
You have a grid with n rows and 3 columns. Each cell must be painted Red, Yellow, or Green such that no two adjacent cells share the same color (horizontally within a row, or vertically between rows). Given an integer n, return the number of ways to paint the grid. Since the answer may be very large, return it modulo 10^9 + 7.
The trick is to classify every valid row into exactly one of two structural categories:
- "ABA" rows (3-color pattern): the first and third cells share the same color, and the middle cell is one of the other two. Example: R-Y-R or G-R-G. There are exactly 6 such row patterns.
- "ABC" rows (2-color pattern in the sense that all three cells are different): all three columns have different colors. Example: R-Y-G. There are exactly 6 such row patterns as well.
Now ask: given a row of type ABA, how many valid rows of each type can follow it directly below? A careful enumeration shows: 3 next-row ABA patterns are compatible, and 2 next-row ABC patterns are compatible. Similarly, after an ABC row: 2 next ABA patterns and 2 next ABC patterns are compatible.
This gives a tiny 2-state linear recurrence — pure 1-D DP. Let aba = number of ways to paint a valid grid of i rows whose last row is ABA-type, and abc analogously. Then:
aba_new = 3 * aba + 2 * abc
abc_new = 2 * aba + 2 * abc
with the base case aba = 6 and abc = 6 (the count of valid 1-row grids of each type). Iterate n - 1 more times and return (aba + abc) mod (10^9 + 7). The whole solution is O(n) time and O(1) space.
Examples
n = 112n = 254n = 500030228214Constraints
- n == the number of rows in the grid
- 1 <= n <= 5000
- Return the answer modulo 10^9 + 7.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.