101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 2 main approaches to solve this problem:

  1. Dynamic Programming with State Compression - Complex approach
  2. Optimized Dynamic Programming - Complex approach

Approach 1: Dynamic Programming with State Compression

The key insight for solving this problem is to use dynamic programming with state compression. We'll represent the state of each column using a base-3 number, where each digit represents the color of a cell (0 for red, 1 for green, 2 for blue).

For each valid state of a column, we need to find all valid states for the next column such that no adjacent cells have the same color, both horizontally and vertically.

Algorithm:

  1. Generate all valid column states where no adjacent cells have the same color.
  2. For each valid state, precompute all valid next states that can follow it.
  3. Use dynamic programming to count the number of ways to paint the grid:
  4. a. Initialize dp[0][state] = 1 for all valid states.
  5. b. For each column j from 1 to n-1:
  6. i. For each valid state i:
  7. 1. For each valid next state k that can follow state i:
  8. dp[j][k] += dp[j-1][i].
  9. Return the sum of dp[n-1][state] for all valid states.

Time Complexity:

O(3^m × 3^m × n)

Where m is the number of rows and n is the number of columns. There are at most 3^m possible states for each column, and for each state, we check all possible next states (also at most 3^m). We do this for each of the n columns.

Space Complexity:

O(3^m × n)

We need to store the DP table of size 3^m × n, where 3^m is the number of possible states for each column and n is the number of columns.

Approach 2: Optimized Dynamic Programming

We can optimize the previous approach by observing that we only need the results from the previous column to compute the results for the current column. This allows us to reduce the space complexity.

Additionally, we can precompute the valid states and transitions to avoid redundant calculations.

Algorithm:

  1. Generate all valid column states where no adjacent cells have the same color.
  2. For each valid state, precompute all valid next states that can follow it.
  3. Use dynamic programming with space optimization:
  4. a. Initialize dp[state] = 1 for all valid states.
  5. b. For each column j from 1 to n-1:
  6. i. Create a new DP array newDp.
  7. ii. For each valid state i:
  8. 1. For each valid next state k that can follow state i:
  9. newDp[k] += dp[i].
  10. iii. Update dp = newDp.
  11. Return the sum of dp[state] for all valid states.

Time Complexity:

O(3^m × 3^m × n)

The time complexity remains the same as the previous approach, but with better constant factors due to precomputation.

Space Complexity:

O(3^m)

We only need to store the DP results for the current column, which requires O(3^m) space.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
function colorTheGrid(m, n):
    MOD = 10^9 + 7
 
    // Generate all valid column states
    validStates = []
    for state from 0 to 3^m - 1:
        if isValidState(state, m):
            validStates.append(state)
 
    // Precompute valid transitions
    validTransitions = {}
    for state1 in validStates:
        validTransitions[state1] = []
        for state2 in validStates:
            if canTransition(state1, state2, m):
                validTransitions[state1].append(state2)
 
    // Initialize DP table
    dp = 2D array of size n × len(validStates), initialized with 0s
    for i from 0 to len(validStates) - 1:
        dp[0][i] = 1
 
    // Fill DP table
    for j from 1 to n - 1:
        for i from 0 to len(validStates) - 1:
            state1 = validStates[i]
            for state2 in validTransitions[state1]:
                idx = index of state2 in validStates
                dp[j][idx] = (dp[j][idx] + dp[j-1][i]) % MOD
 
    // Sum up the results for the last column
    result = 0
    for i from 0 to len(validStates) - 1:
        result = (result + dp[n-1][i]) % MOD
 
    return result
 
function isValidState(state, m):
    // Convert state to base-3 representation
    colors = []
    tempState = state
    for i from 0 to m - 1:
        colors.append(tempState % 3)
        tempState = tempState / 3
 
    // Check if adjacent cells have different colors
    for i from 0 to m - 2:
        if colors[i] == colors[i+1]:
            return false
 
    return true
 
function canTransition(state1, state2, m):
    // Convert states to base-3 representation
    colors1 = []
    colors2 = []
    tempState1 = state1
    tempState2 = state2
 
    for i from 0 to m - 1:
        colors1.append(tempState1 % 3)
        colors2.append(tempState2 % 3)
        tempState1 = tempState1 / 3
        tempState2 = tempState2 / 3
 
    // Check if horizontally adjacent cells have different colors
    for i from 0 to m - 1:
        if colors1[i] == colors2[i]:
            return false
 
    return true
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone