Watch 10 video solutions for Number of Ways to Paint N × 3 Grid, a hard level problem involving Dynamic Programming. This walkthrough by codestorywithMIK has 12,991 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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).
| 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 |