Painting a Grid With Three Different Colors — Solution
Painting a Grid With Three Different Colors solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Painting a Grid With Three Different Colors is a hard coding problem on dynamic programming and bitmask, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Dynamic Programming, Bitmask
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Paint every cell of an m × n grid red, green or blue so that no two adjacent cells — sharing a side — have the same colour.
Return the number of ways, modulo 10⁹ + 7.
Example 1
Input: m = 1, n = 1
Output: 3
Explanation: One cell, three colours.
Example 2
Input: m = 1, n = 2
Output: 6
Explanation: Three choices for the first cell and two for the second.
Example 3
Input: m = 5, n = 5
Output: 580986
Constraints
1 <= m <= 51 <= n <= 1000
Hints for Painting a Grid With Three Different Colors
Hint 1
mis at most 5, so a whole column has at most 3⁵ colourings — and only3 · 2^(m-1)of them are internally valid.Hint 2
Enumerate those valid columns once, then precompute which pairs of columns can sit side by side.
Hint 3
Step column by column, summing over compatible predecessors.
How to solve Painting a Grid With Three Different Colors
Treat each column as a single state. Enumerate the column colourings with no two vertically adjacent cells equal, precompute the compatibility relation between columns (no row matching), and run a linear DP across the n columns.
Approach
- Generate every column colouring of height
mwith no vertical conflict — there are3 · 2^(m-1). - For each ordered pair, mark them compatible when they differ in every row.
- Start
dp[p] = 1for every valid column. - For each further column,
next[b] = Σ dp[a]over compatiblea, modulo 10⁹ + 7. - Sum the final row.
Why it works
Columns rather than cells is the right granularity because the only coupling between columns is row-by-row, and m <= 5 keeps the state count at 48 even in the worst case. Precomputing compatibility matters: recomputing it inside the column loop would add a factor of m to a loop that already runs n · states² times.
Complexity
- Time —
O(n · S²) where S = 3 · 2^(m-1) - Space —
O(S²)
Pitfalls
- Two constraints, not one: vertical conflicts are handled when generating a column, horizontal ones by the compatibility test.
- Compatibility requires every row to differ, not merely some.
mandnare not interchangeable here — the DP runs overnwithminside the state.
Reference solution
Python
def colorTheGrid(m: int, n: int) -> int:
MOD = 10**9 + 7
patterns = []
def build(col):
if len(col) == m:
patterns.append(tuple(col))
return
for c in range(3):
if col and col[-1] == c:
continue
col.append(c)
build(col)
col.pop()
build([])
p = len(patterns)
compatible = [[b for b in range(p) if all(patterns[a][r] != patterns[b][r] for r in range(m))] for a in range(p)]
dp = [1] * p
for _ in range(2, n + 1):
nxt = [0] * p
for a in range(p):
if dp[a] == 0:
continue
for b in compatible[a]:
nxt[b] = (nxt[b] + dp[a]) % MOD
dp = nxt
return sum(dp) % MODJava
public static int colorTheGrid(int m, int n) {
final long MOD = 1000000007L;
List<int[]> patterns = new ArrayList<>();
int[] col = new int[m];
ctgBuild(patterns, col, 0, m);
int p = patterns.size();
List<List<Integer>> compatible = new ArrayList<>();
for (int a = 0; a < p; a++) {
List<Integer> list = new ArrayList<>();
for (int b = 0; b < p; b++) {
boolean ok = true;
for (int r = 0; r < m; r++) {
if (patterns.get(a)[r] == patterns.get(b)[r]) {
ok = false;
break;
}
}
if (ok) list.add(b);
}
compatible.add(list);
}
long[] dp = new long[p];
Arrays.fill(dp, 1);
for (int c = 2; c <= n; c++) {
long[] next = new long[p];
for (int a = 0; a < p; a++) {
if (dp[a] == 0) continue;
for (int b : compatible.get(a)) next[b] = (next[b] + dp[a]) % MOD;
}
dp = next;
}
long total = 0;
for (int a = 0; a < p; a++) total = (total + dp[a]) % MOD;
return (int) total;
}
private static void ctgBuild(List<int[]> out, int[] col, int depth, int m) {
if (depth == m) {
out.add(col.clone());
return;
}
for (int c = 0; c < 3; c++) {
if (depth > 0 && col[depth - 1] == c) continue;
col[depth] = c;
ctgBuild(out, col, depth + 1, m);
}
}C++
static void ctgBuild(vector<vector<int>>& out, vector<int>& col, int depth, int m) {
if (depth == m) {
out.push_back(col);
return;
}
for (int c = 0; c < 3; c++) {
if (depth > 0 && col[depth - 1] == c) continue;
col[depth] = c;
ctgBuild(out, col, depth + 1, m);
}
}
int colorTheGrid(int m, int n) {
const long long MOD = 1000000007LL;
vector<vector<int>> patterns;
vector<int> col(m, 0);
ctgBuild(patterns, col, 0, m);
int p = (int) patterns.size();
vector<vector<int>> compatible(p);
for (int a = 0; a < p; a++) {
for (int b = 0; b < p; b++) {
bool ok = true;
for (int r = 0; r < m; r++) {
if (patterns[a][r] == patterns[b][r]) {
ok = false;
break;
}
}
if (ok) compatible[a].push_back(b);
}
}
vector<long long> dp(p, 1);
for (int c = 2; c <= n; c++) {
vector<long long> next(p, 0);
for (int a = 0; a < p; a++) {
if (dp[a] == 0) continue;
for (int b : compatible[a]) next[b] = (next[b] + dp[a]) % MOD;
}
dp = next;
}
long long total = 0;
for (int a = 0; a < p; a++) total = (total + dp[a]) % MOD;
return (int) total;
}JavaScript
var colorTheGrid = function(m, n) {
var MOD = 1000000007;
var patterns = [];
var build = function(col) {
if (col.length === m) { patterns.push(col.slice()); return; }
for (var c = 0; c < 3; c++) {
if (col.length > 0 && col[col.length - 1] === c) continue;
col.push(c);
build(col);
col.pop();
}
};
build([]);
var p = patterns.length, a, b, r;
var compatible = [];
for (a = 0; a < p; a++) {
var list = [];
for (b = 0; b < p; b++) {
var ok = true;
for (r = 0; r < m; r++) {
if (patterns[a][r] === patterns[b][r]) { ok = false; break; }
}
if (ok) list.push(b);
}
compatible.push(list);
}
var dp = [];
for (a = 0; a < p; a++) dp.push(1);
for (var col = 2; col <= n; col++) {
var next = [];
for (a = 0; a < p; a++) next.push(0);
for (a = 0; a < p; a++) {
if (dp[a] === 0) continue;
for (var t = 0; t < compatible[a].length; t++) {
b = compatible[a][t];
next[b] = (next[b] + dp[a]) % MOD;
}
}
dp = next;
}
var total = 0;
for (a = 0; a < p; a++) total = (total + dp[a]) % MOD;
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming