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#1411 Number of Ways to Paint N × 3 Grid is a classic Dynamic Programming problem that focuses on recognizing repeating coloring patterns across rows of a grid. Since each row contains three cells and adjacent cells cannot share the same color, the key observation is that valid rows fall into two structural patterns: rows where two cells share the same color pattern (like ABA) and rows where all three cells are different (like ABC).
Instead of tracking every coloring combination, we track the number of ways each pattern can occur for a given row. Using these two states, we compute transitions from the previous row while ensuring vertical adjacency constraints are satisfied. This reduces the state space significantly and allows us to build the result iteratively for n rows.
The dynamic programming solution maintains counts for both pattern types and updates them row by row. With constant state transitions and modular arithmetic for large results, the algorithm runs efficiently even for large n. The overall time complexity is O(n) with O(1) additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Pattern States | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
We will use Dynamic programming approach. we will try all possible configuration.
Let dp[idx][prev1col][prev2col][prev3col] be the number of ways to color the rows of the grid from idx to n-1 keeping in mind that the previous row (idx - 1) has colors prev1col, prev2col and prev3col. Build the dp array to get the answer.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is a strong dynamic programming interview question. It tests pattern recognition, state transitions, and optimization techniques, which are commonly evaluated in interviews at top tech companies.
The optimal approach uses dynamic programming with two row patterns: rows where two cells share a color pattern and rows where all three cells have different colors. By tracking these states and computing valid transitions between rows, we can efficiently count the total number of valid colorings.
Dynamic programming works well because each row's valid colorings depend only on the pattern of the previous row. By storing counts of valid pattern types and updating them iteratively, we avoid recomputing all combinations and significantly reduce complexity.
The optimized solution only requires a few integer variables to track counts of the two row patterns. Instead of using large arrays or matrices, we update these values iteratively, achieving constant space usage.