Painting a Grid With Three Different Colors
Asked at Uber
Problem
You have an m x n grid that needs to be painted with three colors (red, green, blue) such that no two adjacent cells share the same color. Count the number of ways to paint the grid. Return the answer modulo 10^9+7. Two cells are adjacent if they share a side.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | HARD | View all Uber questions → |
How to Think About It
For a single column, enumerate all valid colorings (no two adjacent cells same color)
Two columns are compatible if no row has same color in both columns
Precompute compatibility between column colorings using bitmask representation
DP[j][mask] = ways to paint first j columns with last column being mask
Transition: DP[j][mask] = sum of DP[j-1][prev] for all prev compatible with mask
Optimal Approach
Enumerate all valid colorings of a single column (no two adjacent cells share color). Represent each as a base-3 number. Precompute which pairs of column colorings are compatible (no same color in same row). Use DP where dp[j][mask] = ways to paint j columns ending with coloring mask. Transition sums over all compatible previous masks. With matrix exponentiation on the compatibility matrix, solve in O(m * 3^m * log(n)) time.
What Trips People Up in Real Interviews
Column-wise DP is the key insight — process column by column
Represent each column coloring as a base-3 number or bitmask
For m <= 5, there are at most 3^5 = 243 possible column states, but many are invalid
Precompute valid states and compatibility once, then use matrix exponentiation if n is large
Edge case: m=1 or n=1 — just count valid single-row/column colorings
Solution Code
class Solution:
def colorTheGrid(self, m: int, n: int) -> int:
MOD = 10**9 + 7
def valid_states(m):
states = []
def dfs(pos, state, last):
if pos == m:
states.append(state)
return
for c in range(3):
if c != last:
dfs(pos + 1, state * 3 + c, c)
dfs(0, 0, -1)
return states
states = valid_states(m)
num_states = len(states)
compatible = [[] for _ in range(num_states)]
for i in range(num_states):
for j in range(num_states):
s1, s2 = states[i], states[j]
ok = True
for _ in range(m):
if s1 % 3 == s2 % 3:
ok = False
break
s1 //= 3
s2 //= 3
if ok:
compatible[i].append(j)
dp = [1] * num_states
for _ in range(n - 1):
new_dp = [0] * num_states
for j in range(num_states):
for k in compatible[j]:
new_dp[k] = (new_dp[k] + dp[j]) % MOD
dp = new_dp
return sum(dp) % MODFrequently Asked Questions
What is the Painting a Grid With Three Different Colors problem?
You have an m x n grid that needs to be painted with three colors (red, green, blue) such that no two adjacent cells share the same color. Count the number of ways to paint the grid. Return the answer modulo 10^9+7. Two cells are adjacent if they share a side.
How do you solve Painting a Grid With Three Different Colors?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Painting a Grid With Three Different Colors?
Painting a Grid With Three Different Colors is asked at Uber. It is a hard difficulty problem.
What are common mistakes on Painting a Grid With Three Different Colors?
- Column-wise DP is the key insight — process column by column
- Represent each column coloring as a base-3 number or bitmask
- For m <= 5, there are at most 3^5 = 243 possible column states, but many are invalid
- Precompute valid states and compatibility once, then use matrix exponentiation if n is large
- Edge case: m=1 or n=1 — just count valid single-row/column colorings