# Number of Ways to Paint N × 3 Grid
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-to-paint-n-3-grid
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [Fortinet](https://scaleengineer.com/companies/fortinet)
---
## Problem
You have a `grid` of size `n x 3` and you want to paint each cell of the grid with exactly one of the three colors: **Red**, **Yellow,** or **Green** while making sure that no two adjacent cells have the same color (i.e., no two cells that share vertical or horizontal sides have the same color).

Given `n` the number of rows of the grid, return _the number of ways_ you can paint this `grid`. As the answer may grow large, the answer **must be** computed modulo `109 + 7`.

**Example 1:**

![](https://assets.glich.co/dsa/number-of-ways-to-paint-n-3-grid/image0.png) 

**Input:** n = 1
**Output:** 12
**Explanation:** There are 12 possible way to paint the grid as shown.

**Example 2:**

**Input:** n = 5000
**Output:** 30228214

**Constraints:**

* `n == grid.length`
* `1 <= n <= 5000`

# Approaches
## Dynamic Programming with O(n) Space
This problem has optimal substructure and overlapping subproblems, making it a perfect candidate for dynamic programming. The core idea is that the number of ways to color any given row `i` depends solely on the valid colorings of the previous row, `i-1`.

First, we analyze the valid colorings for a single row. A row has 3 cells, and adjacent cells must have different colors. This gives rise to two types of color patterns:
1.  **Two-Color Patterns (ABA type):** The first and third cells are the same color, while the middle cell is different (e.g., Red-Yellow-Red). There are `3` choices for the first color and `2` for the second, totaling `3 * 2 = 6` such patterns.
2.  **Three-Color Patterns (ABC type):** All three cells have different colors (e.g., Red-Yellow-Green). There are `3 * 2 * 1 = 6` such patterns.

For `n=1`, the total number of ways is `6 + 6 = 12`.
**Time:** O(n) - We perform a single loop from `i=2` to `n`, with constant time operations inside. · **Space:** O(n) - We use two arrays of size `n+1` to store the DP states for each row.
**Pros:** Conceptually straightforward and easy to follow.; Directly translates the recurrence relation into code.
**Cons:** Uses linear space, which is not optimal and can be improved.
### Explanation
We can build a DP solution based on these two pattern types. We'll define DP states to count the number of ways to paint the grid up to row `i` ending with each pattern type.

Let:
*   `twoColor[i]` be the number of ways to paint an `i x 3` grid where row `i` has a two-color (ABA) pattern.
*   `threeColor[i]` be the number of ways to paint an `i x 3` grid where row `i` has a three-color (ABC) pattern.

We can establish recurrence relations by analyzing how a pattern in row `i` can follow a pattern in row `i-1` without violating the color constraints.

*   **Transitions to a two-color pattern in row `i`:**
    *   From a two-color pattern in row `i-1`: There are 3 valid ways.
    *   From a three-color pattern in row `i-1`: There are 2 valid ways.
    *   Thus, `twoColor[i] = 3 * twoColor[i-1] + 2 * threeColor[i-1]`.

*   **Transitions to a three-color pattern in row `i`:**
    *   From a two-color pattern in row `i-1`: There are 2 valid ways.
    *   From a three-color pattern in row `i-1`: There are 2 valid ways.
    *   Thus, `threeColor[i] = 2 * twoColor[i-1] + 2 * threeColor[i-1]`.

The implementation involves creating two arrays to store these counts and iterating from `i=2` to `n` to fill them. The final result is the sum of the counts for row `n`.

```java
class Solution {
    public int numOfWays(int n) {
        if (n == 0) {
            return 0;
        }
        long MOD = 1_000_000_007;

        long[] twoColor = new long[n + 1];
        long[] threeColor = new long[n + 1];

        // Base case for n = 1
        twoColor[1] = 6;
        threeColor[1] = 6;

        for (int i = 2; i <= n; i++) {
            // Ways to form a two-color pattern in row i
            twoColor[i] = (3 * twoColor[i - 1] + 2 * threeColor[i - 1]) % MOD;
            // Ways to form a three-color pattern in row i
            threeColor[i] = (2 * twoColor[i - 1] + 2 * threeColor[i - 1]) % MOD;
        }

        return (int) ((twoColor[n] + threeColor[n]) % MOD);
    }
}
```
### Algorithm
*   Define two DP arrays, `twoColor` and `threeColor`, of size `n+1`.
*   `twoColor[i]` will store the number of ways to paint the first `i` rows with the `i`-th row having a two-color (ABA) pattern.
*   `threeColor[i]` will store the number of ways to paint the first `i` rows with the `i`-th row having a three-color (ABC) pattern.
*   Set the base cases for `i=1`: `twoColor[1] = 6` and `threeColor[1] = 6`.
*   Iterate from `i = 2` to `n` and apply the following recurrence relations:
    *   `twoColor[i] = (3 * twoColor[i-1] + 2 * threeColor[i-1]) % MOD`
    *   `threeColor[i] = (2 * twoColor[i-1] + 2 * threeColor[i-1]) % MOD`
*   The final answer is the sum of `twoColor[n]` and `threeColor[n]`, modulo `MOD`.

## Space-Optimized Dynamic Programming
The previous dynamic programming approach uses `O(n)` space, but we can notice that the calculation for the number of ways to color row `i` only requires the results from row `i-1`. There is no dependency on `i-2`, `i-3`, etc. This observation allows us to optimize the space complexity significantly.
**Time:** O(n) - The time complexity is determined by the single loop that runs `n-1` times. · **Space:** O(1) - We only use a fixed number of variables to store the previous state, regardless of `n`.
**Pros:** Extremely space-efficient, using only a constant amount of memory.; Maintains the simplicity and `O(n)` time efficiency of the DP approach.; Very practical and fast for the given problem constraints.
**Cons:** While efficient for the given constraints, the time complexity is still linear, which could be too slow for extremely large `n`.
### Explanation
Instead of storing the entire history of counts in arrays, we only need to maintain the counts for the most recently computed row. We can use a few variables to store the state of the previous row and use them to compute the state for the current row.

We start with the base case for `n=1`, where there are 6 ways for two-color patterns and 6 ways for three-color patterns. We then iterate from `2` to `n`, continuously updating these two counts based on the same recurrence relations as before. At each step `i`, the variables hold the counts for row `i-1`, and we compute the new counts for row `i`.

This iterative update process eliminates the need for DP arrays, reducing the space complexity to constant time.

```java
class Solution {
    public int numOfWays(int n) {
        if (n == 0) {
            return 0;
        }
        long MOD = 1_000_000_007;

        // Base case for n = 1
        long twoColorCount = 6;
        long threeColorCount = 6;

        for (int i = 2; i <= n; i++) {
            long nextTwoColor = (3 * twoColorCount + 2 * threeColorCount) % MOD;
            long nextThreeColor = (2 * twoColorCount + 2 * threeColorCount) % MOD;
            
            twoColorCount = nextTwoColor;
            threeColorCount = nextThreeColor;
        }

        return (int) ((twoColorCount + threeColorCount) % MOD);
    }
}
```
### Algorithm
*   Initialize two variables, `twoColorCount = 6` and `threeColorCount = 6`, representing the base case for `n=1`.
*   If `n=1`, return the sum `12`.
*   Loop from `i = 2` to `n`.
*   Inside the loop, use temporary variables to calculate the counts for the current row `i` based on the counts from the previous row (`twoColorCount` and `threeColorCount`).
    *   `nextTwoColor = (3 * twoColorCount + 2 * threeColorCount) % MOD`
    *   `nextThreeColor = (2 * twoColorCount + 2 * threeColorCount) % MOD`
*   Update the main count variables: `twoColorCount = nextTwoColor` and `threeColorCount = nextThreeColor`.
*   After the loop, return `(twoColorCount + threeColorCount) % MOD`.

## Matrix Exponentiation
For problems with linear recurrence relations, we can often find a more asymptotically efficient solution using matrix exponentiation. The DP state transitions can be represented by a matrix multiplication. 

The recurrence relations are:
`two_color[i] = 3 * two_color[i-1] + 2 * three_color[i-1]`
`three_color[i] = 2 * two_color[i-1] + 2 * three_color[i-1]`

This can be expressed in matrix form as:
`[ two_color[i] ] = [ 3  2 ] * [ two_color[i-1] ]`
`[ three_color[i] ]   [ 2  2 ]   [ three_color[i-1] ]`
**Time:** O(log n) - Dominated by the matrix exponentiation algorithm. Each 2x2 matrix multiplication takes constant time. · **Space:** O(1) - The space required for the matrices and calculations is constant.
**Pros:** The most asymptotically efficient solution in terms of time complexity.; Extremely fast for very large values of `n`.
**Cons:** More complex to understand and implement compared to the iterative DP solution.; The constant factors involved in matrix multiplication might make it slightly slower than the simple DP for small values of `n`.
### Explanation
Let `V[i]` be the state vector `[two_color[i], three_color[i]]^T` and `M` be the transition matrix `[[3, 2], [2, 2]]`. The relationship `V[i] = M * V[i-1]` implies that `V[n] = M^(n-1) * V[1]`.

The problem is now reduced to computing the `(n-1)`-th power of the matrix `M`. This can be done efficiently in `O(log n)` time using binary exponentiation for matrices. After computing `M^(n-1)`, we multiply it by the base state vector `V[1] = [6, 6]^T` to get the final counts for row `n`.

This method is significantly faster than the `O(n)` DP approach for very large values of `n` and represents the most optimal solution in terms of time complexity.

```java
class Solution {
    long MOD = 1_000_000_007;

    public int numOfWays(int n) {
        if (n == 1) {
            return 12;
        }

        // Transition matrix M
        long[][] M = {{3, 2}, {2, 2}};
        
        // Compute M^(n-1)
        long[][] M_pow = matrixPower(M, n - 1);

        // Initial state vector V[1] = [6, 6]
        long twoColor1 = 6;
        long threeColor1 = 6;

        // V[n] = M^(n-1) * V[1]
        long twoColorN = (M_pow[0][0] * twoColor1 + M_pow[0][1] * threeColor1) % MOD;
        long threeColorN = (M_pow[1][0] * twoColor1 + M_pow[1][1] * threeColor1) % MOD;

        return (int) ((twoColorN + threeColorN) % MOD);
    }

    // Computes A^p using binary exponentiation
    private long[][] matrixPower(long[][] A, int p) {
        long[][] res = {{1, 0}, {0, 1}}; // Identity matrix
        long[][] T = A;

        while (p > 0) {
            if ((p & 1) == 1) {
                res = multiply(res, T);
            }
            T = multiply(T, T);
            p >>= 1;
        }
        return res;
    }

    // Multiplies two 2x2 matrices
    private long[][] multiply(long[][] A, long[][] B) {
        long[][] C = new long[2][2];
        C[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD;
        C[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD;
        C[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD;
        C[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD;
        return C;
    }
}
```
### Algorithm
*   Handle the base case `n=1` separately.
*   Define the 2x2 transition matrix `M = {{3, 2}, {2, 2}}`.
*   Implement a function to multiply two 2x2 matrices, applying modulo at each step.
*   Implement a function to compute `M^k` using the binary exponentiation (exponentiation by squaring) algorithm. This will take `O(log k)` time.
*   Calculate `M_pow = M^(n-1)`.
*   The initial state vector for `n=1` is `V[1] = [6, 6]^T`.
*   Compute the final state `V[n] = M_pow * V[1]`.
*   The result is the sum of the elements in the resulting vector `V[n]`, modulo `MOD`.

# Solutions
### Java

```java
class Solution {
public
  int numOfWays(int n) {
    int mod = (int)1 e9 + 7;
    long f0 = 6, f1 = 6;
    for (int i = 0; i < n - 1; ++i) {
      long g0 = (3 * f0 + 2 * f1) % mod;
      long g1 = (2 * f0 + 2 * f1) % mod;
      f0 = g0;
      f1 = g1;
    }
    return (int)(f0 + f1) % mod;
  }
}

```

### CPP

```cpp
using ll = long long ; class Solution { public: int numOfWays ( int n ) { int mod = 1e9 + 7 ; ll f0 = 6 , f1 = 6 ; while ( -- n ) { ll g0 = ( f0 * 3 + f1 * 2 ) % mod ; ll g1 = ( f0 * 2 + f1 * 2 ) % mod ; f0 = g0 ; f1 = g1 ; } return ( int ) ( f0 + f1 ) % mod ; } };
```

### Python

```python
class Solution:
    def numOfWays(self, n: int) -> int: mod = 10 ** 9 + 7 f0 = f1 = 6 for _ in range(n - 1): g0 = (3 * f0 + 2 * f1) % mod g1 = (2 * f0 + 2 * f1) % mod f0, f1 = g0, g1 return (f0 + f1) % mod

```