HardDynamic ProgrammingGraph ColoringUpdated Sep 2026

1931. Painting a Grid With Three Different Colors

Asked at Uber

Difficulty

Hard

Time

O(m * 3^m * log n) with matrix e

Space

O(3^m) for the DP array, plus O(

Pattern

Dynamic Programming

Companies

1

Problem

You get two integers m and n. Picture an m x n grid where every cell starts white. You must paint every cell using one of three colors: red, green, or blue.

The rule is: two cells that share a side must not have the same color. Cells that only touch at a corner are not neighbors, so they may match.

Return the number of valid paintings. Because the count can be huge, give the answer modulo 10^9 + 7.

A useful way to think about it: fix one column. Inside that column, no two stacked cells may share a color. Then between two neighboring columns, no row may have the same color on both sides.

Neighbors must differ

m=2, n=20101RGGBA legal painting: every pair of side-neighbors hasdifferent colors
Each cell takes one of three colors, and side-by-side neighbors can never match.

Constraints

  • ●1 <= m <= 5
  • ●1 <= n <= 1000
  • ●Answer must be returned modulo 10^9 + 7

Examples

Example 1
Inputm = 1, n = 1
Output3
WhyA single cell has no neighbors, so any of the three colors works. That gives 3 paintings.
Example 2
Inputm = 1, n = 2
Output6
WhyThe first cell has 3 choices. The second cell sits next to it, so it must differ from the first, leaving 2 choices. 3 × 2 = 6.
Example 3
Inputm = 5, n = 5
Output580986
WhyWith 5 rows there are 48 valid single-column patterns, and the compatibility rules between columns cut the total down to 580986.

Asked At

1 companies
CompanyDifficulty
UberHardView all Uber questions →

How to Think About It

1

For a single column, enumerate all valid colorings (no two adjacent cells same color)

2

Two columns are compatible if no row has same color in both columns

3

Precompute compatibility between column colorings using bitmask representation

4

DP[j][mask] = ways to paint first j columns with last column being mask

5

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.

Column DP with compatibility

valid columns (m=2)01c0c1c2RGRBGROnly columns with no vertical repeat are allowed — 6of them for m=2compatible pairsc0c1c2c0c1c2-okokok-okokok-Two columns are compatible when no row shares a colordp[j][mask] = sum dp[j-1][prev]over all prev compatible with maskanswer = sum dp[n-1][*] mod 1e9+7
Build valid columns first, then chain them so no row repeats a color between neighbors.
ComplexityTime O(m * 3^m * log n) with matrix eSpace O(3^m) for the DP array, plus O(The cost comes from enumerating all 3^m column patterns and, for each pair, checking row-by-row compatibility.

What Trips People Up in Real Interviews

1

Column-wise DP is the key insight — process column by column

2

Represent each column coloring as a base-3 number or bitmask

3

For m <= 5, there are at most 3^5 = 243 possible column states, but many are invalid

4

Precompute valid states and compatibility once, then use matrix exponentiation if n is large

5

Edge case: m=1 or n=1 — just count valid single-row/column colorings

Solution Code

O(m * 3^m * log n) with matrix e time
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) % MOD

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(m * 3^m * log n) with matrix e time and O(3^m) for the DP array, plus O( space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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