1579. Number of Ways to Paint N 3 Grid

1579. Number of Ways to Paint N × 3 Grid

Difficulty: Hard

Topics: Dynamic Programming, Weekly Contest 184

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⁹ + 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

Hint:

1. We will use Dynamic programming approach. we will try all possible configuration.
2. Let dp[idx][prev1col][prev2col][prev3col] be the number of ways to color the rows of the grid from idx to n-1 keeping in mind that the previous row (idx - 1) has colors prev1col, prev2col and prev3col. Build the dp array to get the answer.

Solution:

We are given an n x 3 grid. We need to paint each cell with one of three colors (Red, Yellow, Green) such that no two adjacent cells (sharing a side) have the same color.

Approach:

1. Generate Valid Row Patterns
   
   Each row of the grid has 3 cells, and adjacent cells in the same row must have different colors. With 3 colors, there are exactly 12 valid color patterns for a row. These are generated by considering all permutations of colors (0,1,2) where the first and second cells differ, and the second and third cells differ (the first and third may be the same).

2. Build Transition Matrix
   
   For any two row patterns, check if they can be placed in adjacent rows. This requires that for every column, the colors in the two rows are different. A 12×12 binary matrix trans is constructed, where trans[i][j] = 1 if pattern i (previous row) and pattern j (current row) are compatible.

3. Dynamic Programming
   
   Let dp[j] be the number of ways to paint the grid up to the current row, ending with pattern j in the current row.

   • For the first row, dp[j] = 1 for all 12 patterns.
   • For each subsequent row, compute a new array next_dp where next_dp[j] is the sum of dp[k] over all patterns k such that trans[k][j] = 1.
   • Update dp = next_dp for the next iteration.
   • The process repeats for n-1 rows (since the first row is already initialized).

4. Result
   
   After processing all rows, the answer is the sum of dp[j] over all patterns j, taken modulo 10⁹ + 7.

Let's implement this solution in PHP: 1579. Number of Ways to Paint N × 3 Grid

<?php
/**
 * @param Integer $n
 * @return Integer
 */
function numOfWays($n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo numOfWays(1) . "\n";       // Output: 12
echo numOfWays(5000) . "\n";    // Output: 30228214
?>

Explanation:

• The problem reduces to counting sequences of row patterns where adjacent rows are compatible.
• Each row pattern is a triple of colors representing the three cells in that row.
• Compatibility between rows is determined column-wise: colors in the same column must differ.
• Dynamic programming efficiently accumulates the number of valid ways row by row, using the transition matrix to ensure compatibility.
• The time complexity is O(n . 12²) = O(144n), which is efficient for n ≤ 5000.

Complexity

• Time Complexity: O(n . 12²) = O(144n), which is linear in n and efficient for n ≤ 5000.
• Space Complexity: O(12²) for the transition matrix and O(12) for the DP arrays, i.e., constant space.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub