Min Stack - Leetcode 155 - Stacks (Python)

Please check my playlists for free DSA problem solutions:

My Favorite Courses:

Data Structures & Algorithms:

Python:

Web Dev / Full Stack:

Cloud Development:

Game Development:

SQL & Data Science:

Machine Learning & AI:

[GregHogg]

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

[JoeTan-nqfq]

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))

[xingyuxiang]

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.

[Am_Elijah]

Im so confused. Can you show when the stack is something like [4, 5, -1, 10]. Theres a logic im trying to unfold but its failing simply because of how the stack is arranged as [5, 4, -1, 10]. Ending at 10 limits my understanding of how to handle larger values ahead pf minimum vslues in the minstsck suppose the stack had to store more max values than the corrent min value. Please help me out.

[unanimed]

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<Tuple<int, int>> list;
private int minNumber;

public MinStack() {
list = new List<Tuple<int, int>>();
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;
}
}

[mohamedmohsen-rcjf]

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

[ceciljoel]

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

[amjadalthabteh]

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

[JACK-ofvi]

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?

[nikhilsoni]

I think this question comes under difficulty level = easy 🥲🥲