Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 <= 5000Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Dynamic Programming
1
5000
painting-a-grid-with-three-different-colors)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1411: Number of Ways to Paint N × 3 Grid
class Solution {
public int numOfWays(int n) {
int mod = (int) 1e9 + 7;
long f0 = 6, f1 = 6;
for (int i = 0; i < n - 1; ++i) {
long g0 = (3 * f0 + 2 * f1) % mod;
long g1 = (2 * f0 + 2 * f1) % mod;
f0 = g0;
f1 = g1;
}
return (int) (f0 + f1) % mod;
}
}
// Accepted solution for LeetCode #1411: Number of Ways to Paint N × 3 Grid
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
}
# Accepted solution for LeetCode #1411: Number of Ways to Paint N × 3 Grid
class Solution:
def numOfWays(self, n: int) -> int:
mod = 10**9 + 7
f0 = f1 = 6
for _ in range(n - 1):
g0 = (3 * f0 + 2 * f1) % mod
g1 = (2 * f0 + 2 * f1) % mod
f0, f1 = g0, g1
return (f0 + f1) % mod
// Accepted solution for LeetCode #1411: Number of Ways to Paint N × 3 Grid
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
}
}
// Accepted solution for LeetCode #1411: Number of Ways to Paint N × 3 Grid
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;
}
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.