Number of Ways to Paint N x 3 Grid
Understanding the Problem
This could be framed as a backtracking problem that tries every possible coloring. With 3 colors and 3 columns, each row has up to 27 possible colorings, and there are up to 5000 rows, so a naive search over full grids is far too slow.
The constraint is local: a cell cannot match its horizontal neighbor in the same row or its vertical neighbor in the previous row. Since the grid is only 3 columns wide, the number of valid colorings for a single row is small. Once we know which patterns are valid for a row and which pairs of consecutive rows are compatible, the problem reduces to dynamic programming over rows.
Valid row colorings come in two types: patterns where all three cells use different colors (like R-Y-G), and patterns where the first and third cells share a color but the middle differs (like R-Y-R). These two types have different numbers of compatible successors, and that difference is what lets the final solution track only two counts instead of twelve.
Key Constraints:
1 <= n <= 5000. An O(n) or O(n * k) solution with small k handles this easily. There are only 12 valid row patterns, so k = 12.- The grid is always 3 columns wide. This fixed width keeps the number of row patterns small. A grid that was n x m with large m would need a different approach, since the number of row patterns grows exponentially in m.
- The answer is returned modulo 10^9 + 7. The count grows exponentially in n, so it overflows 64-bit integers well before n = 5000, and every intermediate sum and product must be taken modulo 10^9 + 7.
Approach 1: Brute Force (Enumerate All Row States)
Intuition
Enumerate all possible row colorings, keep the ones where no two adjacent cells in the same row share a color, and for each pair of valid rows, check whether they are compatible (no column has the same color in both rows). The DP state is then the current row's coloring pattern, and the transition is determined entirely by this compatibility.
Each cell can be one of 3 colors (0, 1, 2), so a row of 3 cells has 3^3 = 27 possible colorings. After removing rows with adjacent same-color cells, 12 valid patterns remain. We build a compatibility graph between these patterns and run DP row by row.
Algorithm
- Generate all 27 possible row colorings (each cell gets a color from 0 to 2).
- Filter to keep only valid rows where no two adjacent cells share a color. This gives 12 valid patterns.
- For each pair of valid patterns, check if they are compatible (no column has the same color in both rows). Store this in a compatibility list.
- Initialize a DP array where
dp[pattern]= 1 for each valid pattern (one way to paint row 1 with that pattern). - For each subsequent row (2 through n), compute
newDp[pattern]as the sum ofdp[prevPattern]for all compatible previous patterns. - The answer is the sum of all values in the final DP array, modulo 10^9 + 7.
Example Walkthrough
Code
- Time Complexity: O(n * k^2) where k = 12 (number of valid row patterns). Since k is constant, this is effectively O(n).
- Space Complexity: O(k^2) = O(1). The DP array and compatibility list are constant-sized.
This runs fast enough, but it tracks more state than necessary. Every 3-color pattern has the same number of compatible successors, and so does every 2-color pattern. The next approach collapses the 12 states into 2 aggregate counts.
Approach 2: Pattern-Based DP (Optimal)
Intuition
Every valid row coloring falls into one of two categories:
- 3-color pattern (ABC): All three cells use different colors. There are 6 such patterns.
- 2-color pattern (ABA): The first and third cells share a color, with a different middle. There are also 6 such patterns.
By enumeration, a 3-color pattern can be followed by 2 three-color and 2 two-color patterns. A 2-color pattern can be followed by 2 three-color and 3 two-color patterns. So we only need two variables.
Take pattern (0, 1, 2), a 3-color type. The next row needs col1 != 0, col2 != 1, col3 != 2, plus no horizontal adjacency. Enumerating all valid successors gives: (1, 0, 1), (1, 2, 0), (1, 2, 1), (2, 0, 1). That is 2 ABC + 2 ABA.
Take pattern (0, 1, 0), a 2-color type. Next row needs col1 != 0, col2 != 1, col3 != 0. Valid successors: (1, 0, 1), (1, 0, 2), (1, 2, 1), (2, 0, 1), (2, 0, 2). That is 2 ABC + 3 ABA.
Algorithm
- Initialize
threeColor = 6andtwoColor = 6(for the first row). - For each subsequent row (2 through n):
newThreeColor = (2 * threeColor + 2 * twoColor) % MODnewTwoColor = (2 * threeColor + 3 * twoColor) % MOD- Return
(threeColor + twoColor) % MOD.
Example Walkthrough:
Code
- Time Complexity: O(n). A single loop from 1 to n, with O(1) work per iteration.
- Space Complexity: O(1). Only a constant number of variables regardless of n.