# Painting a Grid With Three Different Colors
**Difficulty:** HARD
[External](https://leetcode.com/problems/painting-a-grid-with-three-different-colors)
Canonical: https://scaleengineer.com/dsa/problems/painting-a-grid-with-three-different-colors
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
---
## Problem
You are given two integers `m` and `n`. Consider an `m x n` grid where each cell is initially white. You can paint each cell **red**, **green**, or **blue**. All cells **must** be painted.

Return _the number of ways to color the grid with **no two adjacent cells having the same color**_. Since the answer can be very large, return it **modulo** `109 + 7`.

**Example 1:**

![](https://assets.glich.co/dsa/painting-a-grid-with-three-different-colors/image0.png) 

**Input:** m = 1, n = 1
**Output:** 3
**Explanation:** The three possible colorings are shown in the image above.

**Example 2:**

![](https://assets.glich.co/dsa/painting-a-grid-with-three-different-colors/image1.png) 

**Input:** m = 1, n = 2
**Output:** 6
**Explanation:** The six possible colorings are shown in the image above.

**Example 3:**

**Input:** m = 5, n = 5
**Output:** 580986

**Constraints:**

* `1 <= m <= 5`
* `1 <= n <= 1000`

# Approaches
## Brute-Force Backtracking
This approach attempts to solve the problem by exploring every possible way to color the grid, one cell at a time, using recursion. For each cell, it tries to place one of the three colors, ensuring it doesn't conflict with its already colored top and left neighbors. If a valid coloring for the entire grid is found, a counter is incremented. This is a brute-force method that systematically checks all combinations.
**Time:** O(3^(m*n)). At each of the `m*n` cells, we might try up to 3 colors, leading to an exponential number of paths in the recursion tree. This is too slow for the given constraints. · **Space:** O(m * n) to store the grid and for the recursion stack depth.
**Pros:** Conceptually simple and a direct translation of the problem statement.; Easy to implement for a first attempt.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error on any reasonably sized grid.
### Explanation
We define a recursive function, say `solve(row, col)`, that tries to color the cell at `(row, col)`. The base case for the recursion is when we have successfully colored all cells (e.g., when `row == m`). At this point, we've found one valid way, so we increment our answer.

In the recursive step for `solve(row, col)`, we iterate through the three colors (Red, Green, Blue). For each color, we check if placing it at `(row, col)` is valid. A color is valid if it's different from the color of the cell `(row-1, col)` (if `row > 0`) and the cell `(row, col-1)` (if `col > 0`).

If the color is valid, we place it in the grid and recursively call the function for the next cell. After the recursive call returns, we effectively "backtrack" by trying the next color for the current cell. This method explores the entire search space of colorings, pruning branches that violate the adjacency constraint as soon as they are detected.

```java
class Solution {
    int m, n;
    long count = 0;
    int MOD = 1_000_000_007;
    int[][] grid;

    public int colorTheGrid(int m, int n) {
        this.m = m;
        this.n = n;
        // This approach will time out, but illustrates the concept.
        // A real solution would not use this for the given constraints.
        this.grid = new int[m][n]; // 1:Red, 2:Green, 3:Blue
        backtrack(0, 0);
        return (int) count;
    }

    private void backtrack(int row, int col) {
        if (row == m) {
            count = (count + 1) % MOD;
            return;
        }

        int nextRow = row;
        int nextCol = col + 1;
        if (nextCol == n) {
            nextRow = row + 1;
            nextCol = 0;
        }

        for (int color = 1; color <= 3; color++) {
            if (isSafe(row, col, color)) {
                grid[row][col] = color;
                backtrack(nextRow, nextCol);
            }
        }
    }

    private boolean isSafe(int row, int col, int color) {
        // Check top neighbor
        if (row > 0 && grid[row - 1][col] == color) {
            return false;
        }
        // Check left neighbor
        if (col > 0 && grid[row][col - 1] == color) {
            return false;
        }
        return true;
    }
}
```
### Algorithm
- Create a recursive function `backtrack(row, col)`.
- If `row == m`, a valid grid coloring is found. Increment the total count (modulo `10^9 + 7`) and return.
- Determine the next cell `(next_row, next_col)`. If `col + 1 == n`, the next cell is `(row + 1, 0)`; otherwise, it's `(row, col + 1)`.
- Iterate through the 3 colors for the current cell `(row, col)`.
- Check if the chosen color is valid by comparing it with the color of the cell above (`grid[row-1][col]`) and to the left (`grid[row][col-1]`).
- If the color is valid, assign it to `grid[row][col]` and make a recursive call: `backtrack(next_row, next_col)`.
- After the recursive call returns, backtrack by resetting the cell's color to explore other possibilities (though this is implicitly handled by overwriting in the loop).

## Dynamic Programming with Column State Compression
This approach leverages the small constraint on `m` (number of rows). Instead of coloring cell by cell, we color the grid column by column. The state of our dynamic programming is the coloring pattern of a single column. Since `m` is small, the number of valid column colorings is also small. We can then calculate the number of ways to color `n` columns based on the transitions between these valid column states.
**Time:** O(S^2 * n + 3^m * m), where `S` is the number of valid column states (`S <= 3 * 2^(m-1)`). The `3^m * m` part is for generating states, and `S^2 * n` is for the DP calculation. Since `m` is small, `S` is a small constant, making the complexity effectively O(n). · **Space:** O(S^2), where `S` is the number of states. We need `O(S^2)` to store the compatibility map/matrix and `O(S)` for the DP arrays. For `m=5`, `S=48`, so this is constant space.
**Pros:** Highly efficient for the given constraints, reducing the complexity from being exponential in `m*n` to linear in `n`.; The number of states `S` is small and constant for a fixed `m`.
**Cons:** More complex to implement than backtracking.; The state generation and compatibility check logic requires careful implementation.
### Explanation
**State Definition:** A "state" is a valid coloring of a single column of height `m`. A coloring is valid if no two vertically adjacent cells have the same color. We can represent each state as an integer using a base-3 encoding (e.g., color {1,2,3} -> digit {0,1,2}). For `m=5`, there are only 48 such states.

**State Transition:** We define a compatibility relationship between states. Two states `stateA` and `stateB` are compatible if `stateB` can be placed immediately to the right of `stateA`. This means for every row `i`, the color of cell `i` in `stateA` must be different from the color of cell `i` in `stateB`. We can pre-compute and store these compatibilities in a graph or an adjacency matrix.

**DP Formulation:** Let `dp[i][state]` be the number of ways to color the first `i` columns such that the `i`-th column has the coloring `state`. The recurrence is `dp[i][state_curr] = sum(dp[i-1][state_prev])` for all `state_prev` compatible with `state_curr`. Since `dp[i]` only depends on `dp[i-1]`, we can optimize space to `O(S)` by using only two arrays representing the previous and current columns' DP values.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    int MOD = 1_000_000_007;

    public int colorTheGrid(int m, int n) {
        List<Integer> states = new ArrayList<>();
        generateStates(m, 0, 0, states);
        int numStates = states.size();
        
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int i = 0; i < numStates; i++) {
            for (int j = 0; j < numStates; j++) {
                if (areCompatible(states.get(i), states.get(j), m)) {
                    adj.computeIfAbsent(i, k -> new ArrayList<>()).add(j);
                }
            }
        }

        long[] dp = new long[numStates];
        for (int i = 0; i < numStates; i++) {
            dp[i] = 1;
        }

        for (int col = 1; col < n; col++) {
            long[] newDp = new long[numStates];
            for (int i = 0; i < numStates; i++) {
                if (adj.containsKey(i)) {
                    for (int neighbor : adj.get(i)) {
                        newDp[neighbor] = (newDp[neighbor] + dp[i]) % MOD;
                    }
                }
            }
            dp = newDp;
        }

        long totalWays = 0;
        for (long count : dp) {
            totalWays = (totalWays + count) % MOD;
        }
        return (int) totalWays;
    }

    private void generateStates(int m, int row, int currentState, List<Integer> states) {
        if (row == m) {
            states.add(currentState);
            return;
        }
        for (int color = 1; color <= 3; color++) {
            if (row > 0) {
                int prevColor = 1 + (currentState / (int) Math.pow(3, row - 1)) % 3;
                if (color == prevColor) continue;
            }
            generateStates(m, row + 1, currentState + (color - 1) * (int) Math.pow(3, row), states);
        }
    }

    private boolean areCompatible(int state1, int state2, int m) {
        for (int i = 0; i < m; i++) {
            if ((state1 / (int) Math.pow(3, i)) % 3 == (state2 / (int) Math.pow(3, i)) % 3) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- **State Generation:** Use a recursive helper function to generate all valid colorings for a single column of height `m`. A column is valid if no two vertically adjacent cells have the same color. Represent each unique coloring (a "state") as an integer.
- **Compatibility Mapping:** Create a data structure (e.g., an adjacency list or matrix) to store which pairs of states are compatible. Two states can be placed in adjacent columns if all corresponding cells have different colors.
- **DP Initialization:** Create a DP array, `dp`, of size equal to the number of states `S`. Initialize `dp[j] = 1` for all states `j`, representing the ways to color the first column.
- **DP Iteration:** Loop from the second column to the `n`-th column (`i` from 1 to `n-1`):
    - Create a new DP array `new_dp` of size `S`, initialized to zeros.
    - For each state `s_curr` from 0 to `S-1`:
        - Iterate through all states `s_prev` that are compatible with `s_curr`.
        - Add `dp[s_prev]` to `new_dp[s_curr]`, taking the result modulo `10^9 + 7`.
    - After iterating through all states, update `dp = new_dp`.
- **Final Result:** Sum all values in the final `dp` array to get the total number of ways.

## Dynamic Programming with Matrix Exponentiation
This is an optimization over the standard DP approach. The column-to-column transition in the DP can be viewed as a linear transformation represented by a transition matrix. Instead of iterating `n-1` times to compute the result for the `n`-th column, we can use binary exponentiation (also known as exponentiation by squaring) to raise the transition matrix to the power of `n-1`. This reduces the time complexity's dependency on `n` from linear to logarithmic.
**Time:** O(S^3 * log n + S^2 * m). `S^2 * m` is for building the transition matrix and `S^3 * log n` is for the matrix exponentiation. Since `S` is a constant determined by `m`, this is effectively O(log n). · **Space:** O(S^2) to store the matrices required for the computation. Since `S` is a constant based on `m`, this is constant space.
**Pros:** Asymptotically the fastest approach for large `n`.; Reduces the time complexity with respect to `n` from linear to logarithmic.; A powerful and general technique for solving problems with linear recurrences.
**Cons:** Implementation is more complex, requiring matrix multiplication and binary exponentiation logic.; The constant factor is larger due to the `S^3` term in matrix multiplication. For small `n`, the iterative DP might be faster in practice.
### Explanation
The core idea is that the DP state transition `dp_k = dp_{k-1} * T` is a linear recurrence, where `dp_k` is a vector of counts for each state at column `k` and `T` is the transition matrix. To get from the first column to the `n`-th, we apply this transformation `n-1` times: `dp_n = dp_1 * T^(n-1)`. The most computationally intensive part is calculating `T^(n-1)`, which can be done efficiently.

**Binary Exponentiation for Matrices:** This algorithm computes matrix powers in logarithmic time. To compute `T^k`, if `k` is even, we compute `T^(k/2)` and square it. If `k` is odd, we compute `T^(k-1)` and multiply by `T`. This recursive structure leads to `O(log k)` matrix multiplications.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    long MOD = 1_000_000_007;

    public int colorTheGrid(int m, int n) {
        List<Integer> states = new ArrayList<>();
        generateStates(m, 0, 0, states);
        int numStates = states.size();

        long[][] transitionMatrix = new long[numStates][numStates];
        for (int i = 0; i < numStates; i++) {
            for (int j = 0; j < numStates; j++) {
                if (areCompatible(states.get(i), states.get(j), m)) {
                    transitionMatrix[i][j] = 1;
                }
            }
        }

        if (n == 1) return numStates;

        long[][] resultMatrix = matrixPower(transitionMatrix, n - 1);

        long totalWays = 0;
        // Initial vector is all 1s, so we sum all elements of the final matrix
        for (int i = 0; i < numStates; i++) {
            for (int j = 0; j < numStates; j++) {
                totalWays = (totalWays + resultMatrix[i][j]) % MOD;
            }
        }
        return (int) totalWays;
    }

    private long[][] matrixPower(long[][] base, int exp) {
        int size = base.length;
        long[][] result = new long[size][size];
        for (int i = 0; i < size; i++) result[i][i] = 1; // Identity matrix
        
        while (exp > 0) {
            if (exp % 2 == 1) result = multiplyMatrices(result, base);
            base = multiplyMatrices(base, base);
            exp /= 2;
        }
        return result;
    }

    private long[][] multiplyMatrices(long[][] a, long[][] b) {
        int size = a.length;
        long[][] result = new long[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                for (int k = 0; k < size; k++) {
                    result[i][j] = (result[i][j] + a[i][k] * b[k][j]) % MOD;
                }
            }
        }
        return result;
    }
    
    // generateStates and areCompatible methods are the same as in the previous approach.
    private void generateStates(int m, int row, int currentState, List<Integer> states) {
        if (row == m) {
            states.add(currentState);
            return;
        }
        for (int color = 1; color <= 3; color++) {
            if (row > 0) {
                int prevColor = 1 + (currentState / (int) Math.pow(3, row - 1)) % 3;
                if (color == prevColor) continue;
            }
            generateStates(m, row + 1, currentState + (color - 1) * (int) Math.pow(3, row), states);
        }
    }

    private boolean areCompatible(int state1, int state2, int m) {
        for (int i = 0; i < m; i++) {
            if ((state1 / (int) Math.pow(3, i)) % 3 == (state2 / (int) Math.pow(3, i)) % 3) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- **State Generation:** Generate all `S` valid column states, same as the previous DP approach.
- **Transition Matrix:** Build an `S x S` transition matrix `T`. Set `T[i][j] = 1` if state `i` is compatible with state `j` (meaning state `j` can follow state `i`), and `0` otherwise.
- **Matrix Power:** The number of ways to color `n` columns is related to the `(n-1)`-th power of the transition matrix. Compute `T_final = T^(n-1)` using binary exponentiation for matrices. This involves repeatedly squaring the matrix and multiplying, which takes `O(log n)` matrix multiplications.
- **Matrix Multiplication:** Implement a function to multiply two `S x S` matrices, which takes `O(S^3)` time.
- **Final Result:** The initial state vector (for the first column) is a vector of all 1s. The total number of ways is the sum of all elements in the resulting matrix `T_final`. This is because `sum(dp_n) = sum(dp_1 * T^(n-1)) = sum( (1,1,...) * T^(n-1) ) = sum_{i,j} (T^(n-1))_{ij}`.

# Solutions
### Java

```java
class Solution {
private
  int m;
public
  int colorTheGrid(int m, int n) {
    this.m = m;
    final int mod = (int)1 e9 + 7;
    int mx = (int)Math.pow(3, m);
    Set<Integer> valid = new HashSet<>();
    int[] f = new int[mx];
    for (int i = 0; i < mx; ++i) {
      if (f1(i)) {
        valid.add(i);
        f[i] = 1;
      }
    }
    Map<Integer, List<Integer>> d = new HashMap<>();
    for (int i : valid) {
      for (int j : valid) {
        if (f2(i, j)) {
          d.computeIfAbsent(i, k->new ArrayList<>()).add(j);
        }
      }
    }
    for (int k = 1; k < n; ++k) {
      int[] g = new int[mx];
      for (int i : valid) {
        for (int j : d.getOrDefault(i, List.of())) {
          g[i] = (g[i] + f[j]) % mod;
        }
      }
      f = g;
    }
    int ans = 0;
    for (int x : f) {
      ans = (ans + x) % mod;
    }
    return ans;
  }
private
  boolean f1(int x) {
    int last = -1;
    for (int i = 0; i < m; ++i) {
      if (x % 3 == last) {
        return false;
      }
      last = x % 3;
      x /= 3;
    }
    return true;
  }
private
  boolean f2(int x, int y) {
    for (int i = 0; i < m; ++i) {
      if (x % 3 == y % 3) {
        return false;
      }
      x /= 3;
      y /= 3;
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int colorTheGrid(int m, int n) {
    auto f1 = [&](int x) {
      int last = -1;
      for (int i = 0; i < m; ++i) {
        if (x % 3 == last) {
          return false;
        }
        last = x % 3;
        x /= 3;
      }
      return true;
    };
    auto f2 = [&](int x, int y) {
      for (int i = 0; i < m; ++i) {
        if (x % 3 == y % 3) {
          return false;
        }
        x /= 3;
        y /= 3;
      }
      return true;
    };
    const int mod = 1e9 + 7;
    int mx = pow(3, m);
    unordered_set<int> valid;
    vector<int> f(mx);
    for (int i = 0; i < mx; ++i) {
      if (f1(i)) {
        valid.insert(i);
        f[i] = 1;
      }
    }
    unordered_map<int, vector<int>> d;
    for (int i : valid) {
      for (int j : valid) {
        if (f2(i, j)) {
          d[i].push_back(j);
        }
      }
    }
    for (int k = 1; k < n; ++k) {
      vector<int> g(mx);
      for (int i : valid) {
        for (int j : d[i]) {
          g[i] = (g[i] + f[j]) % mod;
        }
      }
      f = move(g);
    }
    int ans = 0;
    for (int x : f) {
      ans = (ans + x) % mod;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def colorTheGrid(self, m: int, n: int) -> int: def f1(x: int) -> bool: last = - 1 for _ in range(m): if x % 3 == last: return False last = x % 3 x //= 3 return True def f2(x: int, y: int) -> bool: for _ in range(m): if x % 3 == y % 3: return False x, y = x // 3, y // 3 return True mod = 10 ** 9 + 7 mx = 3 ** m valid = {i for i in range(mx) if f1(i)} d = defaultdict(list) for x in valid: for y in valid: if f2(x, y): d[x]. append(y) f = [int(i in valid) for i in range(mx)] for _ in range(n - 1): g = [0] * mx for i in valid: for j in d[i]: g[i] = (g[i] + f[j]) % mod f = g return sum(f) % mod

```