Get started

Painting a Grid With Three Different Colors — Hard Problem & Solution

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.

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 <= 5
  • 1 <= n <= 1000

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

  1. Generate every column colouring of height m with no vertical conflict — there are 3 · 2^(m-1).
  2. For each ordered pair, mark them compatible when they differ in every row.
  3. Start dp[p] = 1 for every valid column.
  4. For each further column, next[b] = Σ dp[a] over compatible a, modulo 10⁹ + 7.
  5. 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.
  • m and n are not interchangeable here — the DP runs over n with m inside 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) % MOD

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 195 dynamic programming problems · the whole catalogue