Monotonic Stack Data Structure Explained

LeetCode Pattern - Monotonic stack, Monotonic deque, Monotonic queue
Next Greater Element II
Daily Temperature
Sliding Window Maximum
☑️Full solution: algo.monster/problems/valid_p...
🟪 Check out AlgoMonster: algo.monster
🥷 Discord: / discord
#100secondsofcode #leetcode #leetcodesolution #python #coding #programming
Intro and intuition: (0:00)
Example walk through: (0:35)
Implementation: (4:26)
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

[@user-cb1si7ig6p]

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

[@JackHou-vw7hs]

I loved the moving background. It helped me stay focused

[@bluesteel1]

Everything was fine before i read your comment. Now i cant ignore it .

[@jigar2238]

@@bluesteel1 😆

[@siddhantprakash.]

@@bluesteel1 😂

[@KuaisArts]

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

[@PssGameplayER]

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

[@algo.monster]

Our pleasure!

[@sharwariphadnis1298]

Awesome video! Easy to understand

[@biswajeetpadhi100]

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

[@algo.monster]

can't tell if it's positive or sarcasm haha but yeah glad you like it!

[@biswajeetpadhi100]

@@algo.monster the background in motion acts as a boundary to the actual content, so I think it really works.

[@szymonpiechutowski2340]

I am a complete opposite to this idea, I feel like this 🤮 when I see it. It is not optimal for every 🧠

[@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.

[@aleksandr_t]

Great video, thank you a lot!

[@algo.monster]

Glad it helped!

[@nagendrabommireddi8437]

wow very good explanation. thank you..

[@LunaOoze]

Perfect explanation, thank you !

[@algo.monster]

Glad it was helpful!

[@hardiksinghal1360]

Awesome explaination

[@helloguys9201]

Wonderful Explanation and PPT's

[@algo.monster]

Glad you liked it!

[@ignassablinskas9175]

Very nice explanation, great job.

[@algo.monster]

Thank you!

[@literallyjustsomegirl]

So helpful 😭🖤

[@algo.monster]

Glad it helped!

[@sandeepamarnath3295]

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!

[@algo.monster]

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.

[@rahbanghani4097]

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.

[@bluesteel1]

Nice

[@AINikunjGour]

You are Osm bro..

[@algo.monster]

Thanks ✌️

[@dhruvsakariya3129]

you made it very easy by making visualizing approach. Thanks

[@algo.monster]

Glad it was helpful!

[@Avighna]

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

[@PhuocOngGia]

bro is god

[@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?

[@algo.monster]

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.

[@user-pu1mf8px5e]

The background is too distracting

[@codemonkey007]

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

[@TragicGFuel]

The order is a choice, you could have used a strictly increasing function instead

[@parulgarg5362]

Thanks for the video! Feedback on the moving background : VERY DISTURBING

[@algo.monster]

Thanks and Noted!

[@dimahodan232]

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.

[@algo.monster]

k is not an input parameter. we have to express it in n. after dropping the content it's n^2

[@douglas5260]

its n-1 + n-2 +n-3 ... = n**2

[@BurtPredrag]

@@douglas5260 its not multiplication it should be addition

[@douglas5260]

@@BurtPredrag Yeah, I've corrected it. Thanks!

[@RahulBansal14]

The moving background make it hard to follow.

[@googleit2490]

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

[@kaszatus2]

Literally the worst sample, because not much of exploration... Maybe thats why for you its most confusing... As so its this video...

[@bogdan206]

bro remove that background!

[@tiger7858]

very bad background

[@szymonpiechutowski2340]

yup!

[@Trashcan-sz2qu]

It's really helpful to stay focused actually