Painting a Grid With Three Different Colors - Solution & Explanation
Problem Statement
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 <= 1000
Approach Overview
Problem 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 1: Dynamic Programming with Pattern Compression
We will use dynamic programming to solve this problem by first focusing on a single column. Each column can have certain valid color patterns that adhere to the rules -- no two adjacent cells have the same color. We will precompute these valid patterns and then extend this to multiple columns using dynamic programming.
The core idea is to calculate the number of ways to fill the grid up to each column, given the pattern of the previous column. This involves considering all possible compatible patterns for new columns based on previous ones. We store results in a DP table and utilize modulo operations to avoid overflow.
This C code calculates the number of ways to color the grid using dynamic programming. The two variables 'color3' and 'color2' store the number of ways to paint a column in a 3-color pattern and a 2-color pattern respectively. The loops iterate over columns and update these patterns based on previous columns, respecting the color rules.
Complexity
The time complexity is O(n), and the space complexity is O(1) as we only use a fixed amount of extra space.
Approach 2: Optimized Dynamic Programming with Memoization
This method involves using a memoization table to record transitions between valid patterns. The key is to represent each valid column configuration in a way that captures all legal states, and keep track of transitions between states to avoid redundant calculations. This dramatically reduces the computation complexities by caching evaluations.
By using bitwise operations or effectively encoding states, patterns can be compactly stored, leveraging recursion with memoization to efficiently compute the total number of colorings.
In this C solution, a recursive function is used, coupled with a memoization table (a 2-dimensional array) to store previous results. The 'isValidState' function checks if a particular configuration complies with color rules.
Complexity
Space and time complexities can be near O(n * 3^m) due to memoization and reduced redundant calculations.
Approach 3: State Compression + Dynamic Programming
We notice that the number of rows in the grid does not exceed 5, so there are at most 3^5=243 different color schemes in a column.
Therefore, we define f[i][j] to represent the number of schemes in the first i columns, where the coloring state of the ith column is j. The state f[i][j] is transferred from f[i - 1][k], where k is the coloring state of the i - 1th column, 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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Pattern Compression | The time complexity is O(n), and the space complexity is O(1) as we only use a fixed amount of extra space. |
| Optimized Dynamic Programming with Memoization | Space and time complexities can be near O(n * 3^m) due to memoization and reduced redundant calculations. |
| State Compression + Dynamic Programming | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Painting a Grid With Three Different Colors | Thought Process | Leetcode 1931 | codestorywithMIK • codestorywithMIK • 17,639 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Painting a Grid With Three Different Colors easy or hard?
Painting a Grid With Three Different Colors Python/Java solution
How to solve Painting a Grid With Three Different Colors in O(n)?
What is the best approach for Painting a Grid With Three Different Colors?
Is Painting a Grid With Three Different Colors asked at Google/Amazon/Meta?
What data structure is used in Painting a Grid With Three Different Colors?
What is the time complexity of Painting a Grid With Three Different Colors?
Ready to solve this problem?
Practice Painting a Grid With Three Different Colors with our built-in code editor and test cases.
Practice on FleetCode