Watch 10 video solutions for Painting a Grid With Three Different Colors, a hard level problem involving Dynamic Programming. This walkthrough by codestorywithMIK has 16,959 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1000Problem Overview: You need to paint an m x n grid using three colors so that no two adjacent cells share the same color. Adjacent means both vertical and horizontal neighbors. The goal is to count the number of valid colorings modulo 1e9 + 7.
Approach 1: Dynamic Programming with Pattern Compression (O(n * S^2) time, O(S) space)
The key observation: constraints only depend on neighboring columns. Instead of tracking every cell, compress each column into a state. A state represents a valid coloring of one column where vertically adjacent cells have different colors. For m ≤ 5, there are at most 3^m possibilities, and only the ones with no vertical conflicts are kept. Precompute all valid column states, then build a compatibility graph where two states can follow each other if every row has different colors across the columns.
Dynamic programming runs column by column. Let dp[i][state] be the number of ways to paint up to column i ending with that column pattern. For each new column, iterate through compatible previous states and accumulate counts. Because the number of valid states is small (around 48 when m = 5), the transition cost stays manageable. This is a classic column-compression technique often used in dynamic programming and bitmask DP style problems.
Approach 2: Optimized Dynamic Programming with Memoization (O(n * S^2) time, O(n * S) space)
This variation uses top‑down recursion with memoization. First generate all valid column patterns exactly like the compression approach. Then recursively compute the number of ways to fill columns starting from index 0. The state is defined by (columnIndex, previousPattern). For each step, iterate through all patterns that are compatible with the previous one and recursively process the next column.
Memoization avoids recomputing overlapping subproblems. The recursion depth equals n, and each state explores only valid transitions between patterns. This approach is easier to reason about because it models the grid as a sequence of column decisions, while still leveraging the same compressed state space.
Recommended for interviews: Pattern compression with bottom‑up DP is the expected solution. It shows you can reduce a 2D coloring problem into manageable column states and precompute transitions. Mentioning the brute 3^(m*n) search briefly demonstrates why compression is necessary, but implementing the optimized DP proves strong dynamic programming skills and awareness of state reduction techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Pattern Compression | O(n * S^2) | O(S) | Best practical approach when rows are small (m ≤ 5) and columns are large |
| Optimized DP with Memoization | O(n * S^2) | O(n * S) | When recursion is easier to implement and you want clearer state transitions |