Problem Analysis

Given an n x 3 grid, each cell must be colored with one of three colors (red, yellow, green) such that adjacent cells (sharing horizontal or vertical edges) have different colors. The goal is to count the total number of valid colorings modulo 10^9 + 7.

For a single row (n = 1), there are 12 valid colorings. As n increases, the number grows exponentially, requiring an efficient dynamic programming approach.

Pattern Classification

Each row can be classified into two types of color patterns:

1. ABA patterns: Patterns where the first and third colors are identical (e.g., red-yellow-red)
2. ABC patterns: Patterns where all three colors are distinct (e.g., red-yellow-green)

For n = 1:

• ABA patterns: 6 valid arrangements
• ABC patterns: 6 valid arrangements

Transition Analysis

From one row to the next, the number of valid transitions depends on the current pattern type:

• From ABA pattern:

  • Can generate 3 new ABA patterns
  • Can generate 2 new ABC patterns

• From ABC pattern:

  • Can generate 2 new ABA patterns
  • Can generate 2 new ABC patterns

Dynamic Programming Implementation

const MOD = 1000000007;

function countGridColorings(n) {
    if (n === 0) return 0;
    
    let abaCount = 6;  // ABA type patterns
    let abcCount = 6;  // ABC type patterns
    
    for (let i = 2; i <= n; i++) {
        const nextABA = (abaCount * 3 + abcCount * 2) % MOD;
        const nextABC = (abaCount * 2 + abcCount * 2) % MOD;
        
        abaCount = nextABA;
        abcCount = nextABC;
    }
    
    return (abaCount + abcCount) % MOD;
}

Alternative Matrix Representation

function countGridColoringsMatrix(n) {
    if (n === 0) return 0;
    
    const state = [[6], [6]];  // [ABA_count, ABC_count]
    const transition = [
        [3, 2],  // From ABA: to ABA, to ABC
        [2, 2]   // From ABC: to ABA, to ABC
    ];
    
    for (let i = 1; i < n; i++) {
        const newABA = (transition[0][0] * state[0][0] + transition[1][0] * state[1][0]) % MOD;
        const newABC = (transition[0][1] * state[0][0] + transition[1][1] * state[1][0]) % MOD;
        
        state[0][0] = newABA;
        state[1][0] = newABC;
    }
    
    return (state[0][0] + state[1][0]) % MOD;
}

Complexity Analysis

• Time Complexity: O(n) - Single pass through all rows
• Space Complexity: O(1) - Constant space for tracking two state variables

The solution efficiently computes the result by tracking only the counts of the two pattern types from the previous row, avoiding the need to store all possible configurations.