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

Source: Dev.to

Problem Summary

You’re given:

• A grid of size 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

Because each row has only three cells, every valid row falls into one of two pattern types:

When moving from row i to row i + 1 we count how many new rows of each type can be placed below an existing row without breaking the adjacency rule:

• Below an ABA row: 3 possible ABA rows and 2 possible ABC rows.
• Below an ABC row: 2 possible ABA rows and 2 possible ABC rows.

By keeping only the counts of ABA and ABC rows and updating them for each additional row, we obtain a linear‑time solution.

Code Blocks

C++

class Solution {
public:
    int numOfWays(int n) {
        constexpr int kMod = 1000000007;
        long color2 = 6; // ABA patterns
        long color3 = 6; // ABC patterns

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

Python

k_mod = 10**9 + 7
# color2 = ABA patterns, color3 = ABC patterns
color2 = 6
color3 = 6

for _ in range(1, n):
    next_color2 = (color2 * 3 + color3 * 2) % k_mod
    next_color3 = (color2 * 2 + color3 * 2) % k_mod
    color2, color3 = next_color2, next_color3

result = (color2 + color3) % k_mod

JavaScript

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

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

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

Key Takeaways

• State Reduction: Grouping row configurations into ABA and ABC patterns avoids tracking every individual color combination.
• Linear Time Complexity: The algorithm runs in O(n) time, iterating through the rows once.
• Modulo Arithmetic: Applying the modulo at each step prevents overflow when counts grow exponentially.

Final Thoughts

This problem is an excellent introduction to state‑transition dynamic programming. Similar pattern‑counting techniques appear in real‑world scenarios such as resource scheduling and map‑coloring algorithms, where adjacent entities must differ. Mastering these counting problems is a valuable step toward succeeding in technical interviews at top‑tier companies.