Painting a Grid With Three Different Colors

Hard
1069.

Painting a Grid With Three Different Colors

Painting a Grid With Three Different Colors is a hard coding problem on dynamic programming and bitmask, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var colorTheGrid = function(m, n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Painting a Grid With Three Different Colors

  1. Hint 1

    m is at most 5, so a whole column has at most 3⁵ colourings — and only 3 · 2^(m-1) of them are internally valid.

  2. Hint 2

    Enumerate those valid columns once, then precompute which pairs of columns can sit side by side.

  3. 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

  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

Java

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