1411. Number of Ways to Paint N × 3 Grid LeetCode Solution
In this guide, you will get 1411. Number of Ways to Paint N × 3 Grid LeetCode Solution with the best time and space complexity. The solution to Number of Ways to Paint N × Grid problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Ways to Paint N × Grid
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
1411. Number of Ways to Paint N × 3 Grid LeetCode Solution in C++
class Solution {
public:
int numOfWays(int n) {
constexpr int kMod = 1'000'000'007;
long color2 = 6; // 121, 131, 212, 232, 313, 323
long color3 = 6; // 123, 132, 213, 231, 312, 321
for (int i = 1; i < n; ++i) {
const long nextColor2 = color2 * 3 + color3 * 2;
const long nextColor3 = color2 * 2 + color3 * 2;
color2 = nextColor2 % kMod;
color3 = nextColor3 % kMod;
}
return (color2 + color3) % kMod;
}
}; /* code provided by PROGIEZ */
1411. Number of Ways to Paint N × 3 Grid LeetCode Solution in Java
class Solution {
public int numOfWays(int n) {
final int kMod = 1_000_000_007;
long color2 = 6; // 121, 131, 212, 232, 313, 323
long color3 = 6; // 123, 132, 213, 231, 312, 321
for (int i = 1; i < n; ++i) {
final long nextColor2 = color2 * 3 + color3 * 2;
final long nextColor3 = color2 * 2 + color3 * 2;
color2 = nextColor2 % kMod;
color3 = nextColor3 % kMod;
}
return (int) ((color2 + color3) % kMod);
}
} // code provided by PROGIEZ
1411. Number of Ways to Paint N × 3 Grid LeetCode Solution in Python
