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 horizont

numOfWays.js

/**
 * @param {number} n
 * @return {number}
 */
var numOfWays = function(n) {
    const MOD = 1_000_000_007;

    // a = number of ABC patterns for the current row
    // b = number of ABA patterns for the current row
    let a = 6;  // ABC has 6 permutations
    let b = 6;  // ABA also 6 valid patterns

    // Build row by row using the recurrence
    for (let i = 2; i <= n; i++) {
        // Compute next row counts based on transitions
        let nextA = (2 * a + 2 * b) % MOD;  // ABC -> ABC or ABA
        let nextB = (2 * a + 3 * b) % MOD;  // ABA -> ABC or ABA

        // Move forward
        a = nextA;
        b = nextB;
    }

    // Total valid colorings = ABC patterns + ABA patterns
    return (a + b) % MOD;
};