Here is the problem for Min Stack

1. Understand the problem

• We need a normal stack, but also need to track the minimum value so far quickly.

2. Clarify Constraints & Ask Questions

1. Can there be duplicate values?

=> Yes.

1. What to return if operations are called on empty stack?

=> Typically nothing (or error). In coding tests, assume valid usage.

1. Can negative numbers be included?

=> Yes, any integer.

1. Time complexity required?

=> O(1) per operation.

1. Memory constraints?

=> No specific constraints, but use O(n) space.

3. Explore Examples

push(-2)
push(0)
push(-3)
getMin() ➝ -3
pop()
top() ➝ 0
getMin() ➝ -2

4. Brainstorm 2 - 3 solutions

4.1. Naive solution - O(N) getMin()

• Use normal stack.

• getMin() → scan entire stack → O(n) time.

4.2. Solution 2 – Maintain a sorted structure - O(logN) Insert/Delete

• Insert/Delete from left to right to a heap => O(logN).

• Updates on deletion are O(log n) → Not O(1).

4.3. Solution 3 - Two Stack - O(N)

Use:

• stack → actual values.

• min_stack → current minimums from [start, i], [start, i + 1],…

Idea:

• If new value ≤ current min → push to min_stack.

• If popped value == min_stack top → pop min too.

• Time: O(1).

• Space: O(n).

4.4. Solution 4 - One Stack - O(N)

• Idea: Instead of store the min stack => store diff from curr - min_stack

1. Push: If diff < 0, new is min_stack.

2. Pop: If pop it, reverse the old_min_stack.

3. top()

• If positive difference → normal value.

• If negative → value was the current min.

1. getMin()

• Return the min value.

5. Implement solutions

5.1. Brute Force - GetMin O(N)

class MinStack:

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

    def push(self, val: int) -> None:
        self.stack.append(val)

    def pop(self) -> None:
        if self.stack:
            self.stack.pop()

    def top(self) -> int:
        return self.stack[-1] if self.stack else None

    def getMin(self) -> int:
        if not self.stack:
            return None
        min_val = self.stack[0]
        for num in self.stack:
            if num < min_val:
                min_val = num
        return min_val

• Time complexity:

  • Insert/Update/Delete: O(1).
  • GetMin: O(N).

• Space: O(N)

5.2. Two Stack for Min Stack - GetMin O(1), Space O(2N)

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []  # Stores current minimums

    def push(self, val: int) -> None:
        self.stack.append(val)
        # If min_stack is empty or new value is smaller/equal → push it
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        if not self.stack:
            return
        val = self.stack.pop()
        # If popped value is minimum → remove from min_stack
        if val == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1] if self.stack else None

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

• Time: O(1).

• Space: O(2N).

5.3. One Stack - GetMin O(1), Space O(N)

• Idea:
  • Use min_val to store the minimum value.
  • Stack store the diff array[] same length with current stack[], if negative this is the index of min_val, if positive revert diff + min_val, if negative it is current min and revert old_min.

class MinStack:
    def __init__(self):
        self.min = float('inf')
        self.stack = []

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append(0)
            self.min = val
        else:
            self.stack.append(val - self.min)
            if val < self.min:
                self.min = val

    def pop(self) -> None:
        if not self.stack:
            return

        pop = self.stack.pop()

        if pop < 0:
            self.min = self.min - pop

    def top(self) -> int:
        top = self.stack[-1]
        if top > 0:
            return top + self.min
        else:
            return self.min

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

• Time: O(1).

• Space: O(N).