How hard is LeetCode 1411. Number of Ways to Paint N × 3 Grid?

LeetCode 1411. Number of Ways to Paint N × 3 Grid is rated Hard on LeetCode.

What is the time complexity of LeetCode 1411. Number of Ways to Paint N × 3 Grid?

The Python solution on this page runs in O(n), where n is the number of rows in the grid.

What is the space complexity of LeetCode 1411. Number of Ways to Paint N × 3 Grid?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 1411. Number of Ways to Paint N × 3 Grid cover?

LeetCode 1411. Number of Ways to Paint N × 3 Grid is tagged Dynamic Programming on LeetCode.

Number of Ways to Paint N × 3 Grid — LeetCode 1411 Python Solution

HardDynamic Programming

Problem: #1411
Pattern: Dynamic Programming
Reading time: 2 min
Source: leetcode.com

The problem

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.

Example

Input: n = 1
Output: 12
Explanation: There are 12 possible way to paint the grid as shown.

Python solution

Python

class Solution:
    def numOfWays(self, n: int) -> int:
        mod = 10**9 + 7
        f0 = f1 = 6
        for _ in range(n - 1):
            g0 = (3 * f0 + 2 * f1) % mod
            g1 = (2 * f0 + 2 * f1) % mod
            f0, f1 = g0, g1
        return (f0 + f1) % mod

Complexity

Measure	Complexity
Time	O(n), where n is the number of rows in the grid
Space	O(1) auxiliary

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1411. Number of Ways to Paint N × 3 Grid is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1411. Number of Ways to Paint N × 3 Grid?: LeetCode 1411. Number of Ways to Paint N × 3 Grid is rated Hard on LeetCode.
What is the time complexity of LeetCode 1411. Number of Ways to Paint N × 3 Grid?: The Python solution on this page runs in O(n), where n is the number of rows in the grid.
What is the space complexity of LeetCode 1411. Number of Ways to Paint N × 3 Grid?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1411. Number of Ways to Paint N × 3 Grid cover?: LeetCode 1411. Number of Ways to Paint N × 3 Grid is tagged Dynamic Programming on LeetCode.