{x}
blog image

Painting a Grid With Three Different Colors

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 109 + 7.

 

Example 1:

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

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 <= m <= 5
  • 1 <= n <= 1000

Solution Explanation: Painting a Grid With Three Different Colors

This problem asks to find the number of ways to color an m x n grid with three colors (red, green, blue) such that no two adjacent cells have the same color. Because the answer can be very large, we need to use modulo arithmetic. The constraint 1 <= m <= 5 and 1 <= n <= 1000 suggests a dynamic programming approach with state compression.

Approach:

The core idea is to represent the coloring of each column as a state. Since there are m rows and 3 color choices per row, there are 3^m possible states for a single column. We can represent each state as an integer, where each digit in base 3 corresponds to the color of a row.

  1. State Representation: A number state represents a column's coloring. Each digit in the base 3 representation of state corresponds to a row: 0, 1, and 2 represent red, green, and blue, respectively. For example, if m = 3 and state = 5, the base 3 representation is 120 (because 5 = 13^2 + 23^1 + 0*3^0), representing the column with colors green, blue, and red in rows 1, 2, and 3, respectively.

  2. Validity Check: We need a function f1(state) to check if a state is valid. A state is invalid if any adjacent rows have the same color. This is easily checked by examining consecutive digits in the base 3 representation.

  3. Transition Function: We define f2(prev_state, curr_state) to check if the transition from prev_state to curr_state is valid. This means no two adjacent rows should have the same color across columns. This is also checked by comparing consecutive rows in base 3.

  4. Dynamic Programming: We use a DP array dp[i][state] to store the number of ways to color the first i columns such that the last column is in state. The base case is dp[1][state] = 1 if state is valid, otherwise 0. The recurrence relation is:

    dp[i][curr_state] = (sum of dp[i-1][prev_state] for all valid prev_state such that f2(prev_state, curr_state)) % mod

  5. Optimization: Since dp[i] only depends on dp[i-1], we can use a rolling array of size 2 to save space.

  6. Final Answer: The final answer is the sum of all dp[n][state] values for all valid states state.

Time and Space Complexity:

  • Time Complexity: O((m+n) * 3^(2m)). The outer loop iterates n times. The inner loop iterates through all possible pairs of valid states, which is approximately 3^m * 3^m. The validity checks f1 and f2 take O(m) time.

  • Space Complexity: O(3^m). We use a DP array with a size proportional to the number of possible states for a column (3^m). The rolling array optimization reduces the space to O(3^m).

Code Explanation (Python):

The Python code implements the above algorithm efficiently using the described state representation, validity checks, and dynamic programming. The defaultdict efficiently handles the adjacency mapping between states. The % mod operation ensures we stay within the required modulo range.

The other languages (Java, C++, Go, TypeScript) follow the same logic with appropriate adaptations to their syntax and data structures. For example, Java uses HashSet and HashMap, while C++ employs unordered_set and unordered_map. Go utilizes built-in maps and slices. TypeScript employs Set and Map. The core algorithm remains consistent across all implementations.