Great explanation. Did a good job explaining the combinatorics part, also explained how and why the code is written the way it is to avoid bugs at 13:30 Most tutorials would just write the code that implements the algorithm without explaining how. Even with the typo, we can still understand where she's going.
@Miss Wright you have a small error in slide at time 6:18 Where you have mentioned 2 posts answers 2 posts answer.same + different k + k * (k+1) Shouldn't it be k + k * (k -1) (minus sign)
Hey maam, n=4, k= 3 , it gives 66 if draw all 66 according to the algorithm, then it causes conflict that more than 2 adjacent post have same color, but I think real ans is 60
At 6:16 I didn't get why it would be (k-1) colors to paint 3rd post in different case. For me it looks like K. For example, we painted the first post in Blue, then for the second one we have 2 choices: red and yellow (K-1). But the third one can be any again: Red, Blue or Yellow. Which is K. How did we get K-1. Could someone explain please?
In the equation for case 2, the next post must be different, so it is k-1 to make it different than the previous. Case 1 covers when the next post is the same. So yes, there are K or 3 possibilities for the 3rd post, but because this is broken into two cases, case 1 covers 1 color, and case 2 covers the other 2 colors.
Thank you for your explanation. I have some doubts at 2:41 where you mentioned if the two post have same color. If you paint 1st post with yellow color and as there is a catch that two adjacent posts may be in same color then second one must have k choices. So the same color number of choices should be k*k and not k*1. May be I am wrong. Can you please explain it again?
If the second post has to be the same as the first, then you had k choices for the first, but after you pick the first you only have one choice for the second which is whatever color you picked for the first. The reason you don't have k choices for the second is because that would mean the second could be any of k colors, which may or may not be the same as the first.
I remember I struggled to grasp this question for a long time. I did end up solving it but in real interviews I'd probably struggle big time. What's the secret? Practice and Pratice?
I think with practice you can get better, simply because you have seen more problems so you can begin to see connections. Practice will help, but it's not a 100% guarantee you will not struggle and unrealistic to expect to arrive at that point. Your interviews are supposed to measure how you think, not expect you to solve a difficult problem in less than an hour. Your interviewer is supposed to help you out if you struggle, which should also be a test in how you collaborate with colleagues.
For the recursive solution you could have another function set up similar to this, except the for loop would be the recursive call to a function that would essentially do the same thing as the for loop. If you watch my other 3 part video on the Fibonacci number, I go over how to set up a recursive solution and how to transform it into a dynamic programming solution.
Also, typically anytime you are storing old values and using those previously calculated values to calculate the final answer, then you're problem is a candidate for dynamic programming. It may be more complex than that, but that's the main thing I see.
The 3rd post needs to be different than the 2nd, so any color except 1( The 2nd Color). K - 1, means all the colors except the second, or all the colors except the previous color. At first I thought it would be K-2 for the 3rd post, but the 1st and 3rd colors do not have to be different.
@@buttekaustubhpradeep5566, the 2nd and 3rd post can have the same color, as long as it's not the same as the 1st post. In other words, if post 2 and 3 are the same, your only option for the first post is that it be different than post 2 and 3, otherwise you would have 3 consecutive posts the same color, which is a violation of the constraint.
@@misswright7247 What i meant to say is when we are counting no of ways for 3 posts we are doing same=k*(k-1)*1 ...i understood this but when calculating diff =k*(k-1)*(k-1) we are saying that first two posts are different then why is the no of options for the third post (k-1) and not k..because if we are considering that the first two colors are different then the third post can be any of the k colors, right? example the first two posts are red-yellow then the third post can be either red or yellow or green because that will not violate the constraint of more than 2 consecutive posts with same color....I am missing something in the? Thanks a lot for the quick reply :)
@@buttekaustubhpradeep5566, we are already counting the scenario when the 3rd post is the same, in the equation for same(red-yellow-yellow). Therefore the equation for different must subtract one choice for the 3rd color(red-yellow-red or red-yellow-blue), but not (red-yellow-yellow) again.
The third does not have to be different from the first. It needs to be different from the previous, so 1 is subtracted, and that 1 is for the previous.
The value of k adds another layer of complexity. For example, if k is 1 and there are more than 2 posts, it would violate the constraint that no more than 2 consecutive posts can be the same color. Other than 1 or 0 for k, I can't think of how the value of k may effect the solution.
This solution is so elegant. Before this, whenever I wanna do a DP problem, I also set up an array to save the states value. Thank you Miss. Wright!
You should make more videos. These are timeless. thx
Thank you for this. Thorough explanation with visuals along with implementation. Helped me understand the concept behind the problem.
Great explanation. Did a good job explaining the combinatorics part, also explained how and why the code is written the way it is to avoid bugs at 13:30 Most tutorials would just write the code that implements the algorithm without explaining how. Even with the typo, we can still understand where she's going.
Loved the way explained! Please do make more videos!
That is a very nice explaination. Thank you. Hoping to see more videos like this one.
Thank you so such clear explanation, and your visualization were really helpful! Props!
Yes! Upvote for the visualization!
Great Explanation! Thank you. Really Helpful!
This was the best explanation, I have ever seen. Thank you.
This was really helpful. You made it really easy to understand! Thanks!
Mam why did you stop uploading videos? we need this type of teachers.
@Miss Wright you have a small error in slide at time 6:18 Where you have mentioned 2 posts answers
2 posts answer.same + different
k + k * (k+1)
Shouldn't it be
k + k * (k -1) (minus sign)
Thank you! You are correct. The k+1 should be k-1. I didn't notice it until now.
Nice explanation. I wish I had a teacher like you in school. Thank you.
Nice explanation ...mam.
keep uploading these kind of dynamic programming problem videos.
this will help us.
Please make more videos on Leetcode problems. I really like you explanations!
The BEST explanation. THANK YOU :)
Fantastic Explanation. Clear and jusss perfect. You are a good teacher thanks for the video. Please upload more videos if time allows you to. Regards.
Thanks much for your explanation. It really works for me.
Great explanation, the intuition for this one is pretty tricky.
Clear explanation! Thank you!
Good explanation!!! Very helpful!
Thank you for such an easy solution !!!
Thanks, so clean explanation.
Thank you so much, I would really appreciate if you could make more Leetcode solution videos :)
Pretty clear and easy to understand. thx.
Wow!...such sweet explanation..please make more videos on dp problems.
Nice explanation. Thanks
Really really helpful... Thanks
Amazing video! you should make more
You explained it nicely.Make more video on dp
Thank you miss wright. Good tutorial. 😃
Thank you Sameer!
Thanks A lot....simple helpful..
Finally understood ❤❤❤
great solution
really we can think like that thanks a lot mam
can you make more leetcode answer tutorials?
Brilliant 👏 👏 👏
Kindly post more videos...there are lots of dynamic programming problems...at least there should be 20 such videos
Miss Wright is a genius!
不错,well done
Hey maam, n=4, k= 3 , it gives 66 if draw all 66 according to the algorithm, then it causes conflict that more than 2 adjacent post have same color, but I think real ans is 60
nice explanation
Very useful 👍
Thk you
Thanks a lot.
At 6:16 I didn't get why it would be (k-1) colors to paint 3rd post in different case. For me it looks like K. For example, we painted the first post in Blue, then for the second one we have 2 choices: red and yellow (K-1). But the third one can be any again: Red, Blue or Yellow. Which is K. How did we get K-1. Could someone explain please?
In the equation for case 2, the next post must be different, so it is k-1 to make it different than the previous. Case 1 covers when the next post is the same. So yes, there are K or 3 possibilities for the 3rd post, but because this is broken into two cases, case 1 covers 1 color, and case 2 covers the other 2 colors.
@@misswright7247 Thank you!
woww,mamm, super
Mam, please make more videos on such tricky DP Questions. why did you stop making videos ? :(
I plan to make more videos soon.
Thank you for your explanation. I have some doubts at 2:41 where you mentioned if the two post have same color. If you paint 1st post with yellow color and as there is a catch that two adjacent posts may be in same color then second one must have k choices. So the same color number of choices should be k*k and not k*1. May be I am wrong. Can you please explain it again?
If the second post has to be the same as the first, then you had k choices for the first, but after you pick the first you only have one choice for the second which is whatever color you picked for the first. The reason you don't have k choices for the second is because that would mean the second could be any of k colors, which may or may not be the same as the first.
@@misswright7247 Thank you Mam. So what would be the generalized formula for this problem?
I remember I struggled to grasp this question for a long time. I did end up solving it but in real interviews I'd probably struggle big time. What's the secret? Practice and Pratice?
and to boot, this question is marked Easy in Leetcode...
I think with practice you can get better, simply because you have seen more problems so you can begin to see connections. Practice will help, but it's not a 100% guarantee you will not struggle and unrealistic to expect to arrive at that point. Your interviews are supposed to measure how you think, not expect you to solve a difficult problem in less than an hour. Your interviewer is supposed to help you out if you struggle, which should also be a test in how you collaborate with colleagues.
Do you know the recursive solution to this problem? Can you explain how this is a candidate to dynamic programming? The formula seems pretty tricky
For the recursive solution you could have another function set up similar to this, except the for loop would be the recursive call to a function that would essentially do the same thing as the for loop. If you watch my other 3 part video on the Fibonacci number, I go over how to set up a recursive solution and how to transform it into a dynamic programming solution.
Also, typically anytime you are storing old values and using those previously calculated values to calculate the final answer, then you're problem is a candidate for dynamic programming. It may be more complex than that, but that's the main thing I see.
How the 3 post will have k-1 choices if we use different colours,
The 3rd post needs to be different than the 2nd, so any color except 1( The 2nd Color). K - 1, means all the colors except the second, or all the colors except the previous color. At first I thought it would be K-2 for the 3rd post, but the 1st and 3rd colors do not have to be different.
@@buttekaustubhpradeep5566, the 2nd and 3rd post can have the same color, as long as it's not the same as the 1st post. In other words, if post 2 and 3 are the same, your only option for the first post is that it be different than post 2 and 3, otherwise you would have 3 consecutive posts the same color, which is a violation of the constraint.
@@misswright7247 What i meant to say is when we are counting no of ways for 3 posts we are doing same=k*(k-1)*1 ...i understood this but when calculating diff =k*(k-1)*(k-1) we are saying that first two posts are different then why is the no of options for the third post (k-1) and not k..because if we are considering that the first two colors are different then the third post can be any of the k colors, right? example the first two posts are red-yellow then the third post can be either red or yellow or green because that will not violate the constraint of more than 2 consecutive posts with same color....I am missing something in the? Thanks a lot for the quick reply :)
@@buttekaustubhpradeep5566, we are already counting the scenario when the 3rd post is the same, in the equation for same(red-yellow-yellow). Therefore the equation for different must subtract one choice for the 3rd color(red-yellow-red or red-yellow-blue), but not (red-yellow-yellow) again.
@@misswright7247 oh okay now i understood clearly..Thanks a lot for the quick replies madam. Hoping to see more videos on your channel :)
Thanks Mam 😊😊
Ulalala. I Get it.. This problem is quite hard :D
Only part I am not clear is when we have 1st 2 different, why are we multiplying k-1? shouldn't we be multiplying k-2??
The third does not have to be different from the first. It needs to be different from the previous, so 1 is subtracted, and that 1 is for the previous.
Hi, Miss Wright: I think that you made a typo in listing the answer for 2 posts. it should k + k(k-1), not k + k*(k+1)
Wesley Z. W, you are correct. I'll try and fix it in the subtitles soon. Thank you!
@@misswright7247 Its at 5:38. Just write this in pinned msg. or Pin Wesley's comment. People will understand.
What will happen when k is less than number of post.
The value of k adds another layer of complexity. For example, if k is 1 and there are more than 2 posts, it would violate the constraint that no more than 2 consecutive posts can be the same color. Other than 1 or 0 for k, I can't think of how the value of k may effect the solution.
mam please make more videos
T(2) = K^2 , not k + k(k+1) ; should be k + k(k-1)
Almost slept ..
nice explanation