Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A valid three-cell row uses either two colors in an ABA pattern or three different colors in an ABC pattern. Symmetry makes all rows of the same type have identical transition counts, so individual color arrangements need not be stored.

Approach

Initialize both type counts to six for the first row. Each ABA row allows three compatible ABA successors and two ABC successors; each ABC row allows two of each. Thus compute the new counts as 3*aba + 2*abc and 2*aba + 2*abc, using the old counts for both updates. Apply modulo 10^9 + 7 each row and return the sum of the two final counts modulo the same value.

class Solution:
    def numOfWays(self, n: int) -> int:
        MOD = 10**9 + 7
        aba = 6
        abc = 6

        for i in range(1, n):
            new_aba = (aba * 3 + abc * 2) % MOD
            new_abc = (aba * 2 + abc * 2) % MOD
            aba = new_aba
            abc = new_abc

        return (aba + abc) % MOD

Complexity analysis

The two compressed row-pattern states are updated once for each of n rows. Time is O(n) and auxiliary space is O(1).