You are given two integers m and n. Consider an m x n grid where each cell is initially white. You can paint each cell red, green, or blue. All cells must be painted.
Return the number of ways to color the grid with no two adjacent cells having the same color. Since the answer can be very large, return it modulo 109 + 7.
Example 1:
Input: m = 1, n = 1 Output: 3 Explanation: The three possible colorings are shown in the image above.
Example 2:
Input: m = 1, n = 2 Output: 6 Explanation: The six possible colorings are shown in the image above.
Example 3:
Input: m = 5, n = 5 Output: 580986
Constraints:
1 <= m <= 51 <= n <= 1000In #1931 Painting a Grid With Three Different Colors, the goal is to count the number of valid ways to color an m x n grid using three colors such that no two adjacent cells share the same color. Because m is small (≤5) but n can be large, a column-by-column dynamic programming strategy works well.
The key idea is to represent each column’s coloring as a state using base‑3 encoding or an array representation. First, generate all valid column states where vertically adjacent cells have different colors. Next, precompute which column states can transition to others without violating the horizontal adjacency rule. Then apply DP across columns: for each column, accumulate the number of ways to transition from all compatible previous states.
This reduces the problem to managing transitions between a limited set of valid states. The overall complexity depends on the number of valid column configurations and their transitions, typically around O(n * S^2), where S is the number of valid column states.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Column State DP with Precomputed Transitions | O(n * S^2) | O(S) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Represent each colored column by a bitmask based on each cell color.
Use bitmasks DP with state (currentCell, prevColumn).
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, variations of grid coloring and state-compression dynamic programming problems appear in FAANG-style interviews. They test a candidate’s ability to model constraints, generate valid states, and optimize transitions using DP.
State representations such as arrays or base-3 encoded integers are commonly used to represent column color patterns. Hash maps or arrays can store DP counts for each valid state, while adjacency lists can track valid transitions between states.
The optimal approach uses dynamic programming with column state compression. Each column is encoded as a valid color configuration, and transitions are computed between compatible columns. This significantly reduces the search space and allows efficient counting for large n.
Dynamic programming works well because the grid can be processed column by column, and each column only depends on the previous one. By storing results for valid column states, repeated computations are avoided and the total number of configurations can be counted efficiently.