LeetCode 1931 - Painting a Grid With Three Different Colors

The problem is asking us to count the number of ways to paint an m x n grid using three colors: red, green, and blue, with the constraint that no two adjacent cells can have the same color. Adjacent cells include both vertically and horizontally neighboring cells.

leetcodeharddynamic-programming

LeetCode Problem 1931

Difficulty: 🔴 Hard
Topics: Dynamic Programming

Solution

Problem Understanding

The problem is asking us to count the number of ways to paint an m x n grid using three colors: red, green, and blue, with the constraint that no two adjacent cells can have the same color. Adjacent cells include both vertically and horizontally neighboring cells. The inputs m and n define the number of rows and columns of the grid, respectively, and the output is the total number of valid colorings modulo 10^9 + 7 to avoid overflow.

The key constraints are 1 <= m <= 5 and 1 <= n <= 1000. The small upper bound on m suggests that row-by-row computations are feasible, but the large upper bound on n indicates that any approach iterating over all possible grids directly will be too slow. Important edge cases include very small grids (like 1x1 or 1x2) and the maximum size (5x1000). The problem guarantees that all inputs are positive integers and the grid is fully paintable.

Approaches

A brute-force approach would try to enumerate all possible colorings of the grid, checking each one to see if it satisfies the adjacency constraints. For an m x n grid, there are 3^(m*n) total colorings. This method guarantees correctness but is infeasible for m=5, n=1000 because the number of combinations grows exponentially.

The optimal approach uses dynamic programming with state compression. Since m is small, we can represent each row as a sequence of m colors. First, we generate all valid row patterns where no two adjacent cells in the same row have the same color. Then, we use DP to compute how these row patterns can stack on top of each other, enforcing that no two vertically adjacent cells have the same color. This reduces the exponential complexity from 3^(m*n) to 3^m * n for DP transitions, which is tractable given the constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(3^(m*n)) O(3^(m*n)) Enumerate all possible grids, checking adjacency constraints
Optimal O(n * 3^m * 3^m) O(3^m) Generate valid row patterns and use DP to count stacking possibilities

Algorithm Walkthrough

  1. Generate all valid row patterns: Each row of m cells can be painted in 3^m ways. Filter these to keep only patterns where no two adjacent cells in the row share the same color.
  2. Precompute row adjacency compatibility: For every pair of valid row patterns, check if they can be stacked, i.e., if all cells in one row differ from the corresponding cells in the other row.
  3. Initialize DP: Use a dictionary or array dp where the key/index is a valid row pattern and the value is the number of ways to fill the grid up to the current column with that pattern on top.
  4. Iterate column by column: For each column, update the DP for the next column using the previous column's DP and the adjacency compatibility table.
  5. Sum all final DP values: After processing all columns, the sum of values in the last DP dictionary gives the total number of valid colorings.

Why it works: This algorithm works because it preserves the invariant that dp[pattern] always stores the number of ways to color the grid up to the current column with the top row as pattern. By iteratively combining compatible rows, we correctly count all valid grid configurations without violating adjacency constraints.

Python Solution

class Solution:
    MOD = 10**9 + 7
    
    def colorTheGrid(self, m: int, n: int) -> int:
        from itertools import product
        
        # Generate all valid row patterns
        colors = [0, 1, 2]  # Represent red, green, blue
        valid_rows = []
        for row in product(colors, repeat=m):
            if all(row[i] != row[i+1] for i in range(m-1)):
                valid_rows.append(row)
        
        # Precompute compatibility between rows
        compatible = {row: [] for row in valid_rows}
        for row1 in valid_rows:
            for row2 in valid_rows:
                if all(row1[i] != row2[i] for i in range(m)):
                    compatible[row1].append(row2)
        
        # Initialize DP
        dp = {row: 1 for row in valid_rows}
        
        # Iterate over columns
        for _ in range(1, n):
            new_dp = {row: 0 for row in valid_rows}
            for row in valid_rows:
                for prev in compatible[row]:
                    new_dp[row] = (new_dp[row] + dp[prev]) % self.MOD
            dp = new_dp
        
        return sum(dp.values()) % self.MOD

The Python solution first generates all valid row patterns and precomputes which rows can sit above each other. The DP dictionary stores the number of ways to reach each row configuration, and we update it column by column. The modulus ensures we handle large numbers efficiently.

Go Solution

package main

func colorTheGrid(m int, n int) int {
    const MOD = 1_000_000_007
    
    // Generate all valid rows using recursion
    var validRows [][]int
    var gen func([]int)
    gen = func(row []int) {
        if len(row) == m {
            validRows = append(validRows, append([]int(nil), row...))
            return
        }
        for c := 0; c < 3; c++ {
            if len(row) == 0 || row[len(row)-1] != c {
                gen(append(row, c))
            }
        }
    }
    gen([]int{})
    
    // Precompute compatibility
    compatible := make(map[int][]int)
    for i, r1 := range validRows {
        for j, r2 := range validRows {
            ok := true
            for k := 0; k < m; k++ {
                if r1[k] == r2[k] {
                    ok = false
                    break
                }
            }
            if ok {
                compatible[i] = append(compatible[i], j)
            }
        }
    }
    
    dp := make([]int, len(validRows))
    for i := range dp {
        dp[i] = 1
    }
    
    for col := 1; col < n; col++ {
        newDp := make([]int, len(validRows))
        for i := range validRows {
            for _, prev := range compatible[i] {
                newDp[i] = (newDp[i] + dp[prev]) % MOD
            }
        }
        dp = newDp
    }
    
    result := 0
    for _, val := range dp {
        result = (result + val) % MOD
    }
    return result
}

The Go solution mirrors the Python version but uses slices and maps instead of dictionaries and tuples. It uses recursion to generate valid row patterns and a map to store compatibility relationships. Slice copying ensures independent row storage.

Worked Examples

Example 1: m = 1, n = 1

All single-cell colorings are valid. dp starts with {0:1, 1:1, 2:1}, and since n=1, the sum is 3.

Example 2: m = 1, n = 2

Valid rows: [0],[1],[2]. Compatibility allows any row to follow a different row. For the second column, each row can be followed by two others, giving 3*2=6.

Example 3: m = 5, n = 5

The algorithm generates all valid 5-cell rows (there are 66), computes compatibility, then iterates 5 times for columns. The DP counts the number of valid colorings accurately, resulting in 580986.

Complexity Analysis

Measure Complexity Explanation
Time O(n * 3^m * 3^m) Generate all valid rows 3^m, check all pairs for compatibility 3^m * 3^m, then iterate n columns
Space O(3^m + 3^m * 3^m) Store valid rows and compatibility map, plus DP arrays of size 3^m

The complexity is feasible because m <= 5, making 3^m = 243 at most.

Test Cases

# Provided examples
assert Solution().colorTheGrid(1, 1) == 3  # Single cell
assert Solution().colorTheGrid(1, 2) == 6  # Two cells in a row
assert Solution().colorTheGrid(5, 5) == 580986  # 5x5 grid

# Edge cases
assert Solution().colorTheGrid(1, 1000) > 0  # Long single-row grid
assert Solution().colorTheGrid(5, 1) > 0  # Single column grid
assert Solution().colorTheGrid(5, 1000) > 0  # Maximum size grid
Test Why
1x1 Minimal grid
1x2 Small row, checks adjacency
5x5 Medium size grid, checks DP