0
0
DSA Pythonprogramming~20 mins

Min Stack Design in DSA Python - Practice Problems & Challenges

Choose your learning style9 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Challenge - 5 Problems
🎖️
Min Stack Mastery
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate
2:00remaining
Output of Min Stack after push and pop operations

Consider a Min Stack that supports push, pop, and getMin operations. What is the output of the getMin calls after the following operations?

push(5)
push(3)
push(7)
pop()
getMin()
pop()
getMin()
DSA Python
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self):
        if self.stack:
            val = self.stack.pop()
            if val == self.min_stack[-1]:
                self.min_stack.pop()

    def getMin(self):
        return self.min_stack[-1] if self.min_stack else None

ms = MinStack()
ms.push(5)
ms.push(3)
ms.push(7)
ms.pop()
print(ms.getMin())
ms.pop()
print(ms.getMin())
A[5, 3]
B[3, 7]
C[7, 3]
D[3, 5]
Attempts:
2 left
💡 Hint

Remember the min stack keeps track of the smallest values so far.

🧠 Conceptual
intermediate
1:00remaining
Understanding Min Stack space complexity

What is the worst-case extra space complexity of a Min Stack that stores minimum values alongside the main stack?

AO(n), where n is the number of elements pushed
BO(1), constant extra space
CO(log n), logarithmic extra space
DO(n^2), quadratic extra space
Attempts:
2 left
💡 Hint

Consider the case when each new element is smaller than all previous ones.

🔧 Debug
advanced
1:30remaining
Identify the error in Min Stack pop method

What error will the following Min Stack pop method cause when popping from an empty stack?

def pop(self):
    val = self.stack.pop()
    if val == self.min_stack[-1]:
        self.min_stack.pop()
ANo error, works fine
BIndexError due to popping from empty list
CKeyError due to missing key
DTypeError due to wrong data type
Attempts:
2 left
💡 Hint

What happens if self.stack is empty and pop() is called?

❓ Predict Output
advanced
2:00remaining
Output of getMin after multiple push and pop

What is the output of the getMin calls after these operations?

push(2)
push(0)
push(3)
push(0)
getMin()
pop()
getMin()
pop()
getMin()
DSA Python
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self):
        if self.stack:
            val = self.stack.pop()
            if val == self.min_stack[-1]:
                self.min_stack.pop()

    def getMin(self):
        return self.min_stack[-1] if self.min_stack else None

ms = MinStack()
ms.push(2)
ms.push(0)
ms.push(3)
ms.push(0)
print(ms.getMin())
ms.pop()
print(ms.getMin())
ms.pop()
print(ms.getMin())
A[0, 0, 2]
B[0, 3, 2]
C[0, 0, 0]
D[2, 0, 0]
Attempts:
2 left
💡 Hint

Track the min stack carefully after each pop.

🚀 Application
expert
3:00remaining
Design a Min Stack with O(1) space for min tracking

You want to design a Min Stack that uses only one stack and stores the minimum value without extra space for a min stack. Which approach below correctly achieves this?

AStore differences between current value and min; update min when pushing and popping accordingly
BStore all values normally and scan stack to find min on each getMin call
CUse two stacks: one for values and one for min values
DStore values in a queue and track min separately
Attempts:
2 left
💡 Hint

Think about encoding min info within the stack values themselves.