Number of Ways to Paint N × 3 Grid
HardPrompt
You have a grid of size n x 3 and you want to paint each cell of the grid with exactly one of the three colors: Red, Yellow, or Green while making sure that no two adjacent cells have the same color (i.e., no two cells that share vertical or horizontal sides have the same color).
Given n the number of rows of the grid, return the number of ways you can paint this grid. As the answer may grow large, the answer must be computed modulo 109 + 7.
Example 1:
Input: n = 1
Output: 12
Explanation: There are 12 possible way to paint the grid as shown.Example 2:
Input: n = 5000
Output: 30228214
Constraints:
n == grid.length1 <= n <= 5000
Approaches
3 approaches with complexity analysis and trade-offs.
This problem has optimal substructure and overlapping subproblems, making it a perfect candidate for dynamic programming. The core idea is that the number of ways to color any given row i depends solely on the valid colorings of the previous row, i-1.
First, we analyze the valid colorings for a single row. A row has 3 cells, and adjacent cells must have different colors. This gives rise to two types of color patterns:
- Two-Color Patterns (ABA type): The first and third cells are the same color, while the middle cell is different (e.g., Red-Yellow-Red). There are
3choices for the first color and2for the second, totaling3 * 2 = 6such patterns. - Three-Color Patterns (ABC type): All three cells have different colors (e.g., Red-Yellow-Green). There are
3 * 2 * 1 = 6such patterns.
For n=1, the total number of ways is 6 + 6 = 12.
Algorithm
- Define two DP arrays,
twoColorandthreeColor, of sizen+1. twoColor[i]will store the number of ways to paint the firstirows with thei-th row having a two-color (ABA) pattern.threeColor[i]will store the number of ways to paint the firstirows with thei-th row having a three-color (ABC) pattern.- Set the base cases for
i=1:twoColor[1] = 6andthreeColor[1] = 6. - Iterate from
i = 2tonand apply the following recurrence relations:twoColor[i] = (3 * twoColor[i-1] + 2 * threeColor[i-1]) % MODthreeColor[i] = (2 * twoColor[i-1] + 2 * threeColor[i-1]) % MOD
- The final answer is the sum of
twoColor[n]andthreeColor[n], moduloMOD.
Walkthrough
We can build a DP solution based on these two pattern types. We'll define DP states to count the number of ways to paint the grid up to row i ending with each pattern type.
Let:
twoColor[i]be the number of ways to paint ani x 3grid where rowihas a two-color (ABA) pattern.threeColor[i]be the number of ways to paint ani x 3grid where rowihas a three-color (ABC) pattern.
We can establish recurrence relations by analyzing how a pattern in row i can follow a pattern in row i-1 without violating the color constraints.
-
Transitions to a two-color pattern in row
i:- From a two-color pattern in row
i-1: There are 3 valid ways. - From a three-color pattern in row
i-1: There are 2 valid ways. - Thus,
twoColor[i] = 3 * twoColor[i-1] + 2 * threeColor[i-1].
- From a two-color pattern in row
-
Transitions to a three-color pattern in row
i:- From a two-color pattern in row
i-1: There are 2 valid ways. - From a three-color pattern in row
i-1: There are 2 valid ways. - Thus,
threeColor[i] = 2 * twoColor[i-1] + 2 * threeColor[i-1].
- From a two-color pattern in row
The implementation involves creating two arrays to store these counts and iterating from i=2 to n to fill them. The final result is the sum of the counts for row n.
class Solution { public int numOfWays(int n) { if (n == 0) { return 0; } long MOD = 1_000_000_007; long[] twoColor = new long[n + 1]; long[] threeColor = new long[n + 1]; // Base case for n = 1 twoColor[1] = 6; threeColor[1] = 6; for (int i = 2; i <= n; i++) { // Ways to form a two-color pattern in row i twoColor[i] = (3 * twoColor[i - 1] + 2 * threeColor[i - 1]) % MOD; // Ways to form a three-color pattern in row i threeColor[i] = (2 * twoColor[i - 1] + 2 * threeColor[i - 1]) % MOD; } return (int) ((twoColor[n] + threeColor[n]) % MOD); }}Complexity
Time
O(n) - We perform a single loop from `i=2` to `n`, with constant time operations inside.
Space
O(n) - We use two arrays of size `n+1` to store the DP states for each row.
Trade-offs
Pros
Conceptually straightforward and easy to follow.
Directly translates the recurrence relation into code.
Cons
Uses linear space, which is not optimal and can be improved.
The previous dynamic programming approach uses O(n) space, but we can notice that the calculation for the number of ways to color row i only requires the results from row i-1. There is no dependency on i-2, i-3, etc. This observation allows us to optimize the space complexity significantly.
Algorithm
- Initialize two variables,
twoColorCount = 6andthreeColorCount = 6, representing the base case forn=1. - If
n=1, return the sum12. - Loop from
i = 2ton. - Inside the loop, use temporary variables to calculate the counts for the current row
ibased on the counts from the previous row (twoColorCountandthreeColorCount).nextTwoColor = (3 * twoColorCount + 2 * threeColorCount) % MODnextThreeColor = (2 * twoColorCount + 2 * threeColorCount) % MOD
- Update the main count variables:
twoColorCount = nextTwoColorandthreeColorCount = nextThreeColor. - After the loop, return
(twoColorCount + threeColorCount) % MOD.
Walkthrough
Instead of storing the entire history of counts in arrays, we only need to maintain the counts for the most recently computed row. We can use a few variables to store the state of the previous row and use them to compute the state for the current row.
We start with the base case for n=1, where there are 6 ways for two-color patterns and 6 ways for three-color patterns. We then iterate from 2 to n, continuously updating these two counts based on the same recurrence relations as before. At each step i, the variables hold the counts for row i-1, and we compute the new counts for row i.
This iterative update process eliminates the need for DP arrays, reducing the space complexity to constant time.
class Solution { public int numOfWays(int n) { if (n == 0) { return 0; } long MOD = 1_000_000_007; // Base case for n = 1 long twoColorCount = 6; long threeColorCount = 6; for (int i = 2; i <= n; i++) { long nextTwoColor = (3 * twoColorCount + 2 * threeColorCount) % MOD; long nextThreeColor = (2 * twoColorCount + 2 * threeColorCount) % MOD; twoColorCount = nextTwoColor; threeColorCount = nextThreeColor; } return (int) ((twoColorCount + threeColorCount) % MOD); }}Complexity
Time
O(n) - The time complexity is determined by the single loop that runs `n-1` times.
Space
O(1) - We only use a fixed number of variables to store the previous state, regardless of `n`.
Trade-offs
Pros
Extremely space-efficient, using only a constant amount of memory.
Maintains the simplicity and
O(n)time efficiency of the DP approach.Very practical and fast for the given problem constraints.
Cons
While efficient for the given constraints, the time complexity is still linear, which could be too slow for extremely large
n.
For problems with linear recurrence relations, we can often find a more asymptotically efficient solution using matrix exponentiation. The DP state transitions can be represented by a matrix multiplication.
The recurrence relations are:
two_color[i] = 3 * two_color[i-1] + 2 * three_color[i-1]
three_color[i] = 2 * two_color[i-1] + 2 * three_color[i-1]
This can be expressed in matrix form as:
[ two_color[i] ] = [ 3 2 ] * [ two_color[i-1] ]
[ three_color[i] ] [ 2 2 ] [ three_color[i-1] ]
Algorithm
- Handle the base case
n=1separately. - Define the 2x2 transition matrix
M = {{3, 2}, {2, 2}}. - Implement a function to multiply two 2x2 matrices, applying modulo at each step.
- Implement a function to compute
M^kusing the binary exponentiation (exponentiation by squaring) algorithm. This will takeO(log k)time. - Calculate
M_pow = M^(n-1). - The initial state vector for
n=1isV[1] = [6, 6]^T. - Compute the final state
V[n] = M_pow * V[1]. - The result is the sum of the elements in the resulting vector
V[n], moduloMOD.
Walkthrough
Let V[i] be the state vector [two_color[i], three_color[i]]^T and M be the transition matrix [[3, 2], [2, 2]]. The relationship V[i] = M * V[i-1] implies that V[n] = M^(n-1) * V[1].
The problem is now reduced to computing the (n-1)-th power of the matrix M. This can be done efficiently in O(log n) time using binary exponentiation for matrices. After computing M^(n-1), we multiply it by the base state vector V[1] = [6, 6]^T to get the final counts for row n.
This method is significantly faster than the O(n) DP approach for very large values of n and represents the most optimal solution in terms of time complexity.
class Solution { long MOD = 1_000_000_007; public int numOfWays(int n) { if (n == 1) { return 12; } // Transition matrix M long[][] M = {{3, 2}, {2, 2}}; // Compute M^(n-1) long[][] M_pow = matrixPower(M, n - 1); // Initial state vector V[1] = [6, 6] long twoColor1 = 6; long threeColor1 = 6; // V[n] = M^(n-1) * V[1] long twoColorN = (M_pow[0][0] * twoColor1 + M_pow[0][1] * threeColor1) % MOD; long threeColorN = (M_pow[1][0] * twoColor1 + M_pow[1][1] * threeColor1) % MOD; return (int) ((twoColorN + threeColorN) % MOD); } // Computes A^p using binary exponentiation private long[][] matrixPower(long[][] A, int p) { long[][] res = {{1, 0}, {0, 1}}; // Identity matrix long[][] T = A; while (p > 0) { if ((p & 1) == 1) { res = multiply(res, T); } T = multiply(T, T); p >>= 1; } return res; } // Multiplies two 2x2 matrices private long[][] multiply(long[][] A, long[][] B) { long[][] C = new long[2][2]; C[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD; C[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD; C[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD; C[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD; return C; }}Complexity
Time
O(log n) - Dominated by the matrix exponentiation algorithm. Each 2x2 matrix multiplication takes constant time.
Space
O(1) - The space required for the matrices and calculations is constant.
Trade-offs
Pros
The most asymptotically efficient solution in terms of time complexity.
Extremely fast for very large values of
n.
Cons
More complex to understand and implement compared to the iterative DP solution.
The constant factors involved in matrix multiplication might make it slightly slower than the simple DP for small values of
n.
Solutions
Solution
class Solution {public int numOfWays(int n) { int mod = (int)1 e9 + 7; long f0 = 6, f1 = 6; for (int i = 0; i < n - 1; ++i) { long g0 = (3 * f0 + 2 * f1) % mod; long g1 = (2 * f0 + 2 * f1) % mod; f0 = g0; f1 = g1; } return (int)(f0 + f1) % mod; }}using ll = long long ; class Solution { public: int numOfWays ( int n ) { int mod = 1e9 + 7 ; ll f0 = 6 , f1 = 6 ; while ( -- n ) { ll g0 = ( f0 * 3 + f1 * 2 ) % mod ; ll g1 = ( f0 * 2 + f1 * 2 ) % mod ; f0 = g0 ; f1 = g1 ; } return ( int ) ( f0 + f1 ) % mod ; } };class Solution: def numOfWays(self, n: int) -> int: mod = 10 ** 9 + 7 f0 = f1 = 6 for _ in range(n - 1): g0 = (3 * f0 + 2 * f1) % mod g1 = (2 * f0 + 2 * f1) % mod f0, f1 = g0, g1 return (f0 + f1) % modVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.