Scale Engineer

Painting a Grid With Three Different Colors

Hard
#1762Time: O(3^(m*n)). At each of the `m*n` cells, we might try up to 3 colors, leading to an exponential number of paths in the recursion tree. This is too slow for the given constraints.Space: O(m * n) to store the grid and for the recursion stack depth.
Patterns
Dynamic Programming

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach attempts to solve the problem by exploring every possible way to color the grid, one cell at a time, using recursion. For each cell, it tries to place one of the three colors, ensuring it doesn't conflict with its already colored top and left neighbors. If a valid coloring for the entire grid is found, a counter is incremented. This is a brute-force method that systematically checks all combinations.

Algorithm

  • Create a recursive function backtrack(row, col).
  • If row == m, a valid grid coloring is found. Increment the total count (modulo 10^9 + 7) and return.
  • Determine the next cell (next_row, next_col). If col + 1 == n, the next cell is (row + 1, 0); otherwise, it's (row, col + 1).
  • Iterate through the 3 colors for the current cell (row, col).
  • Check if the chosen color is valid by comparing it with the color of the cell above (grid[row-1][col]) and to the left (grid[row][col-1]).
  • If the color is valid, assign it to grid[row][col] and make a recursive call: backtrack(next_row, next_col).
  • After the recursive call returns, backtrack by resetting the cell's color to explore other possibilities (though this is implicitly handled by overwriting in the loop).

Walkthrough

We define a recursive function, say solve(row, col), that tries to color the cell at (row, col). The base case for the recursion is when we have successfully colored all cells (e.g., when row == m). At this point, we've found one valid way, so we increment our answer.

In the recursive step for solve(row, col), we iterate through the three colors (Red, Green, Blue). For each color, we check if placing it at (row, col) is valid. A color is valid if it's different from the color of the cell (row-1, col) (if row > 0) and the cell (row, col-1) (if col > 0).

If the color is valid, we place it in the grid and recursively call the function for the next cell. After the recursive call returns, we effectively "backtrack" by trying the next color for the current cell. This method explores the entire search space of colorings, pruning branches that violate the adjacency constraint as soon as they are detected.

class Solution {    int m, n;    long count = 0;    int MOD = 1_000_000_007;    int[][] grid;     public int colorTheGrid(int m, int n) {        this.m = m;        this.n = n;        // This approach will time out, but illustrates the concept.        // A real solution would not use this for the given constraints.        this.grid = new int[m][n]; // 1:Red, 2:Green, 3:Blue        backtrack(0, 0);        return (int) count;    }     private void backtrack(int row, int col) {        if (row == m) {            count = (count + 1) % MOD;            return;        }         int nextRow = row;        int nextCol = col + 1;        if (nextCol == n) {            nextRow = row + 1;            nextCol = 0;        }         for (int color = 1; color <= 3; color++) {            if (isSafe(row, col, color)) {                grid[row][col] = color;                backtrack(nextRow, nextCol);            }        }    }     private boolean isSafe(int row, int col, int color) {        // Check top neighbor        if (row > 0 && grid[row - 1][col] == color) {            return false;        }        // Check left neighbor        if (col > 0 && grid[row][col - 1] == color) {            return false;        }        return true;    }}

Complexity

Time

O(3^(m*n)). At each of the `m*n` cells, we might try up to 3 colors, leading to an exponential number of paths in the recursion tree. This is too slow for the given constraints.

Space

O(m * n) to store the grid and for the recursion stack depth.

Trade-offs

Pros

  • Conceptually simple and a direct translation of the problem statement.

  • Easy to implement for a first attempt.

Cons

  • Extremely inefficient due to its exponential time complexity.

  • Will result in a 'Time Limit Exceeded' (TLE) error on any reasonably sized grid.

Solutions

class Solution {private  int m;public  int colorTheGrid(int m, int n) {    this.m = m;    final int mod = (int)1 e9 + 7;    int mx = (int)Math.pow(3, m);    Set<Integer> valid = new HashSet<>();    int[] f = new int[mx];    for (int i = 0; i < mx; ++i) {      if (f1(i)) {        valid.add(i);        f[i] = 1;      }    }    Map<Integer, List<Integer>> d = new HashMap<>();    for (int i : valid) {      for (int j : valid) {        if (f2(i, j)) {          d.computeIfAbsent(i, k->new ArrayList<>()).add(j);        }      }    }    for (int k = 1; k < n; ++k) {      int[] g = new int[mx];      for (int i : valid) {        for (int j : d.getOrDefault(i, List.of())) {          g[i] = (g[i] + f[j]) % mod;        }      }      f = g;    }    int ans = 0;    for (int x : f) {      ans = (ans + x) % mod;    }    return ans;  }private  boolean f1(int x) {    int last = -1;    for (int i = 0; i < m; ++i) {      if (x % 3 == last) {        return false;      }      last = x % 3;      x /= 3;    }    return true;  }private  boolean f2(int x, int y) {    for (int i = 0; i < m; ++i) {      if (x % 3 == y % 3) {        return false;      }      x /= 3;      y /= 3;    }    return true;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem