Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1527. Number of Ways to Paint N × 3 Grid

My accepted Python solution to LeetCode problem 1527, Number of Ways to Paint N × 3 Grid, running in 7ms.

  • Difficulty: Hard
  • Python
  • Runtime 7ms
  • Memory 17.3MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 7ms, memory 17.3MB, accepted 2025-12-29.

python
class Solution:
    def numOfWays(self, n: int) -> int:
        MOD = 10**9 + 7
        
        # For a 3-column grid, each row can be one of two types:
        # Type A: 3 different colors (ABC pattern) - 12 patterns (3*2*1 = 6, but with permutations = 12)
        # Type B: 2 different colors (ABA pattern) - 6 patterns
        
        # Transitions:
        # Type A (ABC) can go to: 3 Type A + 2 Type B
        # Type B (ABA) can go to: 2 Type A + 2 Type B
        
        # Initial counts for n=1
        # Type A patterns: 12 (e.g., RYG, RGY, YRG, YGR, GRY, GYR, etc.)
        # Type B patterns: 6 (e.g., RYR, RGR, YRY, YGY, GRG, GYG)
        
        # Actually let's count properly:
        # Type A (all different): 3 * 2 * 1 = 6 arrangements * 2 (each can be reversed) = 12? No
        # 3 colors for first, 2 for second, 1 for third = 6 arrangements
        # But some are same when considering adjacency... let me recalculate
        
        # For 3 cells with 3 colors (R, Y, G):
        # Type A (all 3 different): RYG, RGY, YRG, YGR, GRY, GYR = 6
        # Type B (first = third): RYR, RGR, YRY, YGY, GRG, GYG = 6
        # Total = 12
        
        type_a = 6  # ABC patterns
        type_b = 6  # ABA patterns
        
        for _ in range(n - 1):
            # New counts based on transitions
            new_a = (3 * type_a + 2 * type_b) % MOD  # A->A has 3 valid, B->A has 2 valid
            new_b = (2 * type_a + 2 * type_b) % MOD  # A->B has 2 valid, B->B has 2 valid
            type_a, type_b = new_a, new_b
        
        return (type_a + type_b) % MOD

Source