LeetCode 1411: Number of Ways to Paint N × 3 Grid Solution
Master LeetCode problem 1411 (Number of Ways to Paint N × 3 Grid), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
1411. Number of Ways to Paint N × 3 Grid
Problem Explanation
Explanation
To solve this problem, we can use dynamic programming. We can maintain three states for each column of the grid: color1, color2, and color3 representing the ways to paint the current column with each color. At each step, we can update the states based on the previous column's states and the constraints given in the problem.
Let's define the following transitions:
- color1 for the current column can be painted with color1, color2, or color3 from the previous column, as long as they are different.
- color2 for the current column can be painted with color1 or color3 from the previous column.
- color3 for the current column can be painted with color1 or color2 from the previous column.
The final answer will be the sum of the states of color1, color2, and color3 in the last column.
Solution Code
class Solution {
public int numOfWays(int n) {
long mod = 1000000007;
long color1 = 6, color2 = 6, color3 = 6;
for (int i = 1; i < n; i++) {
long newColor1 = (2 * color1 + 2 * color2) % mod;
long newColor2 = (2 * color1 + 3 * color2) % mod;
long newColor3 = (2 * color1 + 2 * color3) % mod;
color1 = newColor1;
color2 = newColor2;
color3 = newColor3;
}
return (int)((color1 + color2 + color3) % mod);
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 1411 (Number of Ways to Paint N × 3 Grid)?
This page provides optimized solutions for LeetCode problem 1411 (Number of Ways to Paint N × 3 Grid) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 1411 (Number of Ways to Paint N × 3 Grid)?
The time complexity for LeetCode 1411 (Number of Ways to Paint N × 3 Grid) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 1411 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1411 in Java, C++, or Python.