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 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 .
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:
- 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.
- 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 to row . 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 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.
Top comments (0)