1931. Painting a Grid With Three Different Colors LeetCode Solution
In this guide, you will get 1931. Painting a Grid With Three Different Colors LeetCode Solution with the best time and space complexity. The solution to Painting a Grid With Three Different Colors problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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
Complexity Analysis
Time Complexity: O(n \cdot 3^m \cdot 2^m)
Space Complexity: O(n \cdot 4^m + 4^m \cdot 2^m)
1931. Painting a Grid With Three Different Colors LeetCode Solution in C++
class Solution {
public:
int colorTheGrid(int m, int n) {
this->m = m;
this->n = n;
return dp(0, 0, 0, 0);
}
private:
static constexpr int kMod = 1'000'000'007;
int m;
int n;
vector<vector<int>> mem = vector<vector<int>>(1000, vector<int>(1024));
int dp(int r, int c, int prevColMask, int currColMask) {
if (c == n)
return 1;
if (mem[c][prevColMask])
return mem[c][prevColMask];
if (r == m)
return dp(0, c + 1, currColMask, 0);
int ans = 0;
// 1 := red, 2 := green, 3 := blue
for (int color = 1; color <= 3; ++color) {
if (getColor(prevColMask, r) == color)
continue;
if (r > 0 && getColor(currColMask, r - 1) == color)
continue;
ans += dp(r + 1, c, prevColMask, setColor(currColMask, r, color));
ans %= kMod;
}
if (r == 0)
mem[c][prevColMask] = ans;
return ans;
}
// e.g. __ __ __ __ __
// 01 10 11 11 11
// R G B B B
// getColor(0110111111, 3) -> G
int getColor(int mask, int r) {
return mask >> r * 2 & 3;
}
int setColor(int mask, int r, int color) {
return mask | color << r * 2;
}
}; /* code provided by PROGIEZ */
1931. Painting a Grid With Three Different Colors LeetCode Solution in Java
class Solution {
public int colorTheGrid(int m, int n) {
this.m = m;
this.n = n;
return dp(0, 0, 0, 0);
}
private static final int kMod = 1_000_000_007;
private int m;
private int n;
private int[][] mem = new int[1000][1024];
private int dp(int r, int c, int prevColMask, int currColMask) {
if (c == n)
return 1;
if (mem[c][prevColMask] != 0)
return mem[c][prevColMask];
if (r == m)
return dp(0, c + 1, currColMask, 0);
int ans = 0;
// 1 := red, 2 := green, 3 := blue
for (int color = 1; color <= 3; ++color) {
if (getColor(prevColMask, r) == color)
continue;
if (r > 0 && getColor(currColMask, r - 1) == color)
continue;
ans += dp(r + 1, c, prevColMask, setColor(currColMask, r, color));
ans %= kMod;
}
if (r == 0)
mem[c][prevColMask] = ans;
return ans;
}
// e.g. __ __ __ __ __
// 01 10 11 11 11
// R G B B B
// getColor(0110111111, 3) -> G
private int getColor(int mask, int r) {
return mask >> r * 2 & 3;
}
private int setColor(int mask, int r, int color) {
return mask | color << r * 2;
}
} // code provided by PROGIEZ
1931. Painting a Grid With Three Different Colors LeetCode Solution in Python
class Solution:
def colorTheGrid(self, m: int, n: int) -> int:
def getColor(mask: int, r: int) -> int:
return mask >> r * 2 & 3
def setColor(mask: int, r: int, color: int) -> int:
return mask | color << r * 2
kMod = 1_000_000_007
@functools.lru_cache(None)
def dp(r: int, c: int, prevColMask: int, currColMask: int) -> int:
if c == n:
return 1
if r == m:
return dp(0, c + 1, currColMask, 0)
ans = 0
# 1 := red, 2 := green, 3 := blue
for color in range(1, 4):
if getColor(prevColMask, r) == color:
continue
if r > 0 and getColor(currColMask, r - 1) == color:
continue
ans += dp(r + 1, c, prevColMask, setColor(currColMask, r, color))
ans %= kMod
return ans
return dp(0, 0, 0, 0) # code by PROGIEZ
