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 <= 5000Problem Overview: You need to count how many ways an n × 3 grid can be painted using three colors such that no two adjacent cells share the same color. Adjacency applies both horizontally within a row and vertically between rows. The result must be returned modulo 1e9 + 7.
Approach 1: Dynamic Programming with Pattern States (O(n) time, O(1) space)
The key observation is that every valid row falls into one of two patterns: ABA (two colors) or ABC (three different colors). For the first row, there are 6 ways to create each pattern. While iterating row by row, compute how many new ABA and ABC rows can follow the previous patterns without breaking vertical color constraints. The transitions are simple linear relations: a previous ABA can generate both patterns in fixed counts, and the same applies for ABC. Track two integers (countABA, countABC) and update them for each row. This reduces the state space dramatically compared to enumerating all color combinations and is a classic example of state compression in dynamic programming. Time complexity is O(n) with constant O(1) space.
Approach 2: Matrix Exponentiation (O(log n) time, O(1) space)
The DP recurrence between rows is linear, which means it can be represented as a matrix transition. Define a vector [ABA, ABC] and multiply it by a fixed 2×2 transition matrix that encodes how patterns evolve from one row to the next. Instead of iterating n times, raise the transition matrix to the power n-1 using fast exponentiation. Each multiplication updates the pattern counts while preserving the adjacency rules. This converts the linear DP into logarithmic complexity and is a common optimization technique in matrix exponentiation problems involving recurrence relations.
Both approaches rely on recognizing repeating structural patterns rather than brute-force coloring of each cell. Instead of exploring 3^(3n) possibilities, the algorithm reduces the problem to just two state transitions derived from simple combinatorics.
Recommended for interviews: The dynamic programming state-compression approach is what interviewers expect. It demonstrates pattern recognition, recurrence building, and space optimization. Matrix exponentiation is a strong follow-up optimization when n can be extremely large and you want to reduce runtime from O(n) to O(log n).
In this approach, we establish a pattern-based system to manage the color arrangement of each row. We start by identifying two pattern types: 'Type A', where the row contains two colors across three cells (like RYR), and 'Type B', where all three cells have different colors (like RYG). The transformation of patterns from one row to the next depends on these types, forming distinct state transitions.
We use dynamic programming to keep track of the count formation of both types of patterns, updating these counts row by row until we reach 'n' rows. The final result is obtained by summing the number of possible patterns of Types A and B for a grid with 'n' rows.
This C program uses two long integers, 'a' and 'b', to represent the ways of painting the row ending in Type A and Type B patterns. Starting with 6 of each for the first row, it updates them for each subsequent row of 'n' using specific recurrence relations.
Time Complexity: O(n), since the loop iterates over the number of rows.
Space Complexity: O(1), because only a fixed amount of memory is used regardless of 'n'.
This approach involves formulating the given problem as a matrix exponentiation problem, where the state transformations can be represented as matrix multiplications. This method is highly beneficial when pushing for rapid, logarithmic-time calculation concerning pattern transformations over many rows.
We define our transformation matrix based on pattern interdependencies: how Type A can transform into new Type A and B and vice versa, then compute this matrix's power to 'n' using fast exponentiation. This enables calculating the resulting pattern count efficiently.
This C code uses matrix multiplication to accelerate pattern calculations through power calculations, ensuring an efficient extrapolation of results even with extensive grids.
Time Complexity: O(log n), for matrix exponentiation.
Space Complexity: O(1), only using a constant-sized matrix.
We classify all possible states for each row. According to the principle of symmetry, when a row only has 3 elements, all legal states are classified as: 010 type, 012 type.
010 type: The possible states for the next row are: 101, 102, 121, 201, 202. These 5 states can be summarized as 3 010 types and 2 012 types.012 type: The possible states for the next row are: 101, 120, 121, 201. These 4 states can be summarized as 2 010 types and 2 012 types.In summary, we can get: newf0 = 3 times f0 + 2 times f1, newf1 = 2 times f0 + 2 times f1.
The time complexity is O(n), where n is the number of rows in the grid. The space complexity is O(1).
We notice that the grid only has 3 columns, so there are at most 3^3=27 different coloring schemes in a row.
Therefore, we define f[i][j] to represent the number of schemes in the first i rows, where the coloring state of the ith row is j. The state f[i][j] is transferred from f[i - 1][k], where k is the coloring state of the i - 1th row, and k and j meet the requirement of different colors being adjacent. That is:
$
f[i][j] = sum_{k \in valid(j)} f[i - 1][k]
where valid(j) represents all legal predecessor states of state j.
The final answer is the sum of f[n][j], where j is any legal state.
We notice that f[i][j] is only related to f[i - 1][k], so we can use a rolling array to optimize the space complexity.
The time complexity is O((m + n) times 3^{2m}), and the space complexity is O(3^m). Here, m and n$ are the number of rows and columns of the grid, respectively.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n), since the loop iterates over the number of rows. |
| Matrix Exponentiation | Time Complexity: O(log n), for matrix exponentiation. |
| Recursion | — |
| State Compression + Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Pattern States) | O(n) | O(1) | Best general solution for interviews and typical constraints |
| Matrix Exponentiation | O(log n) | O(1) | When n is extremely large and DP iteration becomes expensive |
Number of Ways to Paint N × 3 Grid | Hard Made Easy | Simple Story To Code | Leetcode 1411 | MIK • codestorywithMIK • 12,991 views views
Watch 9 more video solutions →Practice Number of Ways to Paint N × 3 Grid with our built-in code editor and test cases.
Practice on FleetCode