LeetCode 1411 Solution (Hard)

Difficulty: Hard

Categories: DP, Matrix

Language(s): C++

Complexity: O(N) time, O(1) space

Problem Summary

We are given an N value to create a N × 3 grid. Our task is to compute the number of valid ways to paint the grid with 3 colors such that:

• No two horizontally adjacent cells share the same color
• No two vertically adjacent cells share the same color

We're also told to return the result modulo 1e9 + 7 due to large return sizes.

---

Edge Cases / Things to Consider

• What is the number of valid colorings for a single row?
• How does the coloring of one row constrain the next?
• Can possible patterns be grouped/bucketed?
• What row(s) matter in determining the current row's possibilities?

---

Intuition / High-Level Approach

The key to solving this problem is realizing that there are two distinct groups possible row solutions can be bucketed into:

1. Two-color pattern (121)

   • Example: Red, Blue, Red

2. Three-color pattern (123)

   • Example: Red, Blue, Green

---

Base Case (Single Row)

In a single row, there are six possible combinations for each of our two buckets.

2-color: [121,131,212,232,313,323] 3-color: [123,132,231,213,312,321]

Knowing this , we can initialize the number of solutions possible for each bucket in a vector for the first row, as follows:

vector<int> solutions = {6,6};

Dynamic Programming Step

Once we have our base case defined, we now have to dynamically use the current row to calculate the possibilities of the next. We can do this by thinking about what possible solutions are possible for both of our pattern buckets.

For each 2-color solution for the current row , there exist:

• 3 two-color solutions for the next row , ex: this row: [121] next row: [212] or [313] or [232]

• 2 three-color solutions for the next row, ex: this row: [121] next row: [213] or [312]

For each 3-color solution for the current row, there exist:

• 2 two-color solutions for the next row , ex: this row: [123] next row: [232] or [212]

• 2 three-color solutions for the next row, ex: this row: [123] next row: [312] or [231]

Once we understand this pattern , we can use it to derive equations for calculating the additional solutions added by each row being solved. They will look something like this:

2_solves(n) = ((2_solves(n-1) * 3) + (3_solves(n-1)*2)) % (1e9 + 7) 3_solves(n) = ((2_solves(n-1) * 2) + (3_solves(n-1)*2)) % (1e9 + 7)

Now that we have our step for calculating each following row after the initial one, we can iterate to N to figure out our solution.

Solution

class Solution {
public:
    int numOfWays(int n) {
        const int MOD = 1e9 + 7; 
        vector<long long> base = {6,6};
        for(int i = 1 ; i < n ; i++){
            long long nth_2c= (3*(base[0])+ 2*(base[1])) % MOD;
            long long nth_3c =(2*(base[0]) + 2*(base[1])) % MOD; 
            base[0] = nth_2c;
            base[1] = nth_3c;
        }
        return (base[0] + base[1]) % MOD;
    }
};