Implement A Max Stack - A Stack With A .max() API (Similar To "Min Stack" on LeetCode)

[@BackToBackSWE]

Table of Contents: A Quick Message 0:00 - 0:40 The Problem Introduction 0:40 - 0:53 What Is An API? 0:53 - 1:13 What Is An ADT? 1:13 - 2:03 The Stack ADT 2:03 - 2:42 Our Implementation Goal: A .max() Operation 2:42 - 3:25 The Problem We Face Using A Stack For This 3:25 - 6:41 The Epiphany: Cache Previous Max States 6:41 - 9:35 Improving Our Best Case Space Complexity To O(1) 9:35 - 14:06 How Did The Best Approach Help Us? Here Is How. 14:06 - 15:35 Please Subscribe To Me and Feed My Ego 15:35 - 16:16 The code for this question is in the description. Fully commented for learning purposes.

[@Leo-lb6uj]

very good! thank you!

[@BackToBackSWE]

sure

[@poojamadhavan9229]

Hi Ben, could you help understand the maximum frequency stack question on LC.?

[@BackToBackSWE]

@@poojamadhavan9229 Yeah, but not right now, we are busy building a new platform. Comes out in 3-4 weeks.

[@Official-tk3nc]

if you are watching this in lockdown believe me you are one of the rare species on the earth who is working hard to achieve something in life. Many students are wasting their time watching movies, playing pubg, watching netflix , etc, ALL THE BEST nitjstudenthere

[@BackToBackSWE]

lol - nice

[@Jaffy.]

Thx for the compliment lol

[@大盗江南]

Thanks for the compliment too lol

[@dmytroivanovv]

Totally agree.

[@BasharAlkhalili]

The state tracking trick blew my mind, and when I thought we were done, you came up with the optimized space trick. So much complexity for such a seemingly innocuous problem. But it's now all clear thanks to you, Ben.

[@BackToBackSWE]

I didn't come up with this myself, found it reading elements of programming interviews

[@juliesong2253]

I usually never comment but I’ve been watching your videos religiously for the past month. I watched this video when I woke up this morning and got the exact same question that night during my interview. Just thought it was super cool and wanted to say thanks!

[@BackToBackSWE]

great to hear

[@zewang625]

Great work! the most important thing is to recognize the problem. I like this idea.

[@BackToBackSWE]

thanks

[@James-le2hc]

it's so simple once you realize you can treat each element as a node. the part of using a separate stack to reduce the layers of caching is a little tricky tho. it's because we think in definitions instead of creatively.

[@BackToBackSWE]

Yeah haha, first jump to caching is straight-forward, but the final jump to an O(1) best case space is trickier.

[@zhenliu4779]

Trust me, this is the BEST explanation

[@sushmithasnataraj5122]

You guys deserve more subscribers. Keep up the good work :)

[@BackToBackSWE]

Thx and thx

[@Anveshana837]

One of the best educator, don't know why you stopped making videos😭

[@Nirvana4u-n4w]

So many times, candidates get mental block. Good you mention that and how this is overcome. By the way, you don't need to maintain 2 stacks. Just have one stack, and have additional max entry, when the pop is equal to max entry, do it twice and get the previously stored cache max.

[@BackToBackSWE]

Thanks. And I'm not sure what you mean. Are you referring to the O(1) best case space approach? Could you elaborate

[@Nirvana4u-n4w]

@@BackToBackSWE its similar to approach mentioned here - leetcode.com/explore/learn/card/queue-stack/230/usage-stack/1360/discuss/49031/Share-my-Java-solution-with-ONLY-ONE-stack

[@BackToBackSWE]

@@Nirvana4u-n4w Yeah, I've seen this. To me it's not so much that only one stack is used for that solution, but more importantly the solution is clever and always has O(1) additional space (since all min information is tracked on the items themselves) which makes it even more clever. I feel it is harder to understand though, but still just as valid of a solution. Thanks for sharing.

[@nikhil.pandey]

In love with your explanation.

[@BackToBackSWE]

no luv u

[@MiddleEasternInAmerica]

Benyam Ephrem, you changed my life, thanks man

[@MiddleEasternInAmerica]

hope you make a follow up video using Double Linked List + TreeMap ( solution #2 on leetcode )

[@tannerbarcelos6880]

Got asked this (but min stack) yesterday in an interview. Luckily, they accepted my O(N) solution to getting the min() and told me I passed the technical round however , after I left the call, I realized I could use a second stack, or store an object ok value and current max at every push and keep O(1) Great video!

[@walterwhite6499]

Use a tuple as (value, current_max_value) and store it in the stack. This way one can keep a track of max at every level of the stack. class MaxStack: def __init__(self): self.stack = [] self.cur_max = None def push(self, val): if not self.cur_max: self.cur_max = val else: self.cur_max = max(self.cur_max, val) self.stack.append((val, self.cur_max)) def pop(self): self.stack.pop() def max(self): return self.stack[len(self.stack)-1][1]

[@BackToBackSWE]

dope

[@MoaazAhmad]

@Walter White: This works but isn't optimized for space. At each push, you're storing the value and the max at that level. The second approach in the video (optimizing for best case) would require modifications to your code. Not really sure if interviewers would ask the best case optimization, but good to know nevertheless.

[@walterwhite6499]

Mohammad Ahmad I don't how understand how is it not optimized for space?

[@MoaazAhmad]

@@walterwhite6499 Suppose you need to push [5,5,5,5,5,5,5,5,5,5] (ten 5's). Using your way, your stack contains *twenty* numbers. The 2nd method in the video only stores *twelve* numbers (ten 5's of the list, one 5 to represent the max value, and a 10 to represent how many times 10 is in the stack). This is for the best case though (when you have the same number appearing consecutively). Your method is optimized for the worst case.

[@walterwhite6499]

Mohammad Ahmad at any given point of time the stack will have at most 2n elements which is same as O(n).

[@dark4o90]

you don't need to store key/value pairs in stack. You can just push the maximum number to the maxCache every time you push to the main stack. This way the space will be O(2n). Keeping the key/value pairs is more than that. And in java for example it's cumbersome to create key/value pairs because you don't have tuples. You have to use arrays of two elements or from java 11 and above Pair object. When pushing a new element to the main stack check the last max from the maxCache and if the number is greater than the max push it to the maxCache as well otherwise push the last max.

[@BackToBackSWE]

I cant read all of this im fast replying i love you

[@karthikmucheli7930]

Do you have a patreon page? I just don't want you to stop making these amazing videos. I wish I could contribute more than just my view count.

[@BackToBackSWE]

hahahaha, thank you, I am going to make a large video course/community with Chris Jereza soon

[@ritwik121]

awesomeee thought process.... Good job

[@mahmoudm451]

I only fail to see how we can create the max count annotation programmatically. Great video btw!

[@BackToBackSWE]

With a wrapper class. you wrap entities then augment them with more fields

[@SharatS]

For C++, for instance, you could create a stack of pair of integers, then use that for the max cache.

[@mo337]

This guy is my hero.👍

[@BackToBackSWE]

no u r

[@kzu8976]

at 1:00 I'm totallly lost lol . the API definition is so hard to understand But! great video ! I like it. keep going

[@BackToBackSWE]

An API is simply a behavior set we define that clients to our code can depend on. It is a programming term. It is not the point of the video, just know we need to implement the .max() function for a stack object we are making. I mentioned it to give the bigger picture setup before we answered the question, but yeah. It is a simple concept, you will ease into it so don't worry.

[@Franczinator]

An API is a way that someone can interact with your code. Pretend you wrote the "String" class. Examples of the "String" api would be something like the function that returns you the size of a string.

[@loyyeeko1231]

this is great! thank you!

[@rahulranjan7567]

The solution uses O(N) of space . If the entries are in millions with random entries then we would need a huge cache. Can we do this in constant space and time? Moreover, instead of the spare stack you used to keep the track of max/min element, can't we use the hash table with each push being compared to the max variable and then updating the hash? maxEle = -sys.maxsize hashMap = {} i = 1 def push(x): if i == 1: stack.append(x) maxEle = x hashmap.update({i:maxEle}) else: if x>maxEle: stack.append(x) maxEle = x hashmap.update({i:maxEle) else: stack.append(x) hashmap.update({i:maxEle) i = i+1 Here, i keeps the track of the push operations we are performing. Hash table gives constant access.

[@BackToBackSWE]

ok, I can't read all of this (I'm speed replying to comments). I hope you are right and that this helps someone

[@hritwiksom3032]

Why are you complicating it so much with a hash table? Just use an ArrayList/Array to keep track of the max element per push, the indices of the list keep track of the push operations; use a length var or i in your case to keep track of length of stack, increment/decrement it as per push/pop operations and get the location of the ArrayList element with its index being the current length of the stack. It has also O(1) access.

[@grizzlycougar]

Came to check my solution and it was about the same except instead of caching the number of occurrences I cached the index at which that max number was at. So when popping elements off the stack you check the length of the stack and the top cached index, if those are the same you also pop off the cached stack. Basically the same run time and space complexity but different ways of thinking about it, IDK if this is that unique or not (probably not) but just an alternative.

[@guptapaaras]

Best ever explanation Bro.

[@BackToBackSWE]

sure

[@אוריישראל-ד3נ]

hi it was very helpful thank you very much. also, can you explain how can i prove that all the implementations of delete max will be in omega of log(n)?

[@lipishah474]

Excellent Video. I have question, in the second stack how can we store occurrence of max value? Thanks in advance.

[@BackToBackSWE]

In an augmented structure like an extra object u make and append the field to cache the value

[@Raj_Patel21]

The second approach was nice.

[@BackToBackSWE]

ye

[@大盗江南]

U r amazing buddy, we love you.

[@arindrajitseal4577]

awesome explanation

[@BackToBackSWE]

thanks

[@algorithmimplementer415]

Great video!!

[@BackToBackSWE]

thanks

[@ArielVolovik]

How would we get the .max though? Say for the last example we want to get the `.max()` value which is 5. Isn't the only way to access it is by using `.pop()`? But then our max cache would be empty, and yet 5 would still be *in* the stack.

[@sdevaney89]

Stacks can have a .peek() method that will return the value on the top of the stack without removing it. So if you are you using his second example you would use a return the .peek() value of the max cache.

[@mfkman]

Instead of occurrences in the max stack, I would store the pointers of the elements leading to a new max. When I pop, I check, is the top of the stack pointing to the element I am popping? If yes, pop, else: don't.

[@BackToBackSWE]

Interesting, this brings on the cost of pointer dereferencing

[@mfkman]

@@BackToBackSWE actually during a pop I wouldn't be dereferencing anything - just checking if the addresses match. Only during a push (in order to valide if I have a new max) I would have to dereference the pointer at the top which would point to a location inside the actual element stack. Yes, this may impose the penalty of a cache miss if the last element was pushed quite some time ago.

[@XChen-zj1ek]

This solution is brilliant, however, I don't think this can provide popMax() API which LeeCode also requires.

[@BackToBackSWE]

ok

[@spendingmarrow6914]

I believe we can actually do this in O(n) time. We use peak to get the max entry. Then we create a temporary stack and begin to pop and add items from the original stack to this temporary stack. Once we find the largest item we remove but do not add into the temporary stack. Finally, add the items back into the original stack and then return max item.

[@joydeeprony89]

maxPop() could you implement.

[@emilyhuang2759]

Why can't I understand what is the goal of the problem??? The max is found but then the max is going back down again? Why is that not being returned? EDIT: I see now. This video is for getting the whole picture of whats happening. But why is having two stacks optimum? Instead of just using one variable to hold the state?

[@BackToBackSWE]

Nice and I don't remmeber the approaches - been a while since I recorded this. Are you confused about the complexities?

[@ankitgoyal8556]

Brother, there is a solution to find min() in O(1) time and O(1) space, do actually interviewer expect that from us? Or we can O(1) time and O(n) space like your solution. Thank you

[@BackToBackSWE]

im not sure

[@ankitgoyal8556]

@@BackToBackSWE Thank you for replying brother, love from India 🔥

[@ShaliniNegi24]

Thank you and god bless you :)

[@BackToBackSWE]

Thanks

[@guowanqi9004]

Thank you so much sir.

[@BackToBackSWE]

sure

[@minhhnh_in_jp]

Thanks you so muchhhhhh ♥

[@BackToBackSWE]

sure

[@srihariathiyarath9722]

Is there any way we can sort the stack initially so that we can just pop off the maximum ?!

[@pointerish]

You could, but sorting it's another whole thing to study. Depending on how big the array/stack is, if they are partially sorted already, if they are integers or objects. You could use merge sort, quicksort, radio sort depending on what you're sorting.

[@BackToBackSWE]

@@pointerish yes

[@BackToBackSWE]

Sorting would violate the insertion order unless copies of items were made with references back to the original items. This may be a solution that works with more space (but not asymptotically more, still linear).

[@Eyenn_n]

AWESOME!!!!!!

[@BackToBackSWE]

thanks

[@RuslanSkiraUkraine]

In don't understand with 2 stack How we will increment the maximum?

[@ianzhang7048]

NICE!

[@BackToBackSWE]

hi

[@db-wk8xb]

how can it be done using just one stack

[@BackToBackSWE]

7:08

[@chrisy.703]

how about poping max value? ur solution not includes this case AT ALL

[@hritwiksom3032]

This is not a constant space solution as the number of elements added to max stack is not fixed. P. S. This still is the optimal solution as there can't be O(1) space solution unless number of pop operations are known, which is kinda idiotic if it's provided lol 😉

[@BackToBackSWE]

rapid replying to comments I cant I love u tho

[@raremajor]

How do you land up with an Intern in twitter?(If that's where you got your tshirt from)

[@BackToBackSWE]

what lol

[@raremajor]

How to get an intern/FTE at Twitter?

[@BackToBackSWE]

@@raremajor I can't teach that. No one can teach that. Just because someone worked somewhere doesn't mean that they know anything about teaching someone how to work there. It really just happens by luck & part skill (mostly luck & good fortune). Ex: Google employees can't teach one how to get a job at Google. They know how their interviews were, but are not certified in projecting what your specific team will ask, gauging your abilities, etc.

[@Naveen-luffy56]

I cant find the code

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@PankajKP]

i guess you have too many t-shirts hahaha

[@BackToBackSWE]

yeah haha