Number of Ways to Paint N × 3 Grid — Hard Problem & Solution

Problem statement

Paint every cell of an n × 3 grid Red, Yellow or Green so that no two adjacent cells (sharing a side) have the same colour.

Return the number of ways, modulo 10^9 + 7.

Example 1

Input: n = 1
Output: 12
Explanation: Six patterns use two colours (like RYR) and six use three (like RYG).

Example 2

Input: n = 2
Output: 54

Example 3

Input: n = 3
Output: 246

Constraints

• n == the number of rows
• 1 <= n <= 5000

How to solve Number of Ways to Paint N × 3 Grid

The only thing a row imposes on the next one is its pattern of equalities, and there are just two: ABA (ends equal) and ABC (all distinct). Counting transitions between those two classes collapses the whole problem to a two-term recurrence.

Approach

1. Start with 6 rows of each shape for n = 1.
2. An ABA row admits 3 ABA successors and 2 ABC ones; an ABC row admits 2 of each.
3. Iterate two' = 3·two + 2·three, three' = 2·two + 2·three for each further row.
4. The answer is the sum of the two counts.

Why it works

Two rows are compatible when no column matches, which depends only on the equality patterns — the specific colours never change the count of compatible successors. Enumerating the four transition counts by hand once is enough, and the recurrence then runs in linear time with constant state.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Treating the 12 colourings individually needs a 12 × 12 transition table — correct but far more work.
• The transition counts are not symmetric: ABA → ABA is 3 while ABC → ABC is 2.
• Reduce modulo at every step; the counts grow exponentially.

Reference solution

Python

def numOfWays(n: int) -> int:
    MOD = 1000000007
    two = three = 6
    for _ in range(2, n + 1):
        two, three = (two * 3 + three * 2) % MOD, (two * 2 + three * 2) % MOD
    return (two + three) % MOD

JavaScript

var numOfWays = function(n) {
    var MOD = 1000000007;
    var two = 6, three = 6;
    for (var i = 2; i <= n; i++) {
        var nt = (two * 3 + three * 2) % MOD;
        var nh = (two * 2 + three * 2) % MOD;
        two = nt;
        three = nh;
    }
    return (two + three) % MOD;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Count Ways to Make Array With Product Hard
• Count the Number of Ideal Arrays Hard
• Number of Ways to Rearrange Sticks With K Sticks Visible Hard
• The Number of Good Subsets Hard
• Number of Ways to Reorder Array to Get Same BST Hard
• Make Array Strictly Increasing Hard