Monotonic Stack Data Structure Explained

LeetCode Pattern - Monotonic stack, Monotonic deque, Monotonic queue
Next Greater Element II
Daily Temperature
Sliding Window Maximum

#100secondsofcode #leetcode #leetcodesolution #python #coding #programming

Intro and intuition: (0:00)
Example walk through: (0:35)
Implementation: (4:26)

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

[PrajaktaKarandikar-tw]

Very well explained, would be easier to learn without the moving background.

[sibiranganath]

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 .

[PssGameplayER]

first time heard about Monotonic Stack, thanks for explaining it so properly

[biswajeetpadhi]

the background of this video is greatly designed. its very easy to focus with this background in motion

[Brxndz_]

This helped me solve Next Greater element without looking at your code, thanks!

[sparrow]

phenomenal bro, u got a talent for this

[yoDQ]

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.

[KuaisArts]

Wow! Thanks for walking through the example, it was very insightful

[sandeepamarnath]

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!

[alexsinx]

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?

[guinea_horn]

Really good explanation. I'll agree with everyone else and say that the background is extremely distracting, and it actually makes the bitrate of the whole video go down, making the quality poor whether I select 144p or 1080p. I also feel like you didn't explain the algorithm before going through the problem with the heights of people. You started going through the example, but I didn't know precisely what it was you were doing or why you were making the decisions that you were making. I think it would be nice to have a plain explanation of the problem and how the algorithm solves it before going through the problem step by step.

[rahbanghani]

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.

[csepratikshaargulewar]

I kindly request that you should make videos avoiding moving backgrounds, as they can be distracting while concentrating . By the way, great explanation!

[nagendrabommireddi]

wow very good explanation. thank you..

[codemonkey]

Why the solution iterative the array from right side to left side, is this order matter?

[dimahodan]

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.

[dhruvsakariya]

you made it very easy by making visualizing approach. Thanks

[Avighna]

Before learning this, I'd just use a segment tree for the first question xD.

[gmoney_swag]

Couldn’t you also go from left to right? You could store the indexes in the stack and as soon as you add an element greater than the element at the top of the stack, you keep removing the top until it’s equal or greater to the new element, while updating their values (sorry for the bad explanation)

[googleit]

New Topic Learned!!
Sep'11, 2023 06:36 pm