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 EvaluatorExample 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 integerx
) represents a valid coloring configuration for a column of the grid. To do so, it iterates throughm
elements to make sure that no two adjacent cells are colored the same. Since it involves a loop of sizem
, the time complexity off1
isO(m)
. -
f2 Function: Similar to
f1
, thef2
function checks the compatibility of two adjacent columns, represented by the statesx
andy
. 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 ofO(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 are3^m
possible states (each of them
cells can be in one of 3 colors), and each state is checked withf1
, the time complexity for this part isO(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 ofO(3^m * 3^m)
for this step. However, sincef2
isO(m)
, the total time for creating the adjacency dictionary isO(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 the3^m
valid states, we iterate through its neighbors (which are at most3^m
). The update is constant time, hence this part contributesO(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 thef
array both store information for3^m
states, thus each having a space complexity ofO(3^m)
. -
Adjacency Dictionary:
d
is a dictionary that, for each valid state, stores possible following states. In the worst case, it can store3^m
keys with3^m
entries each, which seems to suggestO(3^{2m})
. However, since no two adjacent columns can have the same state, the number of entries per key is far less than3^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.
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
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Don’t Miss This!