Problem Informations

Problem Index: 1931
Problem Link: Painting a Grid With Three Different Colors
Topics: Dynamic Programming

Problem Description

You are given two integers m and n. Consider an m x n grid where each cell is initially white. You can paint each cell red, green, or blue. All cells must be painted.

Return the number of ways to color the grid with no two adjacent cells having the same color. Since the answer can be very large, return it modulo $10^9 + 7$.

Example 1:

Example 1

Input: m = 1, n = 1
Output: 3
Explanation: The three possible colorings are shown in the image above.

Example 2:

Example 2

Input: m = 1, n = 2
Output: 6
Explanation: The six possible colorings are shown in the image above.

Example 3:

Input: m = 5, n = 5
Output: 580986

Constraints:

$1 \leq m \leq 5$
$1 \leq n \leq 1000$

Intuition

The problem requires us to find the number of ways to color an $ m \times n $ grid with no two adjacent cells having the same color using three colors. Given the constraints, especially with $ n $ possibly being as large as 1000, a direct combinatorial approach could be computationally prohibitive. Instead, the solution leverages dynamic programming with a focus on valid column color patterns and transitions between them. The key insight is to reduce the problem to determining valid state transitions between column patterns, thus simplifying the otherwise daunting task of considering the entire grid at once.

Approach

The approach can be broken down into several steps:

Single Column Representation and Validation:
- Each column in the grid can be represented as a base-3 number since each cell in the column can take one of the three colors. The number of cells in a column is $ m $, so there are $ 3^m $ possible column patterns.
- We define a function isValidSingleColumn that checks if a given column pattern (represented as a number) is valid, i.e., no two adjacent cells in the column have the same color.
Valid Column Patterns Collection:
- We iterate through all $ 3^m $ possible column patterns and collect those which are valid, using the isValidSingleColumn function. These valid patterns are stored along with indexing for easy reference.
Column Transition Validation:
- We define another function isValidColumnPair to check if two columns can stand adjacent to each other without violating the color constraint. This means for two adjacent columns, cells in the same row of these columns should not have the same color.
- Using this function, we build a mapping of valid transitions between any two valid columns.
Dynamic Programming Setup:
- We setup a 2D DP table dp where $ dp[i][j] $ represents the number of ways to color the first $ i $ columns of the grid ending with the $ j $-th valid column pattern.
- For the first column, every valid pattern is a valid coloring, so all entries in $ dp[0] $ initialize as 1.
DP Table Population:
- For each subsequent column, we update the DP table by considering valid transitions from the previously calculated column: $$ dp[col][currentPatternIndex] = (dp[col][currentPatternIndex] + dp[col - 1][prevPatternIndex]) % MOD $$
- The transitions are guided by the pre-computed valid transitions between column patterns.
Final Calculation:
- The final answer is obtained by summing the last column of the DP table, which represents all valid colorings for the whole grid with each potential ending column pattern.

This method efficiently encapsulates the constraints and systematically computes the desired result within feasible time by making use of state reduction and dynamic programming. The use of modulo $10^9 + 7$ ensures that the solution fits within desirable computational limits for large outputs.

Code

C++

#define MOD 1000000007

class Solution {
private:
    // Function to check if a single column pattern is valid
    bool isValidSingleColumn(int num, int m) {
        int prevColor = -1; // Previous cell color

        for (int i = 0; i < m; i++) {
            int currentColor = num % 3; // Current cell color

            // Check if adjacent cells have the same color
            if (currentColor == prevColor) 
                return false;

            prevColor = currentColor;
            num /= 3; // Move to the next cell
        }

        return true;
    }

    // Function to check if two columns can be adjacent
    bool isValidColumnPair(int col1, int col2, int m) {
        for (int i = 0; i < m; i++) {
            // Check if cells in the same row have the same color
            if (col1 % 3 == col2 % 3) 
                return false;

            col1 /= 3;
            col2 /= 3;
        }
        return true;
    }

public:
    // Function to return the number of ways to color the grid
    int colorTheGrid(int m, int n) {
        vector<int> validSingleColumns;
        unordered_map<int, int> patternToIndex;

        int maxState = pow(3, m); // Total possible states for a single column

        // Collect valid column patterns
        for (int i = 0; i < maxState; ++i) {
            if (isValidSingleColumn(i, m)) {
                patternToIndex[i] = validSingleColumns.size();
                validSingleColumns.push_back(i);
            }
        }

        int totalPatterns = validSingleColumns.size();
        vector<vector<int>> validColumnTransitions(totalPatterns);

        // Build valid transitions between columns
        for (int i = 0; i < totalPatterns; ++i) {
            for (int j = 0; j < totalPatterns; ++j) {
                if (isValidColumnPair(validSingleColumns[i], validSingleColumns[j], m)) {
                    validColumnTransitions[i].push_back(j);
                }
            }
        }

        // Dynamic programming table to count colorings
        vector<vector<int>> dp(n, vector<int>(totalPatterns, 0));
        
        // Initial base case setting
        for (int j = 0; j < totalPatterns; ++j) 
            dp[0][j] = 1;

        // Fill DP table
        for (int col = 1; col < n; ++col) {
            for (int currentPatternIndex = 0; currentPatternIndex < totalPatterns; ++currentPatternIndex) {
                for (int prevPatternIndex : validColumnTransitions[currentPatternIndex]) {
                    dp[col][currentPatternIndex] = (dp[col][currentPatternIndex] + dp[col - 1][prevPatternIndex]) % MOD;
                }
            }
        }

        // Calculate the final answer
        int result = 0;
        for (int j = 0; j < totalPatterns; ++j) {
            result = (result + dp[n - 1][j]) % MOD;
        }

        return result;
    }
};

Python

MOD = 1000000007

class Solution:
    # Function to check if a single column pattern is valid
    def isValidSingleColumn(self, num, m):
        prevColor = -1  # Previous cell color

        for i in range(m):
            currentColor = num % 3  # Current cell color

            # Check if adjacent cells have the same color
            if currentColor == prevColor:
                return False

            prevColor = currentColor
            num //= 3  # Move to the next cell

        return True

    # Function to check if two columns can be adjacent
    def isValidColumnPair(self, col1, col2, m):
        for i in range(m):
            # Check if cells in the same row have the same color
            if col1 % 3 == col2 % 3:
                return False

            col1 //= 3
            col2 //= 3
        return True

    # Function to return the number of ways to color the grid
    def colorTheGrid(self, m, n):
        validSingleColumns = []
        patternToIndex = {}

        maxState = pow(3, m)  # Total possible states for a single column

        # Collect valid column patterns
        for i in range(maxState):
            if self.isValidSingleColumn(i, m):
                patternToIndex[i] = len(validSingleColumns)
                validSingleColumns.append(i)

        totalPatterns = len(validSingleColumns)
        validColumnTransitions = [[] for _ in range(totalPatterns)]

        # Build valid transitions between columns
        for i in range(totalPatterns):
            for j in range(totalPatterns):
                if self.isValidColumnPair(validSingleColumns[i], validSingleColumns[j], m):
                    validColumnTransitions[i].append(j)

        # Dynamic programming table to count colorings
        dp = [[0] * totalPatterns for _ in range(n)]
        
        # Initial base case setting
        for j in range(totalPatterns):
            dp[0][j] = 1

        # Fill DP table
        for col in range(1, n):
            for currentPatternIndex in range(totalPatterns):
                for prevPatternIndex in validColumnTransitions[currentPatternIndex]:
                    dp[col][currentPatternIndex] = (dp[col][currentPatternIndex] + dp[col - 1][prevPatternIndex]) % MOD

        # Calculate the final answer
        result = 0
        for j in range(totalPatterns):
            result = (result + dp[n - 1][j]) % MOD

        return result

Complexity

Time complexity: $O(n \cdot p^2)$, where $p = 3^m$. The time complexity is determined by the generation and utilization of valid column transitions between states. Specifically, it involves calculating valid transitions for each pair of patterns, which results in $O(p^2)$ complexity. This is looped over for each of the $n$ columns, resulting in the overall complexity.
Space complexity: $O(n \cdot p)$. The space complexity primarily arises from the dynamic programming table, which stores the number of ways to color up to each column with a valid pattern. The DP table has dimensions $n \times p$, leading to the space usage. Additional space is used for valid patterns and transitions, but this does not exceed the DP table’s space.

CS Note
中

Leetcode 1931. Painting a Grid With Three Different Colors