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 rows1 <= n <= 5000
Hints for Number of Ways to Paint N × 3 Grid
Hint 1
Classify each row by its shape, not its exact colours: either the two ends match (
ABA) or all three differ (ABC).Hint 2
There are 6 colourings of each shape.
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
- Start with 6 rows of each shape for
n = 1. - An
ABArow admits 3ABAsuccessors and 2ABCones; anABCrow admits 2 of each. - Iterate
two' = 3·two + 2·three,three' = 2·two + 2·threefor each further row. - 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 → ABAis 3 whileABC → ABCis 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) % MODJava
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