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


  • 9
    E

    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);
                }
                return total;
            }
        };
    

    Ask me anything. No question is silly.


  • 0
    P

    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?


  • 0
    E

    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


  • 0
    E
    This post is deleted!

  • 0
    P

    Thanks! that makes sense.


Log in to reply
 

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