adding modulo logic to line 13 will significantly improve the runtime and can avoid time limit exceed error, seems handling big number consumes a lot of time
The reason this works is that that all sticks have unique sizes which makes all the subarrays (without an exception) having only 1 max. So, even when we remove 1 max elem from the list; the remaining subarray has exactly the same properties with the initial array (1 max with all subarrays having 1 max again etc.) Having only 1 max always means that there is always 1 element that can be put at the end -> (n-1, k-1) where as for all non-max elements -> (n-1, k) for the rest of the array Having only 1 max for all subarrays also mean that the problem is the same for all subarrays. HOWEVER, if the problem stated that the sizes could be the same. Then, the subarrays wouldn't be unique.
You can change base case condition to k>n (there is no way to make k stocks visible if you don't have enough sticks)- half of dp table will be skipped. Besides, when using hashmap it is really slow -(at least in java), better solution would be to use plain array.With that changes recursive solution passes time limit without problem.
That said, very nice explanation. Had something similar in mind but could not implement it. Just wondering what if we had duplicate values in the array?
Another way of wording the dp solution is... (n-1)* dp[n-1][k] represents putting any number but the largest on the right, and dp[n-1][k-1] represents putting the largest number on the right
O(n * k), the dp complexity formula is: how-many-state-you-have * how-much-time-you-spent-on-each-state This problem’s dp has n * k state, you only spent a constant O(1) time on each state, so obviously it’s O(n * k)
Yeah its not the same. Let the heights be 1, 2, 3 if you place 2 at the end then that stick will not be visible, since there will be a stick of height 3 infront of 2. So we can put any of the (n-1) sticks to the right of the tallest stick (ex. we can put either 1 or 2 to the right of 3), then the problem reduces to finding Number of Ways to Rearrange (n-1) Sticks With K Sticks Visible.
So basically you didn’t explain how you came up with thinking about ranging number on last position instead of on first position. Is it an inspiration from your previous leetcode experience, or is it just pure inspiration? Is there any rational for you to range number on last position? What made you think ranging on last position could solve the problem and then give it a try? I think this thinking process is actually the key point I am interested to learn
Yeah, I know what you mean. I actually only came up with the O(n*n*k) by myself, but I quickly understood the O(n*k) when i read it. Yes, this "reverse thinking" pattern is seen in other DP problems. A recent problem i solved, Bursting Baloons, followed the exact same pattern. So I do think experience and practice can help you recognize it. But sometimes when you run out of all options you just have to try and see if reversing the problem simplifies it.
@@NeetCode may be the people actually come up with this solution in the contest know the trivial implications and the secret sauce, I don’t think they are just lucky to try reverse and found it works, they must notice some deeper level of this problem imply that reverse might work
@@NeetCode One rational I think might be why trying reverse is when you try to apply the same dp induction logic to first position, you actually require information/states from previous “path”/ previous step about how you put the number to decide this position will be seen from left or not, so in this case, you might want to solve it from back to front, with a recursive induction
@@Will-su2fg It depends on question for eg in this qs its easy to think that the tallest stick or the stick at the end will definitely be visible so its easy to fix it first and recurse on remaining
MOD = (10**9) + 7 @cache def dp(n , k): if n == 0 or k == 0: return 0 if n == k: return 1 return (dp(n-1, k-1) + ((n-1) * dp(n-1, k))) % MOD return dp(n, k) % MOD ^ this worked 75% faster
💡 DP Playlist: ruclips.net/video/73r3KWiEvyk/видео.html
adding modulo logic to line 13 will significantly improve the runtime and can avoid time limit exceed error, seems handling big number consumes a lot of time
Yes big numbers are not handled in constant time
Thanks for mentioning this!
The reason this works is that that all sticks have unique sizes which makes all the subarrays (without an exception) having only 1 max.
So, even when we remove 1 max elem from the list; the remaining subarray has exactly the same properties with the initial array (1 max with all subarrays having 1 max again etc.)
Having only 1 max always means that there is always 1 element that can be put at the end -> (n-1, k-1)
where as for all non-max elements -> (n-1, k) for the rest of the array
Having only 1 max for all subarrays also mean that the problem is the same for all subarrays.
HOWEVER, if the problem stated that the sizes could be the same. Then, the subarrays wouldn't be unique.
Underrated comment
you are a saviour dear!
please keep uploading more such dp and graph problems.
Thanks
good explanation!
You can change base case condition to k>n (there is no way to make k stocks visible if you don't have enough sticks)- half of dp table will be skipped. Besides, when using hashmap it is really slow -(at least in java), better solution would be to use plain array.With that changes recursive solution passes time limit without problem.
however the constraint do say 1
You always explain in the most thorough way, thank you!
Checking if n==0 is redundant because it will be equal to k before it could ever go to 0
That said, very nice explanation. Had something similar in mind but could not implement it. Just wondering what if we had duplicate values in the array?
could you please tell me how did you find the time complexity of the brute force solution........plz....
Another way of wording the dp solution is... (n-1)* dp[n-1][k] represents putting any number but the largest on the right, and dp[n-1][k-1] represents putting the largest number on the right
Awesome Explanation! Thanks
I think the naive approach from left to right is of time complexity n^3*k , not n^2*k
Wow! amazing explanation!
Nice explanation!
Great video pal!!
watched it 3 times, now i get the intuition behind this.
Thank you for the video. It is very helpful!
Best explanation!!
Could you elaborate on the time complexity conclusion on both approaches?
O(n * k), the dp complexity formula is:
how-many-state-you-have * how-much-time-you-spent-on-each-state
This problem’s dp has n * k state, you only spent a constant O(1) time on each state, so obviously it’s O(n * k)
there is an interesting closed form solution using permutations
Yeah I was actually going down that road and got a solution in O(n) time; however it took me nearly 2 hours and reviewing some combinatorics
Why are we multiplying by n-1?
Like (1,2) is not same as the arrangement of (2,1) right? can anyone explain the thought process behind this?
Yeah its not the same.
Let the heights be 1, 2, 3 if you place 2 at the end then that stick will not be visible, since there will be a stick of height 3 infront of 2. So we can put any of the (n-1) sticks to the right of the tallest stick (ex. we can put either 1 or 2 to the right of 3), then the problem reduces to finding Number of Ways to Rearrange (n-1) Sticks With K Sticks Visible.
Awesome video thanks alot!
Your every video is worth to watch. Thanks for video
Can you please cover this question 862- Shortest Subarray with Sum at least k
Sure, I will add that to my list and solve it soon!
@@NeetCode Thanks
How many questions can you usually solve during the contests
TLE even with the DP method
So basically you didn’t explain how you came up with thinking about ranging number on last position instead of on first position. Is it an inspiration from your previous leetcode experience, or is it just pure inspiration? Is there any rational for you to range number on last position? What made you think ranging on last position could solve the problem and then give it a try? I think this thinking process is actually the key point I am interested to learn
Yeah, I know what you mean. I actually only came up with the O(n*n*k) by myself, but I quickly understood the O(n*k) when i read it.
Yes, this "reverse thinking" pattern is seen in other DP problems. A recent problem i solved, Bursting Baloons, followed the exact same pattern. So I do think experience and practice can help you recognize it. But sometimes when you run out of all options you just have to try and see if reversing the problem simplifies it.
@@NeetCode may be the people actually come up with this solution in the contest know the trivial implications and the secret sauce, I don’t think they are just lucky to try reverse and found it works, they must notice some deeper level of this problem imply that reverse might work
@@NeetCode One rational I think might be why trying reverse is when you try to apply the same dp induction logic to first position, you actually require information/states from previous “path”/ previous step about how you put the number to decide this position will be seen from left or not, so in this case, you might want to solve it from back to front, with a recursive induction
@@Will-su2fg It depends on question for eg in this qs its easy to think that the tallest stick or the stick at the end will definitely be visible so its easy to fix it first and recurse on remaining
Amazing
MOD = (10**9) + 7
@cache
def dp(n , k):
if n == 0 or k == 0:
return 0
if n == k:
return 1
return (dp(n-1, k-1) + ((n-1) * dp(n-1, k))) % MOD
return dp(n, k) % MOD
^ this worked 75% faster
It is clear and easy to understand, thx a lot
What kind of sadist asks this question in an interview???
True
Google