Skip to main content
Back to problems
#1411
Hard Algorithms

Number of ways to paint n 3 grid

Dynamic Programming
80.5% acceptance
Feb 25, 2026
1651
91
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.

Solution

Rust
Time O(n)
Space O(1)
LeetCode
solution.rs 
impl Solution {
  pub fn num_of_ways(n: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    // aba_count: rows with pattern ABA (2 colors), abc_count: rows with pattern ABC (3 colors)
    let (mut aba, mut abc) = (6i64, 6i64);
    for _ in 1..n {
      let new_aba = (3 * aba + 2 * abc) % MOD;
      let new_abc = (2 * aba + 2 * abc) % MOD;
      aba = new_aba;
      abc = new_abc;
    }
    ((aba + abc) % MOD) as i32
  }
}