Problem Description

You are given an integer n, representing the number of rows in an n x 3 grid. Each cell in the grid can be painted with one of three colors: red, yellow, or green. The rules are:

• No two adjacent cells in the same row can have the same color.
• No two cells in the same column but in adjacent rows can have the same color.

Your task is to determine the total number of ways to paint the grid, modulo 10^9 + 7.

Constraints:

• 1 <= n <= 5000

Thought Process

At first glance, you might think of generating all possible colorings and checking which ones are valid. However, with 3 colors and 3 columns per row, the number of possibilities grows exponentially with n. This brute-force approach is not feasible for large n.

Instead, we should look for patterns or states that allow us to efficiently compute the answer using dynamic programming. The key is to recognize that the coloring of each row only depends on the coloring of the previous row, and that there are limited valid colorings for a single row.

By classifying row colorings into patterns (based on how colors are arranged), we can keep track of how many ways each pattern can transition to the next row, and use this to build up the solution efficiently.

Solution Approach

We break the problem into manageable subproblems using dynamic programming. Let's walk through the steps:

1. Classify row patterns:
   • For a single row of 3 cells with 3 colors, there are two types of valid patterns:
     • Type 1 (ABA): The first and third cell have the same color, the second is different. For example, Red-Yellow-Red.
     • Type 2 (ABC): All three cells have different colors. For example, Red-Yellow-Green.
2. Count patterns for one row:
   • Type 1 (ABA): There are 6 ways (3 choices for the repeated color, 2 for the middle).
   • Type 2 (ABC): There are 6 ways (3 choices for the first, 2 for the second, 1 for the third).
3. Define DP states:
   • same: Number of ways to paint up to row i ending with a Type 1 (ABA) pattern.
   • diff: Number of ways to paint up to row i ending with a Type 2 (ABC) pattern.
4. Derive recurrence relations:
   • For each new row:
     • new_same = same * 3 + diff * 2
     • new_diff = same * 2 + diff * 2
     The coefficients come from counting how many ways a Type 1 or Type 2 row can follow another, based on coloring constraints.
5. Iterate for n rows:
   • Start with initial values for the first row (both are 6).
   • Update same and diff for each subsequent row.
6. Return the result:
   • The total number of ways is (same + diff) % (10^9 + 7).

Example Walkthrough

Let's walk through the process for n = 2 (a 2x3 grid):

1. First row:
   • Type 1 (ABA): 6 ways
   • Type 2 (ABC): 6 ways
2. Second row:
   • Type 1 can be followed by:
     • Type 1: 6 * 3 = 18 ways
     • Type 2: 6 * 2 = 12 ways
   • Type 2 can be followed by:
     • Type 1: 6 * 2 = 12 ways
     • Type 2: 6 * 2 = 12 ways
   • Total for Type 1: 18 + 12 = 30
   • Total for Type 2: 12 + 12 = 24
3. Total ways for n=2:
   • 30 + 24 = 54

This matches the example in the problem statement.

Time and Space Complexity

Brute-force approach:

• Time: O(3^{3n}) (for each cell, 3 choices; for all n rows of 3 columns)
• Space: O(1) if not storing all colorings

• Time: O(n) (one iteration per row)
• Space: O(1) (we only need the previous state, not the whole DP table)

The optimized approach is highly efficient and works for the maximum constraint n = 5000.

Code Implementation

class Solution:
    def numOfWays(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        same, diff = 6, 6  # same: ABA, diff: ABC
        for _ in range(1, n):
            new_same = (same * 3 + diff * 2) % MOD
            new_diff = (same * 2 + diff * 2) % MOD
            same, diff = new_same, new_diff
        return (same + diff) % MOD
      

class Solution {
public:
    int numOfWays(int n) {
        const int MOD = 1e9 + 7;
        long same = 6, diff = 6;
        for (int i = 1; i < n; ++i) {
            long new_same = (same * 3 + diff * 2) % MOD;
            long new_diff = (same * 2 + diff * 2) % MOD;
            same = new_same;
            diff = new_diff;
        }
        return (same + diff) % MOD;
    }
};
      

class Solution {
    public int numOfWays(int n) {
        int MOD = 1000000007;
        long same = 6, diff = 6;
        for (int i = 1; i < n; ++i) {
            long new_same = (same * 3 + diff * 2) % MOD;
            long new_diff = (same * 2 + diff * 2) % MOD;
            same = new_same;
            diff = new_diff;
        }
        return (int)((same + diff) % MOD);
    }
}
      

var numOfWays = function(n) {
    const MOD = 1e9 + 7;
    let same = 6, diff = 6;
    for (let i = 1; i < n; ++i) {
        let new_same = (same * 3 + diff * 2) % MOD;
        let new_diff = (same * 2 + diff * 2) % MOD;
        same = new_same;
        diff = new_diff;
    }
    return (same + diff) % MOD;
};
      

Summary

The key to solving the "Number of Ways to Paint N × 3 Grid" problem efficiently is recognizing the repeating patterns in row colorings and how they transition from one row to the next. By classifying rows into two types (ABA and ABC), and using dynamic programming to keep track of valid transitions, we reduce the problem from an exponential brute-force search to a simple linear recurrence. This approach is both elegant and highly performant, making it suitable for large inputs.