Number of Ways to Paint an N × 3 Grid — 2-state DP (ABA vs ABC)

In this problem, we paint an n × 3 grid using three colors (e.g., R/Y/G) such that no two adjacent cells (horizontally or vertically) share the same color. The answer is computed modulo 1e9+7.

Why this becomes “two row types”

For a single 3-cell row, with the “no equal horizontal neighbors” constraint, every valid coloring falls into exactly one of two types:

• ABA — uses 2 colors; the 1st and 3rd cells match (e.g., R Y R)
• ABC — uses 3 distinct colors (e.g., R Y G)

There are no other cases:

• AAB is invalid (cells 1–2 equal),
• ABB is invalid (cells 2–3 equal),
• AAA is obviously invalid.

Visual: the two row types

How many ways for the first row

We have 3 colors.

• ABA: choose A (3 ways), then choose B != A (2 ways) → 3 × 2 = 6
• ABC: a permutation of three distinct colors → 3! = 6

So for n = 1 the total is 6 + 6 = 12 (as in the statement examples).

Key idea: transitions depend only on the type (ABA/ABC), not on specific colors

We do not need to remember whether the row was (R,Y,R) or (G,R,G). It is enough to know whether the row is ABA or ABC.

Define:

• a[i] — number of ways to paint i rows where the i-th row is of type ABA
• b[i] — number of ways to paint i rows where the i-th row is of type ABC

Initialization:

• a[1] = 6
• b[1] = 6

Where the coefficients 3,2,2,2 come from

We count how many rows of each type can be placed directly under a row of a given type while respecting the vertical constraint (same column must differ).

• Under an ABA row, you can place:

  • 3 rows of type ABA
  • 2 rows of type ABC

• Under an ABC row, you can place:

  • 2 rows of type ABA
  • 2 rows of type ABC

Short intuition:

• For ABA → ABC: since the top row’s ends are the same color, in an ABC row that color must go in the middle to avoid vertical conflicts, leaving exactly 2 valid permutations.
• For ABC → ABC: this is the number of derangements of 3 items (no color stays in the same column), which is 2.

This yields the recurrence:

• a[i] = 3*a[i-1] + 2*b[i-1]
• b[i] = 2*a[i-1] + 2*b[i-1]

Simple implementation (O(1) memory)

We keep only two counters: a and b, representing a[i-1] and b[i-1] in each iteration.

class Solution {
public:
    int numOfWays(int n) {
        constexpr int MOD = 1'000'000'007;

        long long a = 6; // ABA
        long long b = 6; // ABC

        for (int i = 2; i <= n; ++i) {
            long long na = (3*a + 2*b) % MOD;
            long long nb = (2*a + 2*b) % MOD;
            a = na;
            b = nb;
        }

        return (a + b) % MOD;
    }
};