Painting a Grid With Three Different Colors solution and explanation
Google
9 more videos on this problem
Painting a Grid With Three Different Colors | Thought Process | Leetcode 1931 | codestorywithMIKcodestorywithMIK · 50:52 · 17K views
Painting a Grid With Three Different Colors | Leetcode 1931 | DP BitmaskingTechdose · 43:40 · 9K views
LeetCode 1931. Painting a Grid With Three Different ColorsHappy Coding · 25:26 · 4K views
1931. Painting a Grid With Three Different Colors (Leetcode Hard)Programming Live with Larry · 21:32 · 2K views
Leetcode: Painting a Grid With Three Different ColorsCoding For Dummies · 19:17 · 2K views
Painting a Grid With Three Different Colors | Leetcode | Detailed Explaination | Graphs | DPAthar Mohd · 16:27 · 1K views
Daily Leetcode #1874: May 18, 2025 - 1931. Painting a Grid With Three Different ColorsProgramming Live with Larry · 19:35 · 1K views
LeetCode 1931 - Painting a Grid With Three Different Colors - JavaAlpha-Code · 13:24 · 1K views
🎀LeetCode 1931🎀 Painting a Grid With Three Different ColorsCoding with Lucinda · 1:12 · 1K views
Leetcode 1931: How to Color a Grid With No Matching NeighborsVeiled Logic · 0:46 · 1K views
The problem
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.
def numOfWays(m, n):
MOD = 1000000007
color3, color2 = 6, 6
for _ in range(2, n + 1):
newColor3 = (2 * color3 + 2 * color2) % MOD
newColor2 = (2 * color3 + 3 * color2) % MOD
color3, color2 = newColor3, newColor2
return (color3 + color2) % MOD
print(numOfWays(5, 5))public class Solution {
private static final int MOD = 1000000007;
public int numOfWays(int m, int n) {
int color3 = 6, color2 = 6;
for (int col = 2; col <= n; ++col) {
int newColor3 = (2 * color3 + 2 * color2) % MOD;
int newColor2 = (2 * color3 + 3 * color2) % MOD;
color3 = newColor3;
color2 = newColor2;
}
return (color3 + color2) % MOD;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.numOfWays(5, 5));
}
}#include <iostream>
using namespace std;
#define MOD 1000000007
int numOfWays(int m, int n) {
int color3 = 6, color2 = 6;
for (int col = 2; col <= n; ++col) {
int newColor3 = (2 * color3 + 2 * color2) % MOD;
int newColor2 = (2 * color3 + 3 * color2) % MOD;
color3 = newColor3;
color2 = newColor2;
}
return (color3 + color2) % MOD;
}
int main() {
int m = 5, n = 5;
cout << numOfWays(m, n) << endl;
return 0;
}const MOD = 1000000007;
function numOfWays(m, n) {
let color3 = 6, color2 = 6;
for (let col = 2; col <= n; ++col) {
let newColor3 = (2 * color3 + 2 * color2) % MOD;
let newColor2 = (2 * color3 + 3 * color2) % MOD;
color3 = newColor3;
color2 = newColor2;
}
return (color3 + color2) % MOD;
}
console.log(numOfWays(5, 5));#include <stdio.h>
#define MOD 1000000007
int numOfWays(int m, int n) {
int color3 = 6, color2 = 6;
for (int col = 2; col <= n; ++col) {
int newColor3 = (2 * color3 + 2 * color2) % MOD;
int newColor2 = (2 * color3 + 3 * color2) % MOD;
color3 = newColor3;
color2 = newColor2;
}
return (color3 + color2) % MOD;
}
int main() {
int m = 5, n = 5;
printf("%d\n", numOfWays(m, n));
return 0;
}using System;
public class Solution {
private const int MOD = 1000000007;
public int NumOfWays(int m, int n) {
int color3 = 6, color2 = 6;
for (int col = 2; col <= n; ++col) {
int newColor3 = (2 * color3 + 2 * color2) % MOD;
int newColor2 = (2 * color3 + 3 * color2) % MOD;
color3 = newColor3;
color2 = newColor2;
}
return (color3 + color2) % MOD;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.NumOfWays(5, 5));
}
}In the Python implementation, we initiate with predefined valid pattern counts for a single column and update them iteratively for each following column to ensure compliance with the coloring rules.
Time complexity is O(n), and it uses a constant amount of space, O(1).
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.
def numOfWaysRecur(m, n, col, prevState, memo):
MOD = 1000000007
if col == n:
return 1
if (col, prevState) in memo:
return memo[(col, prevState)]
count = 0
for state in range(1 << m):
if isValidState(m, prevState, state):
count = (count + numOfWaysRecur(m, n, col + 1, state, memo)) % MOD
memo[(col, prevState)] = count
return count
def numOfWays(m, n):
return numOfWaysRecur(m, n, 0, 0, {})
def isValidState(m, prevState, state):
# Implementation assumed to check valid adjacent conditions
pass
print(numOfWays(5, 5))import java.util.HashMap;
public class Solution {
private static final int MOD = 1000000007;
private HashMap<Integer, HashMap<Integer, Integer>> memo = new HashMap<>();
private int numOfWaysRecur(int m, int n, int col, int prevState) {
if (col == n) return 1;
if (memo.containsKey(col) && memo.get(col).containsKey(prevState))
return memo.get(col).get(prevState);
int count = 0;
for (int state = 0; state < (1 << m); ++state) {
if (isValidState(m, prevState, state)) {
count = (count + numOfWaysRecur(m, n, col + 1, state)) % MOD;
}
}
memo.computeIfAbsent(col, k -> new HashMap<>()).put(prevState, count);
return count;
}
public int numOfWays(int m, int n) {
return numOfWaysRecur(m, n, 0, 0);
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.numOfWays(5, 5));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
#define MOD 1000000007
unordered_map<int, unordered_map<int, int>> memo;
int numOfWaysRecur(int m, int n, int col, int prevState) {
if (col == n) return 1;
if (memo[col].count(prevState)) return memo[col][prevState];
int count = 0;
for (int state = 0; state < (1 << m); ++state) {
if (isValidState(m, prevState, state)) {
count = (count + numOfWaysRecur(m, n, col + 1, state)) % MOD;
}
}
memo[col][prevState] = count;
return count;
}
int numOfWays(int m, int n) {
return numOfWaysRecur(m, n, 0, 0);
}
int main() {
cout << numOfWays(5, 5) << endl;
return 0;
}const MOD = 1000000007;
function numOfWaysRecur(m, n, col, prevState, memo) {
if (col === n) return 1;
if (memo.has(`${col}-${prevState}`)) return memo.get(`${col}-${prevState}`);
let count = 0;
for (let state = 0; state < (1 << m); ++state) {
if (isValidState(m, prevState, state)) {
count = (count + numOfWaysRecur(m, n, col + 1, state, memo)) % MOD;
}
}
memo.set(`${col}-${prevState}`, count);
return count;
}
function numOfWays(m, n) {
const memo = new Map();
return numOfWaysRecur(m, n, 0, 0, memo);
}
function isValidState(m, prevState, state) {
// Implement validation logic
return true;
}
console.log(numOfWays(5, 5));#include <stdio.h>
#define MOD 1000000007
int memo[1000][1024];
int numOfWaysRecur(int m, int n, int col, int prevState) {
if (col == n) return 1;
if (memo[col][prevState] != -1) return memo[col][prevState];
int count = 0;
for (int state = 0; state < (1 << m); ++state) {
if (isValidState(m, prevState, state)) {
count = (count + numOfWaysRecur(m, n, col + 1, state)) % MOD;
}
}
memo[col][prevState] = count;
return count;
}
int numOfWays(int m, int n) {
memset(memo, -1, sizeof(memo));
return numOfWaysRecur(m, n, 0, 0);
}
int main() {
printf("%d\n", numOfWays(5, 5));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
private const int MOD = 1000000007;
private Dictionary<int, Dictionary<int, int>> memo = new Dictionary<int, Dictionary<int, int>>();
private int NumOfWaysRecur(int m, int n, int col, int prevState) {
if (col == n) return 1;
if (memo.ContainsKey(col) && memo[col].ContainsKey(prevState))
return memo[col][prevState];
int count = 0;
for (int state = 0; state < (1 << m); ++state) {
if (IsValidState(m, prevState, state)) {
count = (count + NumOfWaysRecur(m, n, col + 1, state)) % MOD;
}
}
if (!memo.ContainsKey(col)) memo[col] = new Dictionary<int, int>();
memo[col][prevState] = count;
return count;
}
public int NumOfWays(int m, int n) {
return NumOfWaysRecur(m, n, 0, 0);
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.NumOfWays(5, 5));
}
private bool IsValidState(int m, int prevState, int state) {
// Assumed implementation
return true;
}
}The Python function uses a dictionary for memoization, enabling optimization through recorded results of previously solved states, preventing repeated calculations.
The execution exhibits O(n * 3^m) complexity due to the combination of recursive evaluation and memoization.
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.
function colorTheGrid(m: number, n: number): number {
const f1 = (x: number): boolean => {
let last = -1;
for (let i = 0; i < m; ++i) {
if (x % 3 === last) {
return false;
}
last = x % 3;
x = Math.floor(x / 3);
}
return true;
};
const f2 = (x: number, y: number): boolean => {
for (let i = 0; i < m; ++i) {
if (x % 3 === y % 3) {
return false;
}
x = Math.floor(x / 3);
y = Math.floor(y / 3);
}
return true;
};
const mx = 3 ** m;
const valid = new Set<number>();
const f: number[] = Array(mx).fill(0);
for (let i = 0; i < mx; ++i) {
if (f1(i)) {
valid.add(i);
f[i] = 1;
}
}
const d: Map<number, number[]> = new Map();
for (const i of valid) {
for (const j of valid) {
if (f2(i, j)) {
d.set(i, (d.get(i) || []).concat(j));
}
}
}
const mod = 10 ** 9 + 7;
for (let k = 1; k < n; ++k) {
const g: number[] = Array(mx).fill(0);
for (const i of valid) {
for (const j of d.get(i) || []) {
g[i] = (g[i] + f[j]) % mod;
}
}
f.splice(0, f.length, ...g);
}
let ans = 0;
for (const x of f) {
ans = (ans + x) % mod;
}
return ans;
}func colorTheGrid(m int, n int) (ans int) {
f1 := func(x int) bool {
last := -1
for i := 0; i < m; i++ {
if x%3 == last {
return false
}
last = x % 3
x /= 3
}
return true
}
f2 := func(x, y int) bool {
for i := 0; i < m; i++ {
if x%3 == y%3 {
return false
}
x /= 3
y /= 3
}
return true
}
mx := int(math.Pow(3, float64(m)))
valid := map[int]bool{}
f := make([]int, mx)
for i := 0; i < mx; i++ {
if f1(i) {
valid[i] = true
f[i] = 1
}
}
d := map[int][]int{}
for i := range valid {
for j := range valid {
if f2(i, j) {
d[i] = append(d[i], j)
}
}
}
const mod int = 1e9 + 7
for k := 1; k < n; k++ {
g := make([]int, mx)
for i := range valid {
for _, j := range d[i] {
g[i] = (g[i] + f[j]) % mod
}
}
f = g
}
for _, x := range f {
ans = (ans + x) % mod
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Pattern Compression | Time complexity is O(n), and it uses a constant amount of space, O(1). |
| Optimized Dynamic Programming with Memoization | The execution exhibits O(n * 3^m) complexity due to the combination of recursive evaluation and memoization. |
| State Compression + Dynamic Programming | – |
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 |
Frequently asked questions
Is Painting a Grid With Three Different Colors easy or hard?
Painting a Grid With Three Different Colors is classified as Hard because the naive search space is exponential. The challenge is recognizing that the grid can be processed column by column and compressed into a small set of valid states using dynamic programming.
Painting a Grid With Three Different Colors Python/Java solution
Python and Java implementations typically generate all valid column states using DFS or base-3 enumeration, precompute compatible transitions, then run dynamic programming across columns. Python uses lists and dictionaries for state transitions, while Java often uses arrays for faster DP updates.
How to solve Painting a Grid With Three Different Colors in O(n)?
Pure O(n) time is not achievable because each column must check transitions with multiple valid patterns. The closest efficient approach is O(n * S^2) using pattern-compressed dynamic programming, where S is small due to the constraint m ≤ 5. This keeps the algorithm fast even for n up to 1000.
What is the best approach for Painting a Grid With Three Different Colors?
The most efficient approach uses pattern compression with dynamic programming. Each column is represented as a valid color pattern where vertically adjacent cells differ. Precompute all valid patterns and transitions between compatible columns, then run DP across columns. This reduces the problem from 3^(m*n) possibilities to roughly O(n * S^2) where S is the number of valid column states.
Is Painting a Grid With Three Different Colors asked at Google/Amazon/Meta?
Grid coloring and state-compression dynamic programming problems appear frequently in interviews at companies like Google and Meta. Variants involving column DP, tiling, or bitmask state transitions are common in high-difficulty interview rounds.
What data structure is used in Painting a Grid With Three Different Colors?
The solution mainly uses arrays or hash maps for dynamic programming states and lists to store valid column patterns. Many implementations encode patterns using integers or base-3 representations, similar to techniques used in bitmask dynamic programming.
What is the time complexity of Painting a Grid With Three Different Colors?
The optimized dynamic programming solution runs in O(n * S^2) time, where S is the number of valid column patterns (about 48 when m = 5). Space complexity is O(S) for the iterative DP version or O(n * S) for memoized recursion.