1411. Number of Ways to Paint N × 3 Grid

Description

You are given an n x 3 grid, and you need to paint each cell with one of three colors: Red, Yellow, or Green. The constraint is that no two adjacent cells (sharing a horizontal or vertical side) can have the same color. Find the number of ways to paint the grid, modulo 109 + 7.

Solutions

Solution 1: Matrix Exponentiation (Optimal)

This solution leverages the concept of matrix exponentiation to efficiently calculate the number of ways to color the grid. The core idea is to represent the state transitions between rows as a matrix and then use exponentiation to quickly compute the state after 'n' rows.

Approach:

1. State Representation: We can represent the coloring of a row using a 3-digit ternary number (base-3). Each digit represents the color of a cell (0, 1, or 2). However, only valid colorings (no adjacent cells with the same color) are considered.

2. Transition Matrix: A transition matrix T is created where T[i][j] represents the number of ways to transition from a valid coloring i in one row to a valid coloring j in the next row.

3. Matrix Exponentiation: To find the number of ways after n rows, we raise the transition matrix to the power of n - 1 (since the first row has initial coloring possibilities). This can be done efficiently using exponentiation by squaring.

4. Final Calculation: The sum of all elements in the resulting matrix's first row represents the total number of ways to color the entire grid.

Time Complexity: O(k3 log n), where k is the number of valid colorings (less than 27). Matrix multiplication is O(k3), and exponentiation by squaring takes log n steps.

Space Complexity: O(k2) to store the transition matrix.

Code (Python):

MOD = 10**9 + 7
 
def numOfWays(n: int) -> int:
    valid_colorings = [
        0b010, 0b012, 0b020, 0b021, 0b101, 0b102, 0b120, 0b121,
        0b201, 0b202, 0b210, 0b212
    ]
    k = len(valid_colorings)
    transition_matrix = [[0] * k for _ in range(k)]
    for i in range(k):
        for j in range(k):
            c1 = valid_colorings[i]
            c2 = valid_colorings[j]
            valid = True
            for bit in range(3):
                if (c1 >> bit) & 1 == (c2 >> bit) & 1:
                    valid = False
                    break
                if bit > 0 and (c1 >> (bit - 1)) & 1 == (c2 >> bit) & 1:
                    valid = False
                    break
            if valid:
                transition_matrix[i][j] = 1
                
 
    def matrix_mult(A, B):
        C = [[0] * k for _ in range(k)]
        for i in range(k):
            for j in range(k):
                for l in range(k):
                    C[i][j] = (C[i][j] + A[i][l] * B[l][j]) % MOD
        return C
 
    def matrix_pow(A, n):
        res = [[int(i == j) for j in range(k)] for i in range(k)]
        while n > 0:
            if n % 2 == 1:
                res = matrix_mult(res, A)
            A = matrix_mult(A, A)
            n //= 2
        return res
 
    result_matrix = matrix_pow(transition_matrix, n - 1)
    total_ways = sum(sum(row) for row in result_matrix)
    return total_ways

Code (Java): (Similar approach using matrix exponentiation. Implementation details differ slightly but the core algorithm is the same.)

class Solution {
    public int numOfWays(int n) {
        long[][] base = {{3, 2},{2,3}};
        long[][] res = {{1,0},{0,1}};
        long mod = 1000000007;
        n--;
        while(n>0){
            if(n%2 == 1) res = multiply(res, base, mod);
            base = multiply(base, base, mod);
            n/=2;
        }
        long ans = (6*res[0][0] + 6*res[0][1])%mod;
        return (int) ans;
    }
    public long[][] multiply(long[][] a, long[][] b, long mod){
        long[][] c = new long[2][2];
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                for(int k=0;k<2;k++){
                    c[i][j] = (c[i][j] + a[i][k]*b[k][j])%mod;
                }
            }
        }
        return c;
    }
}
 

Solution 2: Dynamic Programming (Less Efficient)

This approach uses dynamic programming, but it's less efficient than matrix exponentiation for larger values of n.

Approach:

We can use dynamic programming with a state representation similar to the matrix exponentiation approach. The state would include the coloring of the previous row. The complexity grows exponentially with n because the number of possible states increases rapidly.

Time Complexity: O(exponential) - this method is not efficient for large n.

Space Complexity: O(exponential)

This solution is not recommended for large n because of its exponential time and space complexity. The matrix exponentiation approach is far superior in terms of efficiency.