1411. Number of Ways to Paint N × 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 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 109 + 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

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(n)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
const numOfWays = function (n) {
  const MODULO = 10 ** 9 + 7;
  let colors2 = 6; // 010 020 101 121 202 212
  let colors3 = 6; // 012 021 102 120 201 210

  for (let row = 1; row < n; row++) {
    // 010 -> 101 121 202, 102 201
    const nextColors2 = colors2 * 3 + colors3 * 2;
    // 012 -> 101 121, 120 201
    const nextColors3 = colors2 * 2 + colors3 * 2;

    colors2 = nextColors2 % MODULO;
    colors3 = nextColors3 % MODULO;
  }
  return (colors2 + colors3) % MODULO;
};