Minimum Stack (Min in O(1))

▶

Steps

setup

Initialize MinStack

Create an empty stack and set minVal to None, preparing the data structure for operations.

💡 Initialization is crucial to start with a clean state where no values or minimums exist yet.

Line:

def __init__(self):
    self.stack = []
    self.minVal = None

💡 The stack is empty and minVal is undefined, ready to accept the first push.

insert

Push -2 (First Element)

Since the stack is empty, push 0 and set minVal to -2. The stack now encodes the first element as a zero difference.

💡 Pushing the first element sets the baseline minimum and stores zero difference to represent it.

Line:

if not self.stack:
    self.stack.append(0)
    self.minVal = x

💡 The first push always pushes 0 and sets minVal to the pushed value.

insert

Push 0 (Second Element)

Calculate difference 0 - (-2) = 2, push 2 onto stack. Since difference is positive, minVal remains -2.

💡 Positive difference means new value is not smaller than current minVal, so minVal stays the same.

Line:

diff = x - self.minVal
self.stack.append(diff)
if diff < 0:
    self.minVal = x

💡 Positive differences indicate values above the current minimum.

insert

Push -3 (Third Element)

Calculate difference -3 - (-2) = -1, push -1. Since difference is negative, update minVal to -3.

💡 Negative difference signals a new minimum, so minVal must be updated to the new smaller value.

Line:

diff = x - self.minVal
self.stack.append(diff)
if diff < 0:
    self.minVal = x

💡 Negative differences encode new minimum values and trigger minVal updates.

compare

getMin() Query

Return minVal which is currently -3, the minimum value in the stack.

💡 getMin() simply returns minVal in O(1) time without modifying the stack.

Line:

def getMin(self) -> int:
    return self.minVal

💡 minVal always holds the current minimum value for quick retrieval.

delete

Pop Top Element (-3)

Pop top difference -1. Since popped value < 0, update minVal = minVal - popped = -3 - (-1) = -2.

💡 Popping a negative difference means the minimum is reverting to a previous value.

Line:

diff = self.stack.pop()
if diff < 0:
    self.minVal = self.minVal - diff

💡 Negative popped values indicate minVal rollback to previous minimum.

compare

top() Query

Look at top difference 2. Since 2 > 0, top value = minVal + 2 = -2 + 2 = 0.

💡 top() reconstructs the actual top value using minVal and the stored difference.

Line:

diff = self.stack[-1]
if diff > 0:
    return self.minVal + diff
else:
    return self.minVal

💡 Positive top difference means top is above minVal by that difference.

compare

getMin() Query Again

Return minVal which is now -2 after the pop operation.

💡 getMin() reflects the updated minimum after popping the previous minimum element.

Line:

def getMin(self) -> int:
    return self.minVal

💡 minVal always tracks the current minimum correctly after all operations.

insert

Push 1 (Fourth Element)

Calculate difference 1 - (-2) = 3, push 3 onto stack. Since difference is positive, minVal remains -2.

💡 Pushing a value greater than minVal results in a positive difference pushed onto the stack.

Line:

diff = x - self.minVal
self.stack.append(diff)
if diff < 0:
    self.minVal = x

💡 Positive differences indicate values above the current minimum.

delete

Pop Top Element (1)

Pop top difference 3. Since popped value > 0, minVal remains unchanged at -2.

💡 Popping a positive difference does not affect minVal.

Line:

diff = self.stack.pop()
if diff < 0:
    self.minVal = self.minVal - diff

💡 Only negative popped values cause minVal rollback; positive popped values do not.

class MinStack:
    def __init__(self):  # STEP 1
        self.stack = []
        self.minVal = None

    def push(self, x: int) -> None:  # STEP 2-4,9
        if not self.stack:
            self.stack.append(0)  # push 0 for first element
            self.minVal = x
        else:
            diff = x - self.minVal
            self.stack.append(diff)
            if diff < 0:
                self.minVal = x

    def pop(self) -> None:  # STEP 6,10
        diff = self.stack.pop()
        if diff < 0:
            self.minVal = self.minVal - diff

    def top(self) -> int:  # STEP 7
        diff = self.stack[-1]
        if diff > 0:
            return self.minVal + diff
        else:
            return self.minVal

    def getMin(self) -> int:  # STEP 5,8
        return self.minVal

if __name__ == '__main__':
    minStack = MinStack()  # STEP 1
    minStack.push(-2)  # STEP 2
    minStack.push(0)   # STEP 3
    minStack.push(-3)  # STEP 4
    print(minStack.getMin())  # STEP 5: -3
    minStack.pop()           # STEP 6
    print(minStack.top())    # STEP 7: 0
    print(minStack.getMin()) # STEP 8: -2
    minStack.push(1)          # STEP 9
    minStack.pop()            # STEP 10

📊

Minimum Stack (Min in O(1)) - Watch the Algorithm Execute, Step by Step

Watching each push, pop, and query operation reveals how the algorithm encodes minimum values efficiently, which is hard to grasp from code alone.

no_op

Stack (top→bottom)

empty

pushElement[0]: -2

Stack (top→bottom)

0

↑ pushed: 0

pushElement[1]: 0

Stack (top→bottom)

2

0

↑ pushed: 2

pushElement[2]: -3

Stack (top→bottom)

-1

2

0

↑ pushed: -1

no_op

Stack (top→bottom)

-1

2

0

Contributes: -3

pop

Stack (top→bottom)

2

0

↓ popped: [-1]

peek

Stack (top→bottom)

2

0

Contributes: 0

no_op

Stack (top→bottom)

2

0

Contributes: -2

pushElement[3]: 1

Stack (top→bottom)

3

2

0

↑ pushed: 3

pop

Stack (top→bottom)

2

0

↓ popped: [3]

Key Takeaways

✓ The stack stores differences relative to the current minimum, not raw values.

This encoding is subtle and not obvious from code alone; watching the differences pushed clarifies this.

✓ Negative differences indicate a new minimum and trigger minVal updates.

Seeing when and why minVal changes helps understand how the algorithm maintains O(1) min retrieval.

✓ Popping a negative difference rolls back minVal to the previous minimum.

This rollback mechanism is key to correctness and is easier to grasp visually than by reading code.

Practice

1. Consider the following Python code that evaluates Reverse Polish Notation expressions. What is the final output when the input tokens are ["4", "13", "5", "/", "+"]?

class Solution:
    def evalRPN(self, tokens):
        import operator
        ops = {
            '+': operator.add,
            '-': operator.sub,
            '*': operator.mul,
            '/': lambda x, y: int(x / y),
        }
        stack = []
        for token in tokens:
            if token in ops:
                right = stack.pop()
                left = stack.pop()
                stack.append(ops[token](left, right))
            else:
                stack.append(int(token))
        return stack.pop()

sol = Solution()
print(sol.evalRPN(["4", "13", "5", "/", "+"]))

easy

A. 2

B. 6

C. 8

D. 10

Solution

1. Step 1: Trace stack operations

   Push 4, push 13, push 5; then '/' operator pops 5 and 13, computes int(13/5) = 2, push 2; then '+' operator pops 2 and 4, computes 4+2=6, push 6.

2. Step 2: Final stack pop

   Pop the last element 6 as the result.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Stack correctly reflects intermediate results [OK]

Hint: Remember integer division truncates toward zero [OK]

Common Mistakes:

• Swapping left and right operands
• Using float division instead of int
• Off-by-one in stack pops

2. Given the following code for finding the first unique character in a stream, what is the output after processing the input stream ['a', 'b', 'a']?

from collections import deque

def first_unique_stream(stream):
    freq = [0] * 26
    q = deque()
    result = []
    for ch in stream:
        idx = ord(ch) - ord('a')
        freq[idx] += 1
        if freq[idx] == 1:
            q.append(ch)
        while q and freq[ord(q[0]) - ord('a')] > 1:
            q.popleft()
        result.append(q[0] if q else '#')
    return result

print(first_unique_stream(['a', 'b', 'a']))

easy

A. ['a', 'b', '#']

B. ['a', 'a', '#']

C. ['a', 'a', 'b']

D. ['a', 'b', 'b']

Solution

1. Step 1: Trace first iteration with 'a'

   freq['a'] = 1, queue = ['a'], first unique = 'a'

2. Step 2: Trace second iteration with 'b'

   freq['b'] = 1, queue = ['a', 'b'], first unique still 'a' since freq['a'] = 1

3. Step 3: Trace third iteration with 'a'

   freq['a'] = 2, queue front 'a' freq > 1, pop 'a', queue now ['b'], first unique = 'b'

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Queue updates correctly remove duplicates [OK]

Hint: Queue front always holds current first unique or empty [OK]

Common Mistakes:

• Not popping duplicates from queue front
• Appending duplicates to queue multiple times
• Returning wrong character after duplicates

3. You need to implement a data structure that supports enqueue and dequeue operations using only stack operations (push and pop). Which approach guarantees an amortized O(1) time complexity per operation?

easy

A. Use two stacks: push elements onto one stack, and pop elements from the other stack, transferring elements only when the pop stack is empty.

B. Use a single stack and recursion to simulate dequeue by popping all elements and restoring them after retrieving the front.

C. Use two stacks and transfer elements from push stack to pop stack on every push operation to keep pop stack always ready.

D. Use a queue internally and simulate stacks by reversing the order on every operation.

Solution

1. Step 1: Understand the problem constraints

   The goal is to implement a queue using stacks with efficient enqueue and dequeue operations.

2. Step 2: Analyze approaches for efficiency

   Approach A uses two stacks and transfers elements only when the pop stack is empty, achieving amortized O(1) per operation. Approach B uses recursion and is O(n) per pop. Approach C transfers on every push, causing O(n) per push. Approach D is unrelated and inefficient.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two stacks with lazy transfer -> amortized O(1) [OK]

Hint: Two stacks with lazy transfer gives amortized O(1) [OK]

Common Mistakes:

• Thinking transferring on every push is optimal
• Using recursion causing O(n) pop

4. Consider this buggy code for the stock span problem. Which line contains the subtle bug that causes incorrect spans when prices are equal?

medium

A. Line 9: span calculation does not add 1 when stack is not empty

B. Line 11: appending price after appending index to stack

C. Line 6: while condition uses '<' instead of '<='

D. Line 7: popping from stack without checking if empty

Solution

1. Step 1: Identify the bug in while condition

   The condition uses '<' instead of '<=', so equal prices are not popped, causing incorrect spans.

2. Step 2: Confirm other lines are correct

   Span calculation correctly handles empty stack. Appending order is correct. Stack emptiness is checked before popping.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Using '<=' ensures equal prices are popped for correct spans [OK]

Hint: Use '<=' in while to pop equal or smaller prices [OK]

Common Mistakes:

• Using '<' causes incorrect spans for equal prices
• Misplaced span calculation

5. Suppose you want to implement a queue using two stacks, but now the queue must support a 'reuse' operation that re-enqueues the last dequeued element. Which modification ensures correctness and efficiency?

hard

A. Use a third stack to hold reused elements and merge it with push_stack during transfers.

B. After every pop, immediately push the popped element back onto pop_stack to allow reuse, effectively making pop a peek operation.

C. Clear both stacks and re-insert all elements including the reused element to maintain order.

D. Store the last dequeued element separately and push it back onto the push_stack when reuse is called, without changing pop_stack.

Solution

1. Step 1: Understand reuse operation

   Reuse means re-enqueueing the last dequeued element, so it should be treated as a new push.

2. Step 2: Choose efficient modification

   Storing the last popped element separately and pushing it onto push_stack on reuse preserves order and amortized efficiency.

3. Step 3: Analyze other options

   After every pop, immediately push the popped element back onto pop_stack to allow reuse, effectively making pop a peek operation, breaks queue semantics by not removing element. Clearing both stacks and re-inserting all elements including the reused element is inefficient. Using a third stack to hold reused elements and merging it with push_stack during transfers adds unnecessary complexity.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Reuse as push to push_stack keeps order and efficiency [OK]

Hint: Reuse = push last popped element onto push_stack [OK]

Common Mistakes:

• Trying to reuse by pushing onto pop_stack
• Rebuilding stacks on reuse causing inefficiency