1411. Number of Ways to Paint N × 3 Grid

Time: O(n)

Space: O(1)

Intuition

Count ways to paint n columns with 3 colors such that no two adjacent share the same color. Two types of rows: all-different (e.g. 121) and adjacent-same (e.g. 121 patterns with repeats).

Algorithm

1Track count of "end with two same" (ABA pattern) and "end with all different" (ABC pattern).
2Transitions: same*2 + diff*2 -> same. same*3 + diff*2 -> diff for 3 colors.

Common Pitfalls

•With 3 colors in 3 columns: patterns are either all-different (6 ways) or end-repeat like ABA (6 ways). Track transitions between these types.

1411.cs

// Approach: DP tracking count of rows using 2-color pattern vs 3-color pattern; transitions per row follow fixed multiplicative rules.
// Time: O(n) Space: O(1)

public class Solution
{
    public int NumOfWays(int n)
    {
        const int MOD = 1_000_000_007;
        long color2 = 6; // 121, 131, 212, 232, 313, 323
        long color3 = 6; // 123, 132, 213, 231, 312, 321

        for (int i = 1; i < n; ++i)
        {
            long nextColor2 = color2 * 3 + color3 * 2;
            long nextColor3 = color2 * 2 + color3 * 2;
            color2 = nextColor2 % MOD;
            color3 = nextColor3 % MOD;
        }

        return (int)((color2 + color3) % MOD);
    }
}

Was this solution helpful?