Min Stack - Leetcode 155 - Stacks (Python)

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@ceciljoel9577]

why we can just maintain record of a min value ? why min_stk?

[@ChristopherJones-ke8yg]

Perhaps because if you pop the min value then you will have to update min_value using something like min(self.stack), since youre not using min_stk?

[@ceciljoel9577]

@@ChristopherJones-ke8yg oh nice insight! Thanks

[@ThoXuanLe]

Thank you Greg Hogg!!

[@JoeTan-nq4fq]

For each node in the stack, store the current and min value thus far. In this way, we dun need the min_stack. def push(self, val: int) -> None: # Each node stores the val and min val thus far if not self.stack: self.stack.append((val, val)) else: minn = min(self.stack[-1][1], val) self.stack.append((val, minn))

[@ParkavanCK]

Thank you Greg Hogg!!!!!!

[@unanimed1]

I used a list of tuples for implementing the class, the first tuple item is to track the added elements and the second tuple item is to track the min values, is it a valid solution? public class MinStack { private List list; private int minNumber; public MinStack() { list = new List(); minNumber = int.MaxValue; } public void Push(int val) { list.Add(Tuple.Create(val, minNumber)); if(val < minNumber) { minNumber = val; } } public void Pop() { minNumber = list.ElementAt(list.Count - 1).Item2; list.RemoveAt(list.Count - 1); } public int Top() { return list.ElementAt(list.Count - 1).Item1; } public int GetMin() { return minNumber; } }

[@kdiffin]

Thanks for this

[@amjadalthabteh4680]

I thought that we appended the first val into the stk, hence [-1], i am confused on what value we are comparing it too, or are just returning the same val, just confused on the PUSH function lol, anyways thanks for all the help, youre truly amazing Greg!!!!!!

[@amjadalthabteh4680]

The min_stk sorry, i though we appened into the min stk

[@Infinitely16]

There are 3 conditions. First, if the min_stk is empty, then the current val is the minimum, so just append it. Second, if the current val we are looking at is greater than the current minimum value, then we just append the current minimum value, since the new one isn't smaller than it. Third, if the new val is less than the current min, then we append this new val as the new minimum.

[@JACK-of5vi]

hi Greg, thank you for sharing this video! I've got a question: as a beginner in DSA and leetcode, instead of learning all the DSA topics in one big chunk, can I learn one topic of DSA, and then go ahead to practice the corresponding questions for that topic? And repeat the same process for other topics?

[@JACK-of5vi]

for example, learn about topic like array, then practice array-related questions. then move on to another topic such as tree, and then repeat the process?

[@xingyuxiang1637]

@f5vi Code Signal may be better. But the hassles of grinding the problems will not be too much different. One has to type through the indexes to solve Sudoku. Let the hard questions and brain teasers be. There are hard questions, which imply a lot of easy and medium questions practices.

[@GregHogg]

You can certainly break it down into similar categories of problems, yes :)

[@mohamedmohsen-rc3jf]

mmmm i think there is a better solution , you can have an amoritized run O(1) beside space of O(1) as well , by having let's say a tuple that has the min val as the first element and the freq of occurance as a second element and when we push we just see if the new getted value is less than the min we have or not if it is we update our min tuple with the new one and freq = 1 , if it is equal we increase the freq and when we pop any element we just check if it is the min element we store or not . if it is decrease the freq , if not it is ok. if the freq = 0 just iterate again on the stack and get the new min then iterate again to find the freq of occurance . i think it is a valid and better solution

[@xingyuxiang1637]

To be more API-friendly: from collections import deque self.stack = deque() return min(self.stack) Hackerrank will need import. So, writing out the import statement is useful.

[@GregHogg]

But you don't need a queue, it's just a stack

[@moonlight-td8ed]

thats an o(n)