1931. Painting a Grid With Three Different Colors


Problem Description

In this problem, we are presented with a challenge to determine the number of ways to paint a grid of size m x n. We are required to paint every cell of the grid, and we have three colors to choose from: red, green, and blue. The key constraint is that no two adjacent cells (neither horizontally nor vertically) may share the same color. The task is to find the total number of valid colorings and return this number modulo 10^9 + 7, which is a common way to handle large numbers in programming contests.

Intuition

To tackle this problem, we need to recognize that the critical challenge lies in ensuring that no two adjacent cells have the same color. Given that the number of rows (m) is relatively small (the problem doesn't specify the exact limit, but it suggests considering its small size), we can think of each column as a state that can be represented with a small number of bits or a small integer. This is a classic example of state compression, often used in dynamic programming approaches for similar grid-based problems. There are three colors to choose from, and with m rows, we can represent each column's state with a 3^m base number, where each digit (in base 3) represents a cell's color.

Once we're convinced that state compression is the way to go, we can then formulate the problem as one of dynamic programming. We can declare a function f[i][j] where i stands for the column index and j represents the color state of that column. To calculate the number of valid colorings, we want to add up all the ways to the paint columns from the first to the i-th column, given that the i-th column has state j. This addition counts only the valid cases where the i-th column color state is compatible with the i-1-th column state, meaning no two adjacent cells are of the same color.

By using a rolling array—overwriting previous states as we move to the next column—we can efficiently use space, updating our count only based on previously computed states, and thus solve the entire problem with a bottom-up dynamic programming approach.

In summary, the solution exploits the limited row size to compress column states into integers. Then, it applies dynamic programming to iterate over columns, maintaining a count of valid paintings that reach that column and adhere to the coloring constraints. Finally, the sum of valid paintings at the last column represents the total number of ways to paint the grid.

Learn more about Dynamic Programming patterns.

Solution Approach

The implementation of the solution involves several core concepts, primarily dynamic programming, state compression, and proper enumeration of valid states. Following these concepts, the key steps in the algorithm can be summarized as follows:

State Compression

Since each row in the grid can have one of three colors, and no two adjacent rows can have the same color within a column, this creates a manageable number of color configurations for each column. Specifically, for m rows, the total color configurations are 3^m. We refer to each unique color configuration as a state. We can represent the color of each row in a column as digits in a base-3 number, which makes it very efficient to enumerate and compare states. In the given solution, a function f1 is used to check if a given state is valid (i.e., there are no two adjacent cells with the same color) within a single column.

Enumeration of Valid Transitions

The next challenge is to check if transitioning between two states is valid (i.e., adjacent columns have no same-colored cells). To check this, another helper function f2 is implemented, which takes two states and verifies if they can be consecutive columns by verifying color conditions for each row.

Dynamic Programming

With the help of state compression, we setup a dynamic programming table, referred to as f in the code, that contains the number of ways to color the grid up to the current column, considering the state of that column. We also need to maintain a mapping d from each state to its possible next states, which is precomputed before running the dynamic programming loop to optimize the process.

Updating States

For each column, after the first, we iterate through all valid states of the latest column (i) and all valid transitions from previous column states (j). Here we observe that the number of ways to arrive at state i is the sum of all ways to arrive at each compatible state j in the previous column. This is precisely the meaning of f[i][j] = sum(f[i-1][k] for k in valid(j)).

Rolling Array Optimization

The code uses a rolling array technique to conserve space. Rather than maintaining a 2D array for the DP states, we use a 1D array and update it as we move to the next column. Each new state calculation only depends on the previous column, allowing us to overwrite the array for each column iteration.

Modulo Operation

Since the answer can be very large, we utilize the modulo operation at each step of adding up ways to ensure that we don't run into integer overflow and to provide the final answer in the requested form.

By encapsulating these steps in a structured manner, the solution effectively utilizes the efficiency of dynamic programming with state compression and ensures that all conditions of the problem are satisfied.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through the solution approach with a small example. We will consider a grid of size 2 x 3 (m=2, n=3) and imagine we are only using two colors due to the small example size. We'll call these colors A and B. Even though the original problem specifies three colors (red, green, and blue), this simplification with two colors allows us to easily understand the process. The modulo part will be ignored since our numbers will be small.

State Compression

For the grid's row size of m=2, each column can have AA, AB, BA, or BB (in this example, we don't use the third color). Since AB and BA are the only valid states without adjacent colors being the same, we have 2 valid states:

  • State 0: AB
  • State 1: BA

Enumeration of Valid Transitions

Now let's look at valid transitions between states from one column to the next:

  • State 0 (AB) to State 1 (BA) is valid.
  • State 1 (BA) to State 0 (AB) is valid.

Invalid transitions (like State 0 to State 0 or State 1 to State 1) are not allowed because they would mean two adjacent cells of two consecutive columns would have the same colors.

Dynamic Programming

We will create a dynamic programming table to keep track of the number of ways to paint the grid. Let's denote this table as f, where f[i][state] represents the number of ways to paint up to the i-th column with the given state layout at the i-th column.

For the first column, we have:

  • f[1][0] = 1 (AB)
  • f[1][1] = 1 (BA)

For subsequent columns, we'll sum the valid transitions from the previous column.

Updating States

Now let's calculate for the second column (i=2):

  • f[2][0] = f[1][1] because state 0 (AB) can follow state 1 (BA) from the previous column.
  • f[2][1] = f[1][0] because state 1 (BA) can follow state 0 (AB) from the previous column.

For the second column, we have:

  • f[2][0] = 1
  • f[2][1] = 1

For the third column (i=3), we apply the same logic using states from column 2:

  • f[3][0] = f[2][1]
  • f[3][1] = f[2][0]

We get:

  • f[3][0] = 1
  • f[3][1] = 1

Rolling Array Optimization

In practice, we do not need a separate entry in the array for each column. We can simply roll the states and update the count for the current column based on the previous one since only the immediate preceding column's state affects the current state.

Thus, at the end of column 3, we sum up the valid paintings from states 0 and 1 to get our result 2: Total number of ways = f[3][0] + f[3][1] = 1 + 1 = 2

We have found that there are 2 distinct ways to paint a 2 x 3 grid using the two colors while satisfying the adjacency rule.

Solution Implementation

1from collections import defaultdict
2
3class Solution:
4    def colorTheGrid(self, m: int, n: int) -> int:
5        # Helper function to check if a given coloring pattern for a column is valid
6        def is_valid_pattern(pattern: int) -> bool:
7            last_color = -1
8            for _ in range(m):
9                current_color = pattern % 3
10                if current_color == last_color:
11                    return False
12                last_color = current_color
13                pattern //= 3
14            return True
15
16        # Helper function to check if two adjacent columns' coloring patterns are valid
17        def are_adjacent_patterns_valid(first: int, second: int) -> bool:
18            for _ in range(m):
19                if first % 3 == second % 3:
20                    return False
21                first, second = first // 3, second // 3
22            return True
23
24        # Mod value for the final result to prevent integer overflow
25        mod = 10**9 + 7
26      
27        # The maximum value for a coloring pattern
28        max_pattern_value = 3**m
29      
30        # Set of all valid coloring patterns
31        valid_patterns = {i for i in range(max_pattern_value) if is_valid_pattern(i)}
32      
33        # Dictionary that maps each valid pattern to other patterns which it can be adjacent to
34        adjacent_patterns = defaultdict(list)
35        for pattern in valid_patterns:
36            for adjacent in valid_patterns:
37                if are_adjacent_patterns_valid(pattern, adjacent):
38                    adjacent_patterns[pattern].append(adjacent)
39      
40        # List storing the number of ways to color each pattern for a single column
41        ways_to_color = [int(pattern in valid_patterns) for pattern in range(max_pattern_value)]
42      
43        # Iterate over all columns from the second to the last to calculate possible colorings
44        for _ in range(n - 1):
45            next_column_ways = [0] * max_pattern_value
46            # Iterate over each valid pattern
47            for pattern in valid_patterns:
48                # Add up the ways to color this pattern based on its adjacent patterns from previous column
49                for adjacent in adjacent_patterns[pattern]:
50                    next_column_ways[pattern] = (next_column_ways[pattern] + ways_to_color[adjacent]) % mod
51            ways_to_color = next_column_ways
52      
53        # Sum all the ways to color the final column
54        return sum(ways_to_color) % mod
55
56
57# Example of using the code
58solution = Solution()
59print(solution.colorTheGrid(3, 2))  # This would call the function and print the number of ways to color a 3x2 grid.
60
1class Solution {
2    private int gridHeight;
3
4    public int colorTheGrid(int m, int n) {
5        this.gridHeight = m;
6        final int MOD = (int) 1e9 + 7; // Define the modulus for taking modulo
7        int maxStateValue = (int) Math.pow(3, m); // Total possible states given m rows and 3 colors
8        Set<Integer> validStates = new HashSet<>(); // To keep track of all valid configurations
9        int[] dpStateCounts = new int[maxStateValue]; // Dynamic programming array to count configurations
10
11        // Populate the valid states and their count
12        for (int state = 0; state < maxStateValue; ++state) {
13            if (isValidState(state)) {
14                validStates.add(state);
15                dpStateCounts[state] = 1;
16            }
17        }
18
19        // Map to hold the valid transitions between states
20        Map<Integer, List<Integer>> validTransitions = new HashMap<>();
21
22        // Find all valid transitions between valid states
23        for (int i : validStates) {
24            for (int j : validStates) {
25                if (isTransitionValid(i, j)) {
26                    validTransitions.computeIfAbsent(i, k -> new ArrayList<>()).add(j);
27                }
28            }
29        }
30
31        // Build up the answer column by column
32        for (int column = 1; column < n; ++column) {
33            int[] nextStateCounts = new int[maxStateValue]; // Temp array for the next state counts
34            for (int currentState : validStates) {
35                for (int nextState : validTransitions.getOrDefault(currentState, List.of())) {
36                    nextStateCounts[currentState] = (nextStateCounts[currentState] + dpStateCounts[nextState]) % MOD;
37                }
38            }
39            dpStateCounts = nextStateCounts; // Move to the next column
40        }
41
42        // Sum up all possible configurations
43        int answer = 0;
44        for (int count : dpStateCounts) {
45            answer = (answer + count) % MOD;
46        }
47        return answer;
48    }
49
50    // Check if a state is valid: no two adjacent cells in the same row have the same color
51    private boolean isValidState(int state) {
52        int lastColor = -1;
53        for (int i = 0; i < gridHeight; ++i) {
54            int currentColor = state % 3;
55            if (currentColor == lastColor) {
56                return false;
57            }
58            lastColor = currentColor;
59            state /= 3;
60        }
61        return true;
62    }
63
64    // Check if transitioning from one state to another is valid across columns
65    private boolean isTransitionValid(int stateOne, int stateTwo) {
66        for (int i = 0; i < gridHeight; ++i) {
67            if (stateOne % 3 == stateTwo % 3) {
68                return false;
69            }
70            stateOne /= 3;
71            stateTwo /= 3;
72        }
73        return true;
74    }
75}
76
1class Solution {
2public:
3    int colorTheGrid(int m, int n) {
4        // Lambda function to check if a given state is valid
5        auto isValidState = [&](int state) {
6            int lastColor = -1;
7            for (int i = 0; i < m; ++i) {
8                int currentColor = state % 3;
9                if (currentColor == lastColor) {
10                    return false;
11                }
12                lastColor = currentColor;
13                state /= 3;
14            }
15            return true;
16        };
17
18        // Lambda function to check if two states are valid neighbors
19        auto areValidNeighbors = [&](int state1, int state2) {
20            for (int i = 0; i < m; ++i) {
21                if (state1 % 3 == state2 % 3) {
22                    return false;
23                }
24                state1 /= 3;
25                state2 /= 3;
26            }
27            return true;
28        };
29
30        // Modulo for calculating answer
31        const int mod = 1e9 + 7;
32        // Maximum number of states
33        int maxStates = pow(3, m);
34
35        // Set and vector to keep track of valid states and their count
36        unordered_set<int> validStates;
37        vector<int> stateCounts(maxStates);
38
39        // Initialize valid states and their initial counts
40        for (int i = 0; i < maxStates; ++i) {
41            if (isValidState(i)) {
42                validStates.insert(i);
43                stateCounts[i] = 1;
44            }
45        }
46
47        // Map to store neighboring valid states
48        unordered_map<int, vector<int>> neighborStates;
49        for (int i : validStates) {
50            for (int j : validStates) {
51                if (areValidNeighbors(i, j)) {
52                    neighborStates[i].push_back(j);
53                }
54            }
55        }
56
57        // Iterate through columns
58        for (int k = 1; k < n; ++k) {
59            vector<int> newCounts(maxStates);
60            // Update the count for each valid state based on its neighbors
61            for (int i : validStates) {
62                for (int j : neighborStates[i]) {
63                    newCounts[i] = (newCounts[i] + stateCounts[j]) % mod;
64                }
65            }
66            // Move newCounts to stateCounts for the next column
67            stateCounts = move(newCounts);
68        }
69
70        // Calculate the final answer
71        int answer = 0;
72        for (int count : stateCounts) {
73            answer = (answer + count) % mod;
74        }
75
76        return answer;
77    }
78};
79
1function colorTheGrid(m: number, n: number): number {
2    // Helper function to check if a color combination for a column is valid (no two adjacent cells have the same color)
3    const isColumnValid = (column: number): boolean => {
4        let lastColor = -1;
5        for (let i = 0; i < m; ++i) {
6            if (column % 3 === lastColor) {
7                return false;
8            }
9            lastColor = column % 3;
10            column = Math.floor(column / 3);
11        }
12        return true;
13    };
14
15    // Helper function to check if two adjacent columns are valid (no two adjacent cells have the same color)
16    const areColumnsCompatible = (column1: number, column2: number): boolean => {
17        for (let i = 0; i < m; ++i) {
18            if (column1 % 3 === column2 % 3) {
19                return false;
20            }
21            column1 = Math.floor(column1 / 3);
22            column2 = Math.floor(column2 / 3);
23        }
24        return true;
25    };
26
27    const maxState = 3 ** m;
28    const validColumns = new Set<number>();
29    const waysToColor = Array(maxState).fill(0);
30  
31    // Pre-calculate all valid columns and the initial number of ways to color them (which is 1 for each valid column)
32    for (let i = 0; i < maxState; ++i) {
33        if (isColumnValid(i)) {
34            validColumns.add(i);
35            waysToColor[i] = 1;
36        }
37    }
38
39    // Map to store compatible column pairs
40    const compatibleColumns: Map<number, number[]> = new Map();
41    for (const column1 of validColumns) {
42        for (const column2 of validColumns) {
43            if (areColumnsCompatible(column1, column2)) {
44                compatibleColumns.set(column1, (compatibleColumns.get(column1) || []).concat(column2));
45            }
46        }
47    }
48
49    const mod = 10 ** 9 + 7;
50
51    // Calculate the number of ways to color the grid column by column
52    for (let k = 1; k < n; ++k) {
53        const nextWaysToColor: number[] = Array(maxState).fill(0);
54
55        // Update the number of ways to color based on the previous column
56        for (const column1 of validColumns) {
57            for (const column2 of compatibleColumns.get(column1) || []) {
58                nextWaysToColor[column1] = (nextWaysToColor[column1] + waysToColor[column2]) % mod;
59            }
60        }
61        // Move to the next column
62        waysToColor.splice(0, waysToColor.length, ...nextWaysToColor);
63    }
64
65    let result = 0;
66    // Sum all ways to color the grid
67    for (const count of waysToColor) {
68        result = (result + count) % mod;
69    }
70  
71    return result;
72}
73

Time and Space Complexity

The time complexity of the given code can be analyzed through the following considerations:

  • f1 Function: The f1 function is a helper function that checks if a particular state (encoded as an integer x) represents a valid coloring configuration for a column of the grid. To do so, it iterates through m elements to make sure that no two adjacent cells are colored the same. Since it involves a loop of size m, the time complexity of f1 is O(m).

  • f2 Function: Similar to f1, the f2 function checks the compatibility of two adjacent columns, represented by the states x and y. For each element in the column (m of them), it compares cells from both states to ensure they don't match. Thus, f2 also has a time complexity of O(m).

  • Valid States Generation: The code generates all possible states for a column and stores those that are valid in the valid set. Since there are 3^m possible states (each of the m cells can be in one of 3 colors), and each state is checked with f1, the time complexity for this part is O(m * 3^m).

  • Adjacency Dictionary Creation: For each valid column state, we check which states can follow it by using f2. This means that we compare each state with every other state, resulting in a complexity of O(3^m * 3^m) for this step. However, since f2 is O(m), the total time for creating the adjacency dictionary is O(m * 3^{2m}).

  • Dynamic Programming (DP) Loop: Finally, the DP computation is performed for n - 1 iterations (since the first column is already considered). In each iteration, for each of the 3^m valid states, we iterate through its neighbors (which are at most 3^m). The update is constant time, hence this part contributes O(n * 3^m * 3^m) to the time complexity.

Adding up all these contributions, the dominant term, particularly due to the DP loop, gives us the overall time complexity of O((m + n) * 3^{2m}).

As for the space complexity, the factors contributing to it are as follows:

  • Valid Set and DP Array: The valid set and the f array both store information for 3^m states, thus each having a space complexity of O(3^m).

  • Adjacency Dictionary: d is a dictionary that, for each valid state, stores possible following states. In the worst case, it can store 3^m keys with 3^m entries each, which seems to suggest O(3^{2m}). However, since no two adjacent columns can have the same state, the number of entries per key is far less than 3^m. Nevertheless, we only consider the space taken by the largest data structure for space complexity, ignoring constants and lower order terms.

In light of the above, the space complexity of the algorithm is O(3^m).

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!


Load More