Problem Statement in English

You’re given an integer n. You need to paint an n x 3 grid such that no two adjacent cells have the same color.

Return the number of ways you can paint this grid. Since the answer may be very large, return it modulo 109+710^9 + 7.

Approach

So! This is a LeetCode hard :)

If you think about it, there are overlapping subproblems here. The number of ways to paint the i-th row depends on how we painted the (i-1)-th row. So you can actually map out the states and go through the transitions, and calculate the number of ways to paint the grid row by row.

Another way, which I found online, is to actually see what the possible patterns are for each row.

If you think about it, there are only two possible patterns for each row: either aba or abc, where a, b, and c are different colors. This is because the question says there are only 3 colors available. Also, no two adjacent cells can have the same color.

When you have aba in the current row, the next row can be painted in either cac, bab, or bcb patterns. This is because the first and last cells cannot be painted with color a, and the middle cell cannot be painted with color b.

  • From: aba

    aba:cac,bab,bcb abc:cab,bac

When you have abc in the current row, the next row can be painted in either cab, bca, bac, or cac patterns. This is because the first cell cannot be painted with color a, the middle cell cannot be painted with color b, and the last cell cannot be painted with color c.

  • From: abc

    aba:bab,bcb abc:cab,bca

And so, we can simply keep track of the number of ways to paint the grid with aba and abc patterns for each row, and update them based on the transitions above.

We could start with either pattern for the first row. There are 6 ways to paint the first row with aba pattern, and 6 ways to paint the first row with abc pattern.

Then, for each subsequent row, we can update the number of ways to paint the grid with aba and abc patterns based on the transitions above.

Finally, we can return the sum of the number of ways to paint the grid with aba and abc patterns for the last row, modulo 109+710^9 + 7.

Solution in Python


class Solution:
    def numOfWays(self, n: int) -> int:
        MOD = 10 ** 9 + 7

        aba, abc = 6, 6

        for _ in range(n - 1):
            next_aba = (3 * aba + 2 * abc) % MOD
            next_abc = (2 * aba + 2 * abc) % MOD

            aba, abc = next_aba, next_abc

        return (aba + abc) % MOD

Complexity

  • Time: O(n)O(n)
    Since we have to iterate n - 1 times to calculate the number of ways to paint the grid.

  • Space: O(1)O(1)
    We are using only a constant amount of space to store the intermediate results.

Mistakes I Made

I had to look this up :(

And we are done.