April 17, 2020
LeetCode 1411: Number of Ways to Paint N x 3 Grid

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 colours: RedYellow or Green while making sure that no two adjacent cells have the same colour (i.e no two cells that share vertical or horizontal sides have the same colour).

You are 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.

 

Solution:

This is a DP (Dynamic Programming) problem. We calculate the simple problems and store their results. Using the results of the simple problems we solve the given bigger problem!

Let's start from one row grid

1 x 3 grid: 

Number of ways to paint 1x3 grid using 3 colors (source: leetcode.com)

Then it boils down to a simple permutation problem. We can paint this in 27 ways (3 x 3 x 3) but only 12 of them will be valid as per the problem description. The possible color combinations are shown in the above figure. We can approach this as

Number of ways using two colors: 121, 212, 131, 313, 232, 323

Number of ways using three colors: 123, 132, 213, 231, 312, 321

2 x 3 grid:

We've already solved the first row. Now we solve for the second row

Assume first row has 121:

  • Using two colors: 212, 313, 232
  • Using three colors: 123, 321

Assume first row has 123:

  • Using two colors: 212, 232
  • Using three colors: 312, 231

For ith of row we can write a recursive euation as follows.

Note: C2i, C3i, represents number of ways possible for ith row with two colors and three colors respectivelt.

C2i (no of ways using two colors) = (C2i-1  x 3) + (C3i-1  x 2)

Similarly

C3i (no of ways using three colors) = (C2i-1  x 2) + (C3i-1  x 2)

In case of i=2, C2i-1 = C3i-1 = 6

class Solution:
    def numOfWays(self, n: int) -> int:
        # Ways to color first row using 3 colors
        c3 = 6
        # ways to color first row using 2 colors
        c2 = 6
        
        mod = 10 ** 9 + 7
        for i in range(1, n):
            temp2 = c3 * 2 + c2 * 3
            temp3 = c3 * 2 + c2 * 2
            c3 = temp3 % mod
            c2 = temp2 % mod

        return (c3 + c2) % mod

 

 

Credit: leetcode, hiclipart