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.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Painting a Grid With Three Different Colors solution in C++
  4. Painting a Grid With Three Different Colors solution in Java
  5. Painting a Grid With Three Different Colors solution in Python
  6. Additional Resources
1931. Painting a Grid With Three Different Colors LeetCode Solution image

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

Additional Resources

See also  2678. Number of Senior Citizens LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.