We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Painting a Grid With Three Different Colors

Number: 2061

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an m x n grid where each cell is initially white, you need to paint each cell with one of three colors: red, green, or blue. The painting must be done such that no two adjacent cells (horizontally or vertically) share the same color. Every cell must be painted. Return the number of valid ways to color the grid modulo 10^9 + 7.

Key Insights

  • Since m is small (m ≤ 5) but n can be large (n ≤ 1000), it is efficient to treat each column as a state.
  • Precompute all valid color configurations for a single column (ensuring vertical adjacent cells differ).
  • For any two consecutive columns, ensure that colors in corresponding rows (horizontal adjacent cells) are different.
  • Use dynamic programming where dp[i] represents the number of ways to paint up to the current column ending with the i‑th valid state.
  • Precompute valid transitions between states to avoid repeated checks.

Space and Time Complexity

Time Complexity: O(n * S^2) where S is the number of valid states (at most 3 * 2^(m-1)).
Space Complexity: O(S^2 + S) for storing state transition information and DP arrays.

Solution

We solve the problem using a dynamic programming (DP) approach on columns:

  1. Generate all valid states for a column of height m ensuring vertical adjacent cells are painted with different colors.
  2. Precompute a 2D boolean matrix capturing whether state i is compatible with state j for adjacent columns (i.e., for every row, the color in state i is different from the color in state j).
  3. Initialize the DP array with 1 for each valid state as the first column can be painted in any valid configuration.
  4. For each subsequent column, update the DP counts using the precomputed transitions.
  5. Finally, return the sum of the DP array values modulo 10^9 + 7.

Below are solutions in Python, JavaScript, C++, and Java with detailed comments.

Code Solutions

MOD = 10**9 + 7

# Recursively generate all valid states for one column
def generate_valid_states(m, colors=3):
    states = []
    def backtrack(row, current):
        if row == m:
            states.append(tuple(current))
            return
        for color in range(colors):
            if row > 0 and current[-1] == color:
                continue
            current.append(color)
            backtrack(row + 1, current)
            current.pop()
    backtrack(0, [])
    return states

# Check if two states are compatible (i.e., horizontal adjacent cells have different colors)
def are_compatible(state1, state2):
    return all(c1 != c2 for c1, c2 in zip(state1, state2))

def colorTheGrid(m, n):
    valid_states = generate_valid_states(m)
    state_count = len(valid_states)
    
    # Precompute valid transitions between states for adjacent columns
    transitions = [[False] * state_count for _ in range(state_count)]
    for i in range(state_count):
        for j in range(state_count):
            if are_compatible(valid_states[i], valid_states[j]):
                transitions[i][j] = True
    
    dp = [1] * state_count  # Initialize dp for the first column
    for _ in range(1, n):
        new_dp = [0] * state_count
        for i in range(state_count):
            for j in range(state_count):
                if transitions[i][j]:
                    new_dp[j] = (new_dp[j] + dp[i]) % MOD
        dp = new_dp
    return sum(dp) % MOD

# Example usage:
print(colorTheGrid(1, 1))  # Expected Output: 3
print(colorTheGrid(1, 2))  # Expected Output: 6
print(colorTheGrid(5, 5))  # Expected Output: 580986
← Back to All Questions