Number of Ways to Paint N × 3 Grid

Problem Description

You are given a grid with n rows and 3 columns. Each cell must be painted with one of three colors – Red, Yellow, or Green – so that no two adjacent cells (sharing a common edge either vertically or horizontally) have the same color. Return the number of ways to paint the grid. Since the answer can be very large, return it modulo 10^9 + 7.

For example, when n = 1, there are 12 valid ways to paint the grid.

Key Insights

• Each row of 3 cells (with the horizontal-adjacency restriction) can be painted in 12 valid ways.
• These 12 colorings fall into two categories:
  • Type A: Patterns in which all 3 cells have distinct colors (6 possibilities).
  • Type B: Patterns in which the first and third cell share the same color (6 possibilities).
• The valid painting for the next row depends on the pattern category of the previous row. By carefully analyzing the vertical constraints (avoiding same color in the same column) alongside the horizontal condition within the row, we can derive transition rules between the two types:
  • From a Type A row:
    • Next row can be Type A in 3 ways.
    • Next row can be Type B in 2 ways.
  • From a Type B row:
    • Next row can be Type A in 2 ways.
    • Next row can be Type B in 2 ways.
• Use dynamic programming to update the number of ways row by row based on these transitions.

Space and Time Complexity

Time Complexity: O(n) – we iterate once through the n rows. Space Complexity: O(1) – only a constant amount of memory is used to store the counts for the two groups.

Solution

We solve the problem using a dynamic programming approach with two state variables:

• dpA: number of ways to paint the current row with a Type A (all different) pattern.
• dpB: number of ways to paint the current row with a Type B (first and third same) pattern.

For the first row, both dpA and dpB are 6 (total 12 valid patterns). For each subsequent row, we calculate:

• nextA = 3 * dpA (transitions from a previous Type A) + 2 * dpB (transitions from a previous Type B).
• nextB = 2 * dpA (transitions from a previous Type A) + 2 * dpB (transitions from a previous Type B).

After updating these values for each row, the final answer is (dpA + dpB) modulo 10^9 + 7. This solution uses constant space and processes each row in constant time.

Code Solutions