Why is the time complexity O(n) if we have two nested loops? shouldn't it be o(n*m) where n is the number of elements in the array and m is the number of elements in the stack?
It's a god level explanation of monotonic stack. A request from your rest subscriber: Don't have that running background in the tutorial it's irritating .
Great video thanks. Trying to understand how the monotonic stack approach would be of O(n) time. We traverse the array only once for sure, but what about the pop operations? For a few elements of array, we are popping out of stack multiple times until we find a stack element that is greater than the current element, so are we not counting this towards the time complexity? If length of stack is k, wouldn't the overall time be O(nk)? Thanks again!
Every element in the array is processed exactly once. When an element is popped from the stack, it does not re-enter. Consequently, the maximum number of operations is 2n, accounting for each element being pushed and popped once.
Thank you for the monotonic stack explainer. It may be helpful to also show an image of the heights array above the image of the answer array to help visualize the relationship between the two better while popping and inserting.
why brute force is O(n^2)? Each element doesn't start from the beginning of the array. Isn't it O(n*m) where m is i - k - 1? where k is the current element.
Very well explained, would be easier to learn without the moving background.
I loved the moving background. It helped me stay focused
Everything was fine before i read your comment. Now i cant ignore it .
@@bluesteel1 😆
@@bluesteel1 😂
@@JackHou-vw7hs my man
first time heard about Monotonic Stack, thanks for explaining it so properly
Our pleasure!
Wow! Thanks for walking through the example, it was very insightful
Why is the time complexity O(n) if we have two nested loops? shouldn't it be o(n*m) where n is the number of elements in the array and m is the number of elements in the stack?
The code can be indeed deceiving. But remember each element enters or exits at most once. This is why monotonic stack is a efficient data structure.
Literally the worst sample, because not much of exploration... Maybe thats why for you its most confusing... As so its this video...
It's a god level explanation of monotonic stack.
A request from your rest subscriber: Don't have that running background in the tutorial it's irritating .
The moving background is very distracting. I can't even watch the full video
Great video thanks. Trying to understand how the monotonic stack approach would be of O(n) time. We traverse the array only once for sure, but what about the pop operations? For a few elements of array, we are popping out of stack multiple times until we find a stack element that is greater than the current element, so are we not counting this towards the time complexity? If length of stack is k, wouldn't the overall time be O(nk)? Thanks again!
Every element in the array is processed exactly once. When an element is popped from the stack, it does not re-enter. Consequently, the maximum number of operations is 2n, accounting for each element being pushed and popped once.
The background is too distracting
bro remove that background!
great explanation but the moving background really makes me dizzy, could not watch it for more than 1 minute
Great!
The moving background make it hard to follow.
Thank you for the monotonic stack explainer. It may be helpful to also show an image of the heights array above the image of the answer array to help visualize the relationship between the two better while popping and inserting.
the background of this video is greatly designed. its very easy to focus with this background in motion
can't tell if it's positive or sarcasm haha but yeah glad you like it!
@@algo.monster the background in motion acts as a boundary to the actual content, so I think it really works.
I am a complete opposite to this idea, I feel like this 🤮 when I see it. It is not optimal for every 🧠
thanks
Before learning this, I'd just use a segment tree for the first question xD.
would you be kind enough to share what is the application that you are using for the walk through of the solution :) Thank you in advance.
Thank you so much
You're most welcome
New Topic Learned!!
Sep'11, 2023 06:36 pm
Thanks for the video! Feedback on the moving background : VERY DISTURBING
Thanks and Noted!
wow very good explanation. thank you..
Why the solution iterative the array from right side to left side, is this order matter?
The order is a choice, you could have used a strictly increasing function instead
Awesome explaination
bro is god
Nice
Very nice explanation, great job.
Thank you!
Perfect explanation, thank you !
Glad it was helpful!
why brute force is O(n^2)? Each element doesn't start from the beginning of the array.
Isn't it O(n*m) where m is i - k - 1? where k is the current element.
k is not an input parameter. we have to express it in n. after dropping the content it's n^2
its n-1 + n-2 +n-3 ... = n**2
@@douglas5260 its not multiplication it should be addition
@@BurtPredrag Yeah, I've corrected it. Thanks!
very bad background
yup!
It's really helpful to stay focused actually
Awesome video! Easy to understand
Wonderful Explanation and PPT's
Glad you liked it!
So helpful 😭🖤
Glad it helped!
You are Osm bro..
Thanks ✌️
Great video, thank you a lot!
Glad it helped!
you made it very easy by making visualizing approach. Thanks
Glad it was helpful!