Stack Basic Problems

Five essential stack problems that test your ability to use LIFO ordering for matching, tracking state, and processing sequences. These are among the most frequently asked interview questions.

Problem 1: Valid Parentheses (LC 20)

Problem: Given a string containing just (){}[], determine if the input string is valid. Every open bracket must have a matching close bracket in the correct order.

# Examples:
#   "()"     -> True
#   "()[]{}" -> True
#   "(]"     -> False
#   "([)]"   -> False
#   "{[]}"   -> True
#
# Stack trace for "{[]}":
#   char '{'  -> push '{'          stack: ['{']
#   char '['  -> push '['          stack: ['{', '[']
#   char ']'  -> pop '[', matches  stack: ['{']
#   char '}'  -> pop '{', matches  stack: []
#   Stack empty -> Valid!

def isValid(s):
    """Check if parentheses are valid using a stack.

    Push opening brackets onto stack.
    For closing brackets, check if top of stack matches.

    Time:  O(n) - single pass through string
    Space: O(n) - stack can hold up to n/2 brackets
    """
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in matching:
            # Closing bracket: check match
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()
        else:
            # Opening bracket: push
            stack.append(char)

    return len(stack) == 0  # all brackets matched

Problem 2: Min Stack (LC 155)

Problem: Design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1) time.

# Approach: Use two stacks - one for values, one for minimums
#
# Operations on [5, 3, 7, 2, 8]:
#
#   push(5): stack=[5]       min_stack=[5]       min=5
#   push(3): stack=[5,3]     min_stack=[5,3]     min=3
#   push(7): stack=[5,3,7]   min_stack=[5,3,3]   min=3
#   push(2): stack=[5,3,7,2] min_stack=[5,3,3,2] min=2
#   pop():   stack=[5,3,7]   min_stack=[5,3,3]   min=3
#   getMin() -> 3

class MinStack:
    """Stack with O(1) minimum retrieval.

    Maintain a parallel stack that tracks the minimum
    at each level. When we push, we also push the
    current minimum. When we pop, we pop from both.

    All operations: O(1) time, O(n) space total
    """
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        # Push the minimum of val and current min
        min_val = min(val, self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(min_val)

    def pop(self):
        self.stack.pop()
        self.min_stack.pop()

    def top(self):
        return self.stack[-1]

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

Problem 3: Evaluate Reverse Polish Notation (LC 150)

Problem: Evaluate an arithmetic expression in Reverse Polish Notation (postfix). Valid operators are +, -, *, /. Each operand is an integer.

# Input: ["2", "1", "+", "3", "*"]
# Evaluation:
#   "2" -> push 2         stack: [2]
#   "1" -> push 1         stack: [2, 1]
#   "+" -> pop 1,2 -> 3   stack: [3]
#   "3" -> push 3         stack: [3, 3]
#   "*" -> pop 3,3 -> 9   stack: [9]
# Output: 9
#
# This is equivalent to: (2 + 1) * 3 = 9

def evalRPN(tokens):
    """Evaluate expression in Reverse Polish Notation.

    Use a stack: push numbers, pop two operands for operators.
    Note: Python's // rounds toward negative infinity,
    but we need truncation toward zero (use int(a/b)).

    Time:  O(n) - process each token once
    Space: O(n) - stack for operands
    """
    stack = []
    operators = {'+', '-', '*', '/'}

    for token in tokens:
        if token in operators:
            b = stack.pop()  # second operand (popped first)
            a = stack.pop()  # first operand

            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                # Truncate toward zero (not floor division)
                stack.append(int(a / b))
        else:
            stack.append(int(token))

    return stack[0]

Problem 4: Daily Temperatures (LC 739)

Problem: Given daily temperatures, return an array where answer[i] is the number of days until a warmer temperature. If no warmer day exists, put 0.

# Input:  [73, 74, 75, 71, 69, 72, 76, 73]
# Output: [1,  1,  4,  2,  1,  1,  0,  0]
#
# Stack trace (store indices, not values):
#
#   i=0, T=73: stack empty, push 0       stack: [0]
#   i=1, T=74: 74 > T[0]=73, pop 0      ans[0]=1-0=1
#              push 1                    stack: [1]
#   i=2, T=75: 75 > T[1]=74, pop 1      ans[1]=2-1=1
#              push 2                    stack: [2]
#   i=3, T=71: 71 < T[2]=75, push 3     stack: [2, 3]
#   i=4, T=69: 69 < T[3]=71, push 4     stack: [2, 3, 4]
#   i=5, T=72: 72 > T[4]=69, pop 4      ans[4]=5-4=1
#              72 > T[3]=71, pop 3       ans[3]=5-3=2
#              72 < T[2]=75, push 5      stack: [2, 5]
#   i=6, T=76: 76 > T[5]=72, pop 5      ans[5]=6-5=1
#              76 > T[2]=75, pop 2       ans[2]=6-2=4
#              push 6                    stack: [6]
#   i=7, T=73: 73 < T[6]=76, push 7     stack: [6, 7]
#   Remaining indices (6, 7) stay 0.

def dailyTemperatures(temperatures):
    """Find days until warmer temperature using a stack.

    Maintain a decreasing stack of indices.
    When we find a warmer day, pop and calculate distance.

    Time:  O(n) - each index pushed/popped at most once
    Space: O(n) - stack size
    """
    n = len(temperatures)
    answer = [0] * n
    stack = []  # stores indices

    for i in range(n):
        # Pop all indices with lower temperatures
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_idx = stack.pop()
            answer[prev_idx] = i - prev_idx

        stack.append(i)

    return answer

Problem 5: Asteroid Collision (LC 735)

Problem: Asteroids move in a row. Positive = right, negative = left. When two collide (right meets left), the smaller one explodes. If equal, both explode. Find the state after all collisions.

# Input:  [5, 10, -5]
# Output: [5, 10]
#
# Simulation:
#   5 (right) -> push              stack: [5]
#   10 (right) -> push             stack: [5, 10]
#   -5 (left) -> collides with 10
#     |10| > |-5| -> -5 explodes   stack: [5, 10]
#
# Input:  [8, -8]
# Output: []
#   8 (right) -> push              stack: [8]
#   -8 (left) -> collides with 8
#     |8| == |-8| -> both explode  stack: []
#
# Input:  [10, 2, -5]
# Output: [10]
#   10 -> push                     stack: [10]
#   2 -> push                      stack: [10, 2]
#   -5 -> collides with 2
#     |2| < |-5| -> 2 explodes     stack: [10]
#   -5 -> collides with 10
#     |10| > |-5| -> -5 explodes   stack: [10]

def asteroidCollision(asteroids):
    """Simulate asteroid collisions using a stack.

    Only collisions happen when stack top is positive (right)
    and current asteroid is negative (left).

    Time:  O(n) - each asteroid pushed/popped at most once
    Space: O(n) - stack for surviving asteroids
    """
    stack = []

    for asteroid in asteroids:
        alive = True

        while alive and stack and asteroid < 0 < stack[-1]:
            # Collision: positive (top) vs negative (current)
            if stack[-1] < abs(asteroid):
                # Top asteroid is smaller, it explodes
                stack.pop()
            elif stack[-1] == abs(asteroid):
                # Equal size, both explode
                stack.pop()
                alive = False
            else:
                # Top asteroid is larger, current explodes
                alive = False

        if alive:
            stack.append(asteroid)

    return stack

Complexity Summary