🎨 Beginner-Friendly Guide 'Number of Ways to Paint N 3 Grid' – LeetCode 1411 (C++, Python, JavaScript)

Combinatorics and dynamic programming can often feel like solving a massive puzzle with missing pieces. This problem is a classic example of how observing small patterns can help us derive a mathematical formula to solve much larger problems efficiently.

Problem Summary

You're given:

• A grid of size $n \times 3$ (n rows and 3 columns).

• Three available colors: Red, Yellow, and Green.

• A rule that no two adjacent cells (horizontal or vertical) can have the same color.

  

Your goal:

• Calculate the total number of ways to paint the entire grid.

• Return the result modulo $10^9 + 7$.

Intuition

To solve this, we focus on the patterns within a single row. Because there are only 3 columns, we can categorize every valid row into two types:

1. ABA Pattern (2 colors used): The first and third cells are the same color, and the middle cell is different (e.g., Red-Yellow-Red). There are 6 such combinations.

2. ABC Pattern (3 colors used): All three cells have different colors (e.g., Red-Yellow-Green). There are also 6 such combinations.

The magic happens when we move from row $i$ to row $i+1$. We calculate how many new ABA and ABC patterns can be placed below an existing one without violating the adjacency rule.

• Below an ABA row, you can fit 3 new ABA-style rows and 2 new ABC-style rows.

• Below an ABC row, you can fit 2 new ABA-style rows and 2 new ABC-style rows.

By maintaining these two counts and updating them for each new row, we avoid complex recursion and solve the problem in linear time.

Code Blocks

C++

class Solution {
public:
 int numOfWays(int n) {
 constexpr int kMod = 1000000007;
 // Initial count for row 1: 6 ways for ABA, 6 ways for ABC
 long color2 = 6; 
 long color3 = 6; 

 for (int i = 1; i < n; ++i) {
 long nextColor2 = (color2 * 3 + color3 * 2) % kMod;
 long nextColor3 = (color2 * 2 + color3 * 2) % kMod;
 color2 = nextColor2;
 color3 = nextColor3;
 }

 return (color2 + color3) % kMod;
 }
};

Python

class Solution:
 def numOfWays(self, n: int) -> int:
 k_mod = 10**9 + 7
 # color2 represents ABA patterns, color3 represents ABC patterns
 color2 = 6
 color3 = 6
 
 for _ in range(1, n):
 # Transition logic based on previous row patterns
 next_color2 = (color2 * 3 + color3 * 2) % k_mod
 next_color3 = (color2 * 2 + color3 * 2) % k_mod
 color2, color3 = next_color2, next_color3
 
 return (color2 + color3) % k_mod

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var numOfWays = function(n) {
 const kMod = 1000000007n; // Using BigInt for large number precision
 let color2 = 6n;
 let color3 = 6n;

 for (let i = 1; i < n; i++) {
 let nextColor2 = (color2 * 3n + color3 * 2n) % kMod;
 let nextColor3 = (color2 * 2n + color3 * 2n) % kMod;
 color2 = nextColor2;
 color3 = nextColor3;
 }

 return Number((color2 + color3) % kMod);
};

Key Takeaways

• State Reduction: Instead of tracking every single color combination, we grouped them into patterns (ABA and ABC), which simplified the logic significantly.

• Linear Time Complexity: The solution runs in $O(n)$ time because we only iterate through the number of rows once.

• Modulo Arithmetic: When dealing with counts that grow exponentially, using the modulo operator at each step prevents integer overflow.

Final Thoughts

This problem is a fantastic introduction to State-Transition Dynamic Programming. In real-world software engineering, these types of logic patterns are used in resource scheduling and map coloring algorithms. If you were designing a scheduling system where no two consecutive tasks can use the same specialized hardware, the underlying logic would look very similar to this. Mastering these "counting" problems is a huge step toward passing technical interviews at top-tier firms.