Painting a Grid With Three Different Colors Solution in Java

Problem Description

So, you want to paint a grid with three different colors, huh? Sounds easy, right? Just grab a paintbrush and go wild! But wait, there’s a catch! You can’t have the same color in adjacent cells. It’s like trying to pick a color for your living room while your partner insists on a color that doesn’t clash with the couch. Good luck with that!

Imagine you have a grid of size m x n, and you have three colors to choose from. Your task is to find out how many ways you can paint this grid while following the “no adjacent colors” rule. It’s like a game of Tetris, but instead of blocks, you have colors, and instead of fun, you have a headache!

Code Solution


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;
  }

  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;
  }
}

Approach Explanation

The solution employs a dynamic programming approach to explore all possible ways to paint the grid. It uses a recursive function dp that takes the current row and column, along with masks representing the colors of the previous and current columns. The function checks for valid color placements and accumulates the count of valid configurations.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n * 4^m) - The function explores all possible color combinations for each column, leading to an exponential growth based on the number of rows.
Space Complexity	O(n * 2^m) - The memoization table stores results for each column and color combination.

Real-World Example

Think of this problem like organizing a colorful party where you have to arrange tables in a grid. Each table can be painted in red, green, or blue, but you can’t have two adjacent tables in the same color. If you mess this up, your guests might think you have no taste!