Intermediate

Stacks & Queues

Stacks (LIFO) and queues (FIFO) are fundamental data structures that appear in parsing, BFS/DFS traversals, and many optimization problems. This lesson covers 5 essential problems with complete solutions.

Problem 1: Valid Parentheses

Brute Force (Repeated Replacement): O(n²) Time, O(n) Space

def is_valid_brute(s):
    """Repeatedly remove innermost valid pairs until empty or stuck."""
    while '()' in s or '{}' in s or '[]' in s:
        s = s.replace('()', '')
        s = s.replace('{}', '')
        s = s.replace('[]', '')
    return s == ''

print(is_valid_brute("()[]{}"))    # True
print(is_valid_brute("([)]"))      # False

Optimal (Stack): O(n) Time, O(n) Space

def is_valid(s):
    """
    Use a stack to track unmatched opening brackets.
    For each character:
    - If opening bracket: push to stack
    - If closing bracket: check if it matches the top of stack
    """
    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

# Test
print(is_valid("()"))         # True
print(is_valid("()[]{}"))     # True
print(is_valid("(]"))         # False
print(is_valid("([)]"))       # False
print(is_valid("{[]}"))       # True
print(is_valid(""))           # True

AI/ML context: Bracket matching is used in JSON/config file validation for ML pipeline configs, validating mathematical expressions in symbolic computation, and checking well-formedness of model architecture definitions.

Problem 2: Min Stack

Brute Force: O(n) getMin

class MinStackBrute:
    """Simple stack where getMin scans all elements."""
    def __init__(self):
        self.stack = []

    def push(self, val):
        self.stack.append(val)

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

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

    def getMin(self):
        return min(self.stack)  # O(n) - not good enough

Optimal (Two Stacks): O(1) All Operations

class MinStack:
    """
    Maintain a second stack that tracks the minimum at each level.

    Key insight: When we push a value, the minimum can only
    decrease or stay the same. So we push the current minimum
    onto the min_stack alongside each element.
    """
    def __init__(self):
        self.stack = []
        self.min_stack = []  # Parallel stack tracking minimums

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

    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]


# Test
ms = MinStack()
ms.push(-2)
ms.push(0)
ms.push(-3)
print(ms.getMin())   # -3
ms.pop()
print(ms.top())      # 0
print(ms.getMin())   # -2

AI/ML context: Tracking running minimums/maximums is used in early stopping during training (tracking best validation loss), gradient clipping (tracking gradient norms), and monitoring metrics in experiment tracking systems.

Problem 3: Implement Queue Using Stacks

Optimal (Amortized O(1)): Two-Stack Approach

class MyQueue:
    """
    Queue using two stacks with amortized O(1) operations.

    Stack 1 (input): receives all push operations
    Stack 2 (output): provides all pop/peek operations

    When output stack is empty, transfer all elements from
    input stack (reversing order, which gives FIFO behavior).

    Each element is moved at most twice (into input, into output),
    so amortized cost per operation is O(1).
    """
    def __init__(self):
        self.input_stack = []   # For push
        self.output_stack = []  # For pop/peek

    def push(self, x):
        self.input_stack.append(x)

    def pop(self):
        self._transfer()
        return self.output_stack.pop()

    def peek(self):
        self._transfer()
        return self.output_stack[-1]

    def empty(self):
        return not self.input_stack and not self.output_stack

    def _transfer(self):
        """Move elements from input to output only when output is empty."""
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())


# Test
q = MyQueue()
q.push(1)
q.push(2)
print(q.peek())    # 1
print(q.pop())     # 1
print(q.empty())   # False
print(q.pop())     # 2
print(q.empty())   # True

AI/ML context: Understanding how to build one data structure from another is crucial when working with constrained environments. In distributed ML, message passing between workers often uses queue abstractions built on available primitives.

Problem 4: Daily Temperatures (Monotonic Stack)

Brute Force: O(n²) Time, O(n) Space

def daily_temperatures_brute(temperatures):
    """For each day, scan forward to find next warmer day."""
    n = len(temperatures)
    result = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if temperatures[j] > temperatures[i]:
                result[i] = j - i
                break
    return result

print(daily_temperatures_brute([73, 74, 75, 71, 69, 72, 76, 73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

Optimal (Monotonic Stack): O(n) Time, O(n) Space

def daily_temperatures(temperatures):
    """
    Use a monotonic decreasing stack (stores indices).

    For each temperature:
    - While stack is not empty AND current temp > temp at stack top:
      Pop the index, calculate waiting days
    - Push current index onto stack

    Elements remaining on the stack never found a warmer day (answer = 0).
    """
    n = len(temperatures)
    result = [0] * n
    stack = []  # indices of days with no warmer day yet

    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_day = stack.pop()
            result[prev_day] = i - prev_day
        stack.append(i)

    return result

# Test
print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

print(daily_temperatures([30, 40, 50, 60]))  # [1, 1, 1, 0]
print(daily_temperatures([30, 20, 10]))       # [0, 0, 0]

AI/ML context: Monotonic stacks find “next greater/smaller” elements efficiently. This pattern is used in histogram-based gradient boosting (finding split points), signal processing for peak detection, and computing attention spans in efficient transformer variants.

Problem 5: Next Greater Element I

Brute Force: O(n * m) Time, O(n) Space

def next_greater_brute(nums1, nums2):
    """For each element in nums1, find it in nums2, then scan right."""
    result = []
    for num in nums1:
        found = False
        found_num = False
        for val in nums2:
            if val == num:
                found_num = True
            elif found_num and val > num:
                result.append(val)
                found = True
                break
        if not found:
            result.append(-1)
    return result

Optimal (Stack + Hash Map): O(n + m) Time, O(m) Space

def next_greater_element(nums1, nums2):
    """
    Step 1: Build a map of next greater elements for ALL
    elements in nums2 using a monotonic stack.

    Step 2: Look up each element of nums1 in the map.

    The stack processes nums2 right-to-left:
    - Pop elements smaller than current (they are irrelevant)
    - Stack top (if exists) is the next greater element
    - Push current element
    """
    # Build next-greater map for nums2
    next_greater = {}
    stack = []

    for num in reversed(nums2):
        # Pop elements that are not greater
        while stack and stack[-1] <= num:
            stack.pop()

        # Stack top is next greater (or -1 if empty)
        next_greater[num] = stack[-1] if stack else -1

        # Push current
        stack.append(num)

    # Look up results for nums1
    return [next_greater[num] for num in nums1]

# Test
print(next_greater_element([4, 1, 2], [1, 3, 4, 2]))
# [-1, 3, -1]

print(next_greater_element([2, 4], [1, 2, 3, 4]))
# [3, -1]

AI/ML context: Finding the next greater element is a building block for computing histograms, constructing decision tree split points, and implementing priority-based scheduling in training pipelines where you need to find the next job with higher priority.

Summary: Complexity Comparison

Problem	Brute Force	Optimal	Key Technique
Valid Parentheses	O(n²)	O(n)	Stack with matching map
Min Stack	O(n) getMin	O(1) all ops	Parallel min-tracking stack
Queue Using Stacks	N/A	O(1) amortized	Two-stack transfer pattern
Daily Temperatures	O(n²)	O(n)	Monotonic decreasing stack
Next Greater Element	O(n * m)	O(n + m)	Monotonic stack + hash map