Complete Explanation O(n) time +O(1) Space

• Explanation:
As we can paint at most two adjacent posts with same color, we can never have such a situation: For example: BBBW or WWWB or BWWW or BWWW. Here B = Black, W = White.

Let's say we start painting from left side. Posts will look like this:
|^|..|^|..|^|..|^|

Here there are 4 posts. So n = 4.

Now for painting, i = 1, Post #1, we have.

`````` 1. sameColor = 0 as there is no Post #(i-1)
2. diffColor = k. because we can use any 1 of the k colors.
3. total = sameColor + diffColor = 0 + k = k
``````

At any given Post i, i > 1, we can have two ways

`````` 1. sameColor = Paint with same color as Post #(i-1)
2. diffColor = Paint with different color than Post #(i-1)
3. total = sameColor + diffColor
``````

Or,

`````` 1. sameColor = diffColor*1 = diffColor of Post #(i-1)
2. diffColor = (k-1)*total at Post #(i-1)
3. total = sameColor + diffColor
``````

For diffColor, We multiply total by k-1 because you can use any color except 1 color which was the previous.

``````
class Solution {
public:
int numWays(int n, int k) {
if(k==0 || n == 0 || (n>2 && k==1) ) return 0;
int sameColor = 0;
int diffColor = k;
int total = diffColor + sameColor;
for(int i=2; i<=n; i++){
sameColor = diffColor;
diffColor = (k-1)*total;
total = (diffColor+sameColor);
}
}
};
``````

Ask me anything. No question is silly.

• Hi Thank you for the detailed explanation. I get your solution except for calculating `sameColor` on each iteration. How is it `diffColor * 1` and what does the 1 signify?

• For Post #(i-1), there are k = diffColor choices
For Post(#1) if we want the same color as Post #(i-1), we have only 1 way. This means in total we have k1 total choices if we want the same color. 1 here signifies that for current Pos #i, we have only 1 choice if want same color as previous one. Think like this.
If you have only 4 colors, A, B, C, D.
You painted Post #(i-2) with B.
So for coloring Post#(i) with same color as Post #(i-1).. You cannot have B at Post#(i-1). Else B will be on three posts i-1, i, i+1.
You need to go with a differentColor for Post#(i-1) and then use that same color for Post#(i).
We have 3 choices for #(i-1) i.e. A, C, D. Whichever color we choose for i-1, For i we have to chose the same color for counting sameColor. So sameColor = 3
1 = 3

• This post is deleted!

• Thanks! that makes sense.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.