Number of Ways to Paint N × 3 Grid solution and explanation
Google
9 more videos on this problem
1411. Number of Ways to Paint N × 3 Grid | Leetcode Daily - PythonLeetcode Daily · 9:11 · 5K views
Number of Ways to Paint N × 3 Grid | LeetCode 1411 | Dynamic ProgrammingSanyam IIT Guwahati · 16:12 · 3K views
Number of Ways to Paint N×3 Grid | LeetCode 1411 | Recurrence Explained Study Placement · 21:31 · 2K views
Number of Ways to Paint N × 3 Grid | LeetCode 1411 | Dynamic ProgrammingcodeTips · 11:08 · 1K views
Daily Leetcode #2104: Jan 03, 2026 - 1411. Number of Ways to Paint N × 3 GridProgramming Live with Larry · 15:39 · 1K views
1411. Number of Ways to Paint N × 3 Grid | Recursion to tabular DP solution | C++Priyanshi Porwal · 19:51 · 681 views
Number of Ways to Paint N × 3 Grid | LeetCode 1411 | Java Code | Developer CoderDeveloper Coder · 32:28 · 309 views
Number of Ways to Paint Nx3 Grid - Leetcode 1411 - PythonTim Huang · 4:00 · 213 views
Number of Ways to Paint N×3 Grid | Solution Walkthrough | Dynamic Programming | Java | LeetCode 1411Mayank Modi · 19:37 · 131 views
1411. Number of Ways to Paint N × 3 Grid | Leetcode Daily ChallengeEye on AI and DSA · 23:15 · 99 views
The problem
You have a grid of size n x 3 and you want to paint each cell of the grid with exactly one of the three colors: Red, Yellow, or Green while making sure that no two adjacent cells have the same color (i.e., no two cells that share vertical or horizontal sides have the same color).
Given n the number of rows of the grid, return the number of ways you can paint this grid. As the answer may grow large, the answer must be computed modulo 109 + 7.
Example 1:
Input: n = 1 Output: 12 Explanation: There are 12 possible way to paint the grid as shown.
Example 2:
Input: n = 5000 Output: 30228214
Constraints:
n == grid.length1 <= n <= 5000
Approach overview
Problem Overview: You need to count how many ways an n × 3 grid can be painted using three colors such that no two adjacent cells share the same color. Adjacency applies both horizontally within a row and vertically between rows. The result must be returned modulo 1e9 + 7.
Approach 1: Dynamic Programming with Pattern States (O(n) time, O(1) space)
The key observation is that every valid row falls into one of two patterns: ABA (two colors) or ABC (three different colors). For the first row, there are 6 ways to create each pattern. While iterating row by row, compute how many new ABA and ABC rows can follow the previous patterns without breaking vertical color constraints. The transitions are simple linear relations: a previous ABA can generate both patterns in fixed counts, and the same applies for ABC. Track two integers (countABA, countABC) and update them for each row. This reduces the state space dramatically compared to enumerating all color combinations and is a classic example of state compression in dynamic programming. Time complexity is O(n) with constant O(1) space.
Approach 2: Matrix Exponentiation (O(log n) time, O(1) space)
The DP recurrence between rows is linear, which means it can be represented as a matrix transition. Define a vector [ABA, ABC] and multiply it by a fixed 2×2 transition matrix that encodes how patterns evolve from one row to the next. Instead of iterating n times, raise the transition matrix to the power n-1 using fast exponentiation. Each multiplication updates the pattern counts while preserving the adjacency rules. This converts the linear DP into logarithmic complexity and is a common optimization technique in matrix exponentiation problems involving recurrence relations.
Both approaches rely on recognizing repeating structural patterns rather than brute-force coloring of each cell. Instead of exploring 3^(3n) possibilities, the algorithm reduces the problem to just two state transitions derived from simple combinatorics.
Recommended for interviews: The dynamic programming state-compression approach is what interviewers expect. It demonstrates pattern recognition, recurrence building, and space optimization. Matrix exponentiation is a strong follow-up optimization when n can be extremely large and you want to reduce runtime from O(n) to O(log n).
Approach 1: Dynamic Programming Approach
In this approach, we establish a pattern-based system to manage the color arrangement of each row. We start by identifying two pattern types: 'Type A', where the row contains two colors across three cells (like RYR), and 'Type B', where all three cells have different colors (like RYG). The transformation of patterns from one row to the next depends on these types, forming distinct state transitions.
We use dynamic programming to keep track of the count formation of both types of patterns, updating these counts row by row until we reach 'n' rows. The final result is obtained by summing the number of possible patterns of Types A and B for a grid with 'n' rows.
def numOfWays(n: int) -> int:
a, b = 6, 6
mod = 1000000007
for _ in range(1, n):
a, b = (3 * a + 2 * b) % mod, (2 * a + 2 * b) % mod
return (a + b) % mod
print(numOfWays(5000))public class PaintGrid {
public int numOfWays(int n) {
long a = 6, b = 6;
long mod = 1000000007;
for (int i = 1; i < n; i++) {
long newA = (3 * a + 2 * b) % mod;
long newB = (2 * a + 2 * b) % mod;
a = newA;
b = newB;
}
return (int)((a + b) % mod);
}
public static void main(String[] args) {
PaintGrid pg = new PaintGrid();
System.out.println(pg.numOfWays(5000));
}
}#include <iostream>
#define MODULO 1000000007
int numOfWays(int n) {
long a = 6, b = 6;
for (int i = 1; i < n; i++) {
long new_a = (3 * a + 2 * b) % MODULO;
long new_b = (2 * a + 2 * b) % MODULO;
a = new_a;
b = new_b;
}
return (a + b) % MODULO;
}
int main() {
int n = 5000;
std::cout << numOfWays(n) << std::endl;
return 0;
}function numOfWays(n) {
let a = 6, b = 6;
const mod = 1000000007;
for (let i = 1; i < n; i++) {
[a, b] = [(3 * a + 2 * b) % mod, (2 * a + 2 * b) % mod];
}
return (a + b) % mod;
}
console.log(numOfWays(5000));#include <stdio.h>
#define MODULO 1000000007
int numOfWays(int n) {
long a = 6, b = 6;
for (int i = 1; i < n; i++) {
long new_a = (3 * a + 2 * b) % MODULO;
long new_b = (2 * a + 2 * b) % MODULO;
a = new_a;
b = new_b;
}
return (a + b) % MODULO;
}
int main() {
int n = 5000;
printf("%d\n", numOfWays(n));
return 0;
}using System;
public class PaintGrid {
public int NumOfWays(int n) {
long a = 6, b = 6;
long mod = 1000000007;
for (int i = 1; i < n; i++) {
long newA = (3 * a + 2 * b) % mod;
long newB = (2 * a + 2 * b) % mod;
a = newA;
b = newB;
}
return (int)((a + b) % mod);
}
public static void Main() {
PaintGrid pg = new PaintGrid();
Console.WriteLine(pg.NumOfWays(5000));
}
}The Python function mimics the dynamic pattern tracking with the iteration over row count. The tuple assignment neatly updates the patterns for each row iteration.
Time Complexity: O(n), because of the loop over rows.
Space Complexity: O(1), using a fixed set of variables for computation.
Approach 2: Matrix Exponentiation
This approach involves formulating the given problem as a matrix exponentiation problem, where the state transformations can be represented as matrix multiplications. This method is highly beneficial when pushing for rapid, logarithmic-time calculation concerning pattern transformations over many rows.
We define our transformation matrix based on pattern interdependencies: how Type A can transform into new Type A and B and vice versa, then compute this matrix's power to 'n' using fast exponentiation. This enables calculating the resulting pattern count efficiently.
def multiply(F, M):
x = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) % (10**9 + 7)
y = (F[0][0] * M[0][1] + F[0][1] * M[1][1]) % (10**9 + 7)
z = (F[1][0] * M[0][0] + F[1][1] * M[1][0]) % (10**9 + 7)
w = (F[1][0] * M[0][1] + F[1][1] * M[1][1]) % (10**9 + 7)
F[0][0] = x
F[0][1] = y
F[1][0] = z
F[1][1] = w
def power(F, n):
if n == 0 or n == 1:
return
M = [[3, 2], [2, 2]]
power(F, n // 2)
multiply(F, F)
if n % 2 != 0:
multiply(F, M)
def numOfWays(n: int) -> int:
if n == 1:
return 12
F = [[3, 2], [2, 2]]
power(F, n-1)
return (6 * F[0][0] + 6 * F[0][1]) % (10**9 + 7)
print(numOfWays(5000))public class PaintGrid {
static final int MODULO = 1000000007;
private void multiply(long[][] F, long[][] M) {
long x = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) % MODULO;
long y = (F[0][0] * M[0][1] + F[0][1] * M[1][1]) % MODULO;
long z = (F[1][0] * M[0][0] + F[1][1] * M[1][0]) % MODULO;
long w = (F[1][0] * M[0][1] + F[1][1] * M[1][1]) % MODULO;
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
private void power(long[][] F, int n) {
if (n == 0 || n == 1)
return;
long M[][] = {{3, 2}, {2, 2}};
power(F, n / 2);
multiply(F, F);
if (n % 2 != 0)
multiply(F, M);
}
public int numOfWays(int n) {
if (n == 1)
return 12;
long F[][] = {{3, 2}, {2, 2}};
power(F, n - 1);
return (int)((6 * F[0][0] + 6 * F[0][1]) % MODULO);
}
public static void main(String[] args) {
PaintGrid pg = new PaintGrid();
System.out.println(pg.numOfWays(5000));
}
}#include <iostream>
#define MODULO 1000000007
void multiply(long long F[2][2], long long M[2][2]) {
long long x = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) % MODULO;
long long y = (F[0][0] * M[0][1] + F[0][1] * M[1][1]) % MODULO;
long long z = (F[1][0] * M[0][0] + F[1][1] * M[1][0]) % MODULO;
long long w = (F[1][0] * M[0][1] + F[1][1] * M[1][1]) % MODULO;
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
void power(long long F[2][2], int n) {
if (n == 0 || n == 1)
return;
long long M[2][2] = {{3, 2}, {2, 2}};
power(F, n / 2);
multiply(F, F);
if (n % 2 != 0)
multiply(F, M);
}
int numOfWays(int n) {
if (n == 1)
return 12;
long long F[2][2] = {{3, 2}, {2, 2}};
power(F, n - 1);
return (int)((6 * F[0][0] + 6 * F[0][1]) % MODULO);
}
int main() {
std::cout << numOfWays(5000) << std::endl;
return 0;
}function multiply(F, M) {
const x = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) % (10**9 + 7);
const y = (F[0][0] * M[0][1] + F[0][1] * M[1][1]) % (10**9 + 7);
const z = (F[1][0] * M[0][0] + F[1][1] * M[1][0]) % (10**9 + 7);
const w = (F[1][0] * M[0][1] + F[1][1] * M[1][1]) % (10**9 + 7);
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
function power(F, n) {
if (n === 0 || n === 1) return;
const M = [[3, 2], [2, 2]];
power(F, Math.floor(n / 2));
multiply(F, F);
if (n % 2 !== 0) {
multiply(F, M);
}
}
function numOfWays(n) {
if (n === 1) return 12;
const F = [[3, 2], [2, 2]];
power(F, n - 1);
return (6 * F[0][0] + 6 * F[0][1]) % (10**9 + 7);
}
console.log(numOfWays(5000));#include <stdio.h>
#define MODULO 1000000007
void multiply(long long F[2][2], long long M[2][2]) {
long long x = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) % MODULO;
long long y = (F[0][0] * M[0][1] + F[0][1] * M[1][1]) % MODULO;
long long z = (F[1][0] * M[0][0] + F[1][1] * M[1][0]) % MODULO;
long long w = (F[1][0] * M[0][1] + F[1][1] * M[1][1]) % MODULO;
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
void power(long long F[2][2], int n) {
if (n == 0 || n == 1)
return;
long long M[2][2] = {{3, 2}, {2, 2}};
power(F, n / 2);
multiply(F, F);
if (n % 2 != 0)
multiply(F, M);
}
int numOfWays(int n) {
if (n == 1)
return 12;
long long F[2][2] = {{3, 2}, {2, 2}};
power(F, n - 1);
return (int)((6 * F[0][0] + 6 * F[0][1]) % MODULO);
}
int main() {
printf("%d\n", numOfWays(5000));
return 0;
}using System;
public class PaintGrid {
static readonly int MODULO = 1000000007;
private void Multiply(long[,] F, long[,] M) {
long x = (F[0, 0] * M[0, 0] + F[0, 1] * M[1, 0]) % MODULO;
long y = (F[0, 0] * M[0, 1] + F[0, 1] * M[1, 1]) % MODULO;
long z = (F[1, 0] * M[0, 0] + F[1, 1] * M[1, 0]) % MODULO;
long w = (F[1, 0] * M[0, 1] + F[1, 1] * M[1, 1]) % MODULO;
F[0, 0] = x;
F[0, 1] = y;
F[1, 0] = z;
F[1, 1] = w;
}
private void Power(long[,] F, int n) {
if (n == 0 || n == 1)
return;
long[,] M = { { 3, 2 }, { 2, 2 } };
Power(F, n / 2);
Multiply(F, F);
if (n % 2 != 0)
Multiply(F, M);
}
public int NumOfWays(int n) {
if (n == 1)
return 12;
long[,] F = {{3, 2}, {2, 2}};
Power(F, n - 1);
return (int)((6 * F[0, 0] + 6 * F[0, 1]) % MODULO);
}
public static void Main() {
PaintGrid pg = new PaintGrid();
Console.WriteLine(pg.NumOfWays(5000));
}
}Python's matrix exponentiation focuses on mutable list operations to track and update transformation states, applying modular arithmetic to meet integer size constraints efficiently.
Time Complexity: O(log n), accomplished by matrix power calculation.
Space Complexity: O(1), thanks to on-the-fly updating of the matrix.
Approach 3: Recursion
We classify all possible states for each row. According to the principle of symmetry, when a row only has 3 elements, all legal states are classified as: 010 type, 012 type.
- When the state is
010type: The possible states for the next row are:101,102,121,201,202. These5states can be summarized as3010types and2012types. - When the state is
012type: The possible states for the next row are:101,120,121,201. These4states can be summarized as2010types and2012types.
In summary, we can get: newf0 = 3 times f0 + 2 times f1, newf1 = 2 times f0 + 2 times f1.
The time complexity is O(n), where n is the number of rows in the grid. The space complexity is O(1).
function numOfWays(n: number): number {
const mod: number = 10 ** 9 + 7;
let f0: number = 6;
let f1: number = 6;
for (let i = 1; i < n; i++) {
const g0: number = (3 * f0 + 2 * f1) % mod;
const g1: number = (2 * f0 + 2 * f1) % mod;
f0 = g0;
f1 = g1;
}
return (f0 + f1) % mod;
}func numOfWays(n int) int {
mod := int(1e9) + 7
f0, f1 := 6, 6
for n > 1 {
n--
g0 := (f0*3 + f1*2) % mod
g1 := (f0*2 + f1*2) % mod
f0, f1 = g0, g1
}
return (f0 + f1) % mod
}impl Solution {
pub fn num_of_ways(n: i32) -> i32 {
const MOD: i64 = 1_000_000_007;
let mut f0: i64 = 6;
let mut f1: i64 = 6;
for _ in 0..n - 1 {
let g0 = (3 * f0 + 2 * f1) % MOD;
let g1 = (2 * f0 + 2 * f1) % MOD;
f0 = g0;
f1 = g1;
}
((f0 + f1) % MOD) as i32
}
}Approach 4: State Compression + Dynamic Programming
We notice that the grid only has 3 columns, so there are at most 3^3=27 different coloring schemes in a row.
Therefore, we define f[i][j] to represent the number of schemes in the first i rows, where the coloring state of the ith row is j. The state f[i][j] is transferred from f[i - 1][k], where k is the coloring state of the i - 1th row, and k and j meet the requirement of different colors being adjacent. That is:
$
f[i][j] = sum_{k \in valid(j)} f[i - 1][k]
where valid(j) represents all legal predecessor states of state j.
The final answer is the sum of f[n][j], where j is any legal state.
We notice that f[i][j] is only related to f[i - 1][k], so we can use a rolling array to optimize the space complexity.
The time complexity is O((m + n) times 3^{2m}), and the space complexity is O(3^m). Here, m and n$ are the number of rows and columns of the grid, respectively.
function numOfWays(n: number): number {
const f1 = (x: number): boolean => {
let last = -1;
for (let i = 0; i < 3; ++i) {
if (x % 3 === last) {
return false;
}
last = x % 3;
x = Math.floor(x / 3);
}
return true;
};
const f2 = (x: number, y: number): boolean => {
for (let i = 0; i < 3; ++i) {
if (x % 3 === y % 3) {
return false;
}
x = Math.floor(x / 3);
y = Math.floor(y / 3);
}
return true;
};
const m = 27;
const valid = new Set<number>();
const f: number[] = Array(m).fill(0);
for (let i = 0; i < m; ++i) {
if (f1(i)) {
valid.add(i);
f[i] = 1;
}
}
const d: Map<number, number[]> = new Map();
for (const i of valid) {
for (const j of valid) {
if (f2(i, j)) {
d.set(i, (d.get(i) || []).concat(j));
}
}
}
const mod = 10 ** 9 + 7;
for (let k = 1; k < n; ++k) {
const g: number[] = Array(m).fill(0);
for (const i of valid) {
for (const j of d.get(i) || []) {
g[i] = (g[i] + f[j]) % mod;
}
}
f.splice(0, f.length, ...g);
}
let ans = 0;
for (const x of f) {
ans = (ans + x) % mod;
}
return ans;
}func numOfWays(n int) (ans int) {
f1 := func(x int) bool {
last := -1
for i := 0; i < 3; i++ {
if x%3 == last {
return false
}
last = x % 3
x /= 3
}
return true
}
f2 := func(x, y int) bool {
for i := 0; i < 3; i++ {
if x%3 == y%3 {
return false
}
x /= 3
y /= 3
}
return true
}
m := 27
valid := map[int]bool{}
f := make([]int, m)
for i := 0; i < m; i++ {
if f1(i) {
valid[i] = true
f[i] = 1
}
}
d := map[int][]int{}
for i := range valid {
for j := range valid {
if f2(i, j) {
d[i] = append(d[i], j)
}
}
}
const mod int = 1e9 + 7
for k := 1; k < n; k++ {
g := make([]int, m)
for i := range valid {
for _, j := range d[i] {
g[i] = (g[i] + f[j]) % mod
}
}
f = g
}
for _, x := range f {
ans = (ans + x) % mod
}
return
}use std::collections::{HashSet, HashMap};
impl Solution {
pub fn num_of_ways(n: i32) -> i32 {
const MOD: i32 = 1_000_000_007;
let m = 27;
let mut valid = HashSet::new();
let mut f = vec![0; m];
for i in 0..m {
if Self::f1(i as i32) {
valid.insert(i as i32);
f[i] = 1;
}
}
let mut d: HashMap<i32, Vec<i32>> = HashMap::new();
for &i in &valid {
for &j in &valid {
if Self::f2(i, j) {
d.entry(i).or_insert_with(Vec::new).push(j);
}
}
}
for _ in 1..n {
let mut g = vec![0; m];
for &i in &valid {
if let Some(neighbors) = d.get(&i) {
for &j in neighbors {
g[j as usize] = (g[j as usize] + f[i as usize]) % MOD;
}
}
}
f = g;
}
let mut ans = 0;
for x in f {
ans = (ans + x) % MOD;
}
ans
}
fn f1(mut x: i32) -> bool {
let mut last = -1;
for _ in 0..3 {
if x % 3 == last {
return false;
}
last = x % 3;
x /= 3;
}
true
}
fn f2(mut x: i32, mut y: i32) -> bool {
for _ in 0..3 {
if x % 3 == y % 3 {
return false;
}
x /= 3;
y /= 3;
}
true
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n), because of the loop over rows. |
| Matrix Exponentiation | Time Complexity: O(log n), accomplished by matrix power calculation. |
| Recursion | – |
| State Compression + Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Pattern States) | O(n) | O(1) | Best general solution for interviews and typical constraints |
| Matrix Exponentiation | O(log n) | O(1) | When n is extremely large and DP iteration becomes expensive |
Frequently asked questions
Is Number of Ways to Paint N × 3 Grid easy or hard?
The problem is labeled Hard because the key insight is not obvious: recognizing that all valid rows reduce to two repeating patterns. Once that observation is made, the implementation becomes a short dynamic programming recurrence with constant space.
Number of Ways to Paint N × 3 Grid Python/Java solution
Python, Java, C++, C#, and JavaScript implementations typically follow the same DP recurrence using two variables for pattern counts. Each iteration updates the counts based on allowed transitions and applies modulo 1e9+7. The logic is identical across languages with only syntax differences.
How to solve Number of Ways to Paint N × 3 Grid in O(n)?
Track two valid row patterns: ABA and ABC. Initialize both counts as 6 for the first row, then update them using recurrence relations derived from valid vertical transitions. Iterate through rows from 2 to n and update the counts modulo 1e9+7, producing the final total in linear time.
What is the best approach for Number of Ways to Paint N × 3 Grid?
The best approach uses dynamic programming with two pattern states: ABA (two colors in the row) and ABC (three distinct colors). Instead of evaluating every coloring combination, track how these patterns transition from one row to the next. This reduces the problem to constant state updates with O(n) time and O(1) space complexity.
Is Number of Ways to Paint N × 3 Grid asked at Google/Amazon/Meta?
This problem represents a classic dynamic programming pattern involving state compression and recurrence transitions. Variants of grid coloring and pattern-based DP frequently appear in interviews at companies like Google, Amazon, and Meta, especially when testing recurrence design and optimization skills.
What data structure is used in Number of Ways to Paint N × 3 Grid?
The solution mainly relies on dynamic programming with constant state variables rather than complex data structures. Two integers track the number of valid row patterns (ABA and ABC). The matrix exponentiation version additionally uses a small 2×2 matrix for fast recurrence computation.
What is the time complexity of Number of Ways to Paint N × 3 Grid?
The standard dynamic programming solution runs in O(n) time because it processes the grid row by row while updating two state counts. Space complexity is O(1) since only two variables are maintained. Using matrix exponentiation can further reduce time complexity to O(log n).