Number of Ways to Paint N × 3 Grid

Problem Description

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

Key Insights

• Each cell can be painted in one of three colors.
• Adjacent cells (vertically and horizontally) cannot be painted the same color.
• The problem can be solved using dynamic programming by breaking it down into smaller subproblems based on previous rows.
• The number of ways to paint the grid can be derived from the number of ways to paint the previous row.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The approach to solve this problem involves dynamic programming. We define dp[i] as the number of ways to paint a grid of size i x 3.

1. For the first row (n=1), there are 3 * 4 = 12 ways to paint it, as each of the three cells can be painted in 3 colors, and there are 4 options for the second cell (not the same as the first).
2. For subsequent rows, the number of ways to paint the grid can be derived from the previous row's configurations. Specifically, we can use a recurrence relation that accounts for the previous row's valid configurations.
3. We can use two variables to track the number of ways to paint the last row and the second last row, which allows us to keep our space complexity constant.

Code Solutions