Number of Ways to Paint N × 3 Grid

Hard
887.

Number of Ways to Paint N × 3 Grid

Number of Ways to Paint N × 3 Grid is a hard coding problem on dynamic programming, asked in Amazon, Google, Adobe and Intuit interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var numOfWays = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Number of Ways to Paint N × 3 Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Number of Ways to Paint N × 3 Grid is a hard coding problem on dynamic programming, asked in Amazon, Google, Adobe and Intuit interviews.

  • Difficulty: Hard
  • Topics: Dynamic Programming
  • Asked at: Amazon, Google, Adobe, Intuit
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Number of Ways to Paint N × 3 Grid

  1. Hint 1

    Classify each row by its shape, not its exact colours: either the two ends match (ABA) or all three differ (ABC).

  2. Hint 2

    There are 6 colourings of each shape.

  3. Hint 3

    Count how many valid next rows each shape allows — it depends only on the shape.

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

Java

public static int numOfWays(int n) {
    final long MOD = 1000000007L;
    long two = 6, three = 6;
    for (int i = 2; i <= n; i++) {
        long nt = (two * 3 + three * 2) % MOD;
        long nh = (two * 2 + three * 2) % MOD;
        two = nt;
        three = nh;
    }
    return (int) ((two + three) % MOD);
}

C++

int numOfWays(int n) {
    const long long MOD = 1000000007LL;
    long long two = 6, three = 6;
    for (int i = 2; i <= n; i++) {
        long long nt = (two * 3 + three * 2) % MOD;
        long long nh = (two * 2 + three * 2) % MOD;
        two = nt;
        three = nh;
    }
    return (int) ((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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming