Scale Engineer

Number of Ways to Paint N × 3 Grid

Hard
#1306Time: O(n) - We perform a single loop from `i=2` to `n`, with constant time operations inside.Space: O(n) - We use two arrays of size `n+1` to store the DP states for each row.1 company
Patterns
Dynamic Programming
Companies
Fortinet

Prompt

You have a grid of size n x 3 and you want to paint each cell of the grid with exactly one of the three colors: Red, Yellow, or Green while making sure that no two adjacent cells have the same color (i.e., no two cells that share vertical or horizontal sides have the same color).

Given n the number of rows of the grid, return the number of ways you can paint this grid. As the answer may grow large, the answer must be computed modulo 109 + 7.

 

Example 1:

Input: n = 1
Output: 12
Explanation: There are 12 possible way to paint the grid as shown.

Example 2:

Input: n = 5000
Output: 30228214

 

Constraints:

  • n == grid.length
  • 1 <= n <= 5000

Approaches

3 approaches with complexity analysis and trade-offs.

This problem has optimal substructure and overlapping subproblems, making it a perfect candidate for dynamic programming. The core idea is that the number of ways to color any given row i depends solely on the valid colorings of the previous row, i-1.

First, we analyze the valid colorings for a single row. A row has 3 cells, and adjacent cells must have different colors. This gives rise to two types of color patterns:

  1. Two-Color Patterns (ABA type): The first and third cells are the same color, while the middle cell is different (e.g., Red-Yellow-Red). There are 3 choices for the first color and 2 for the second, totaling 3 * 2 = 6 such patterns.
  2. Three-Color Patterns (ABC type): All three cells have different colors (e.g., Red-Yellow-Green). There are 3 * 2 * 1 = 6 such patterns.

For n=1, the total number of ways is 6 + 6 = 12.

Algorithm

  • Define two DP arrays, twoColor and threeColor, of size n+1.
  • twoColor[i] will store the number of ways to paint the first i rows with the i-th row having a two-color (ABA) pattern.
  • threeColor[i] will store the number of ways to paint the first i rows with the i-th row having a three-color (ABC) pattern.
  • Set the base cases for i=1: twoColor[1] = 6 and threeColor[1] = 6.
  • Iterate from i = 2 to n and apply the following recurrence relations:
    • twoColor[i] = (3 * twoColor[i-1] + 2 * threeColor[i-1]) % MOD
    • threeColor[i] = (2 * twoColor[i-1] + 2 * threeColor[i-1]) % MOD
  • The final answer is the sum of twoColor[n] and threeColor[n], modulo MOD.

Walkthrough

We can build a DP solution based on these two pattern types. We'll define DP states to count the number of ways to paint the grid up to row i ending with each pattern type.

Let:

  • twoColor[i] be the number of ways to paint an i x 3 grid where row i has a two-color (ABA) pattern.
  • threeColor[i] be the number of ways to paint an i x 3 grid where row i has a three-color (ABC) pattern.

We can establish recurrence relations by analyzing how a pattern in row i can follow a pattern in row i-1 without violating the color constraints.

  • Transitions to a two-color pattern in row i:

    • From a two-color pattern in row i-1: There are 3 valid ways.
    • From a three-color pattern in row i-1: There are 2 valid ways.
    • Thus, twoColor[i] = 3 * twoColor[i-1] + 2 * threeColor[i-1].

  • Transitions to a three-color pattern in row i:

    • From a two-color pattern in row i-1: There are 2 valid ways.
    • From a three-color pattern in row i-1: There are 2 valid ways.
    • Thus, threeColor[i] = 2 * twoColor[i-1] + 2 * threeColor[i-1].

The implementation involves creating two arrays to store these counts and iterating from i=2 to n to fill them. The final result is the sum of the counts for row n.

class Solution {    public int numOfWays(int n) {        if (n == 0) {            return 0;        }        long MOD = 1_000_000_007;         long[] twoColor = new long[n + 1];        long[] threeColor = new long[n + 1];         // Base case for n = 1        twoColor[1] = 6;        threeColor[1] = 6;         for (int i = 2; i <= n; i++) {            // Ways to form a two-color pattern in row i            twoColor[i] = (3 * twoColor[i - 1] + 2 * threeColor[i - 1]) % MOD;            // Ways to form a three-color pattern in row i            threeColor[i] = (2 * twoColor[i - 1] + 2 * threeColor[i - 1]) % MOD;        }         return (int) ((twoColor[n] + threeColor[n]) % MOD);    }}

Complexity

Time

O(n) - We perform a single loop from `i=2` to `n`, with constant time operations inside.

Space

O(n) - We use two arrays of size `n+1` to store the DP states for each row.

Trade-offs

Pros

  • Conceptually straightforward and easy to follow.

  • Directly translates the recurrence relation into code.

Cons

  • Uses linear space, which is not optimal and can be improved.

Solutions

class Solution {public  int numOfWays(int n) {    int mod = (int)1 e9 + 7;    long f0 = 6, f1 = 6;    for (int i = 0; i < n - 1; ++i) {      long g0 = (3 * f0 + 2 * f1) % mod;      long g1 = (2 * f0 + 2 * f1) % mod;      f0 = g0;      f1 = g1;    }    return (int)(f0 + f1) % mod;  }}

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