Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1931.html

1931. Painting a Grid With Three Different Colors

Level

Hard

Description

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 10^9 + 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

There are m rows and n columns. For each column, precalculate all legal states such that no two adjacent cells have the same color, and precalculate all pairs of column states that can be two adjacent columns. Then for each column, calculate the number of ways to paint all columns up to the column. Finally, return the number of ways to paint all n columns.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int colorTheGrid(int m, int n) {
          final int MODULO = 1000000007;
          List<Integer> types = new ArrayList<Integer>();
          int maxCount = (int) Math.pow(3, m);
          for (int i = 0; i < maxCount; i++) {
              if (adjacentDistinct(i, m))
                  types.add(i);
          }
          int typeCnt = types.size();
          int[][] related = new int[typeCnt][typeCnt];
          for (int i = 0; i < typeCnt; i++) {
              int type1 = types.get(i);
              int[] arr1 = new int[m];
              for (int k = m - 1; k >= 0 && type1 > 0; k--) {
                  arr1[k] = type1 % 3;
                  type1 /= 3;
              }
              for (int j = 0; j < typeCnt; j++) {
                  int type2 = types.get(j);
                  int[] arr2 = new int[m];
                  for (int k = m - 1; k >= 0 && type2 > 0; k--) {
                      arr2[k] = type2 % 3;
                      type2 /= 3;
                  }
                  boolean flag = true;
                  for (int k = 0; k < m; k++) {
                      if (arr1[k] == arr2[k]) {
                          flag = false;
                          break;
                      }
                  }
                  if (flag)
                      related[i][j] = 1;
              }
          }
          int[][] f = new int[n + 1][typeCnt];
          for (int i = 0; i < typeCnt; i++)
              f[1][i] = 1;
          for (int i = 2; i <= n; i++) {
              for (int j = 0; j < typeCnt; j++) {
                  for (int k = 0; k < typeCnt; k++) {
                      if (related[k][j] != 0)
                          f[i][j] = (f[i][j] + f[i - 1][k]) % MODULO;
                  }
              }
          }
          int count = 0;
          for (int j = 0; j < typeCnt; j++)
              count = (count + f[n][j]) % MODULO;
          return count;
      }
  
      public boolean adjacentDistinct(int num, int m) {
          int prev = -1;
          for (int i = 0; i < m; i++) {
              int curr = num % 3;
              if (curr == prev)
                  return false;
              prev = curr;
              num /= 3;
          }
          return true;
      }
  }
  

• // OJ: https://leetcode.com/problems/painting-a-grid-with-three-different-colors/
  // Time: O(V^2 * M + VNM) where V is the count of valid column vectors
  // Space: O(V^2)
  class Solution {
      vector<unordered_map<int, long>> dp;
      long mod = 1e9 + 7;
      vector<string> states;
      vector<vector<int>> G;
      void getStates(int len, int prev, string &s) {
          if (s.size() == len) {
              states.push_back(s);
              return;
          }
          for (int j = 0; j < 3; ++j) {
              if (prev == j) continue;
              s += '0' + j;
              getStates(len, j, s);
              s.pop_back();
          }
      }
      bool areNeighbors(string &a, string &b) {
          for (int i = 0; i < a.size(); ++i)  {
              if (a[i] == b[i]) return false;
          }
          return true;
      }
      long dfs(int len, int u) {
          if (len == 1) return 1;
          if (dp[len].count(u)) return dp[len][u];
          long ans = 0;
          for (int v : G[u]) {
              ans = (ans + dfs(v, len - 1)) % mod;
          }
          return dp[len][u] = ans;
      }
  public:
      int colorTheGrid(int m, int n) {
          string s;
          getStates(m, -1, s);
          int N = states.size();
          G.assign(N, {});
          for (int i = 0; i < N; ++i) {
              for (int j = 0; j < N; ++j) {
                  if (areNeighbors(states[i], states[j])) {
                      G[i].push_back(j);
                  }
              }
          }
          long ans = 0;
          dp.assign(n + 1, {});
          for (int i = 0; i < N; ++i) ans = (ans + dfs(n, i)) % mod;
          return ans;
      }
  };
  

• class Solution:
      def colorTheGrid(self, m: int, n: int) -> int:
          def f1(x: int) -> bool:
              last = -1
              for _ in range(m):
                  if x % 3 == last:
                      return False
                  last = x % 3
                  x //= 3
              return True
  
          def f2(x: int, y: int) -> bool:
              for _ in range(m):
                  if x % 3 == y % 3:
                      return False
                  x, y = x // 3, y // 3
              return True
  
          mod = 10**9 + 7
          mx = 3**m
          valid = {i for i in range(mx) if f1(i)}
          d = defaultdict(list)
          for x in valid:
              for y in valid:
                  if f2(x, y):
                      d[x].append(y)
          f = [int(i in valid) for i in range(mx)]
          for _ in range(n - 1):
              g = [0] * mx
              for i in valid:
                  for j in d[i]:
                      g[i] = (g[i] + f[j]) % mod
              f = g
          return sum(f) % mod
  
  

• func colorTheGrid(m int, n int) (ans int) {
  	f1 := func(x int) bool {
  		last := -1
  		for i := 0; i < m; i++ {
  			if x%3 == last {
  				return false
  			}
  			last = x % 3
  			x /= 3
  		}
  		return true
  	}
  	f2 := func(x, y int) bool {
  		for i := 0; i < m; i++ {
  			if x%3 == y%3 {
  				return false
  			}
  			x /= 3
  			y /= 3
  		}
  		return true
  	}
  	mx := int(math.Pow(3, float64(m)))
  	valid := map[int]bool{}
  	f := make([]int, mx)
  	for i := 0; i < mx; i++ {
  		if f1(i) {
  			valid[i] = true
  			f[i] = 1
  		}
  	}
  	d := map[int][]int{}
  	for i := range valid {
  		for j := range valid {
  			if f2(i, j) {
  				d[i] = append(d[i], j)
  			}
  		}
  	}
  	const mod int = 1e9 + 7
  	for k := 1; k < n; k++ {
  		g := make([]int, mx)
  		for i := range valid {
  			for _, j := range d[i] {
  				g[i] = (g[i] + f[j]) % mod
  			}
  		}
  		f = g
  	}
  	for _, x := range f {
  		ans = (ans + x) % mod
  	}
  	return
  }
  

• function colorTheGrid(m: number, n: number): number {
      const f1 = (x: number): boolean => {
          let last = -1;
          for (let i = 0; i < m; ++i) {
              if (x % 3 === last) {
                  return false;
              }
              last = x % 3;
              x = Math.floor(x / 3);
          }
          return true;
      };
      const f2 = (x: number, y: number): boolean => {
          for (let i = 0; i < m; ++i) {
              if (x % 3 === y % 3) {
                  return false;
              }
              x = Math.floor(x / 3);
              y = Math.floor(y / 3);
          }
          return true;
      };
      const mx = 3 ** m;
      const valid = new Set<number>();
      const f: number[] = Array(mx).fill(0);
      for (let i = 0; i < mx; ++i) {
          if (f1(i)) {
              valid.add(i);
              f[i] = 1;
          }
      }
      const d: Map<number, number[]> = new Map();
      for (const i of valid) {
          for (const j of valid) {
              if (f2(i, j)) {
                  d.set(i, (d.get(i) || []).concat(j));
              }
          }
      }
      const mod = 10 ** 9 + 7;
      for (let k = 1; k < n; ++k) {
          const g: number[] = Array(mx).fill(0);
          for (const i of valid) {
              for (const j of d.get(i) || []) {
                  g[i] = (g[i] + f[j]) % mod;
              }
          }
          f.splice(0, f.length, ...g);
      }
      let ans = 0;
      for (const x of f) {
          ans = (ans + x) % mod;
      }
      return ans;
  }
  
  

All Problems

All Solutions