Problem Set

Valid Parentheses

Problem: Given a string containing only (, ), {, }, [, and ], determine if the input is valid. An input is valid if every opening bracket has a matching closing bracket in the correct order.

Approach: Push each opening bracket onto the stack. When you encounter a closing bracket, check if it matches the top of the stack. If it does, pop the stack. If not, or if the stack is empty, the string is invalid. At the end, the stack should be empty.

def is_valid(s):
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in mapping:
            if stack and stack[-1] == mapping[char]:
                stack.pop()
            else:
                return False
        else:
            stack.append(char)
    return len(stack) == 0

Complexity: O(n) time, O(n) space.

Min Stack

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

Approach: Use two stacks. The main stack holds all elements. The min stack holds the current minimum at each level. When pushing, also push onto the min stack if the value is less than or equal to the current minimum. When popping, pop from both stacks.

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):
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()
        return val

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

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

Complexity: O(1) for all operations. O(n) space for the auxiliary min stack.

Evaluate Reverse Polish Notation

Problem: Given an array of tokens representing a Reverse Polish Notation expression, evaluate it. Tokens are numbers or operators (+, -, *, /).

Approach: Push numbers onto the stack. When you encounter an operator, pop the top two elements, apply the operator, and push the result. The final answer is the only element left on the stack.

def eval_rpn(tokens):
    stack = []
    for token in tokens:
        if token in '+-*/':
            b = stack.pop()
            a = stack.pop()
            if token == '+': stack.append(a + b)
            elif token == '-': stack.append(a - b)
            elif token == '*': stack.append(a * b)
            else: stack.append(int(a / b))
        else:
            stack.append(int(token))
    return stack[0]

Complexity: O(n) time, O(n) space.

Implement Queue Using Stacks

Problem: Implement a FIFO queue using only two stacks. The queue should support push, pop, peek, and isEmpty.

Approach: Use an input stack for push operations and an output stack for pop/peek. When the output stack is empty and you need to pop, transfer all elements from the input stack to the output stack (reversing the order). Each element is moved at most twice.

class QueueWithStacks:
    def __init__(self):
        self.input = []
        self.output = []

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

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

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

    def isEmpty(self):
        return not self.input and not self.output

    def _transfer(self):
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())

Complexity: Amortized O(1) per operation. O(n) space.

Daily Temperatures

Problem: Given an array of daily temperatures, return an array where each element tells you how many days you have to wait until a warmer temperature. If there is no future day, use 0.

Approach: Use a monotonic decreasing stack that stores indices. Iterate through the array. For each day, while the stack is not empty and the current temperature is warmer than the temperature at the stack's top index, pop and record the difference in indices as the answer for that popped index.

def daily_temperatures(temps):
    n = len(temps)
    result = [0] * n
    stack = []
    for i in range(n):
        while stack and temps[i] > temps[stack[-1]]:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)
    return result

Complexity: O(n) time, O(n) space. Each element is pushed and popped at most once.

Largest Rectangle in Histogram

Problem: Given an array of bar heights representing a histogram, find the area of the largest rectangle that can be formed within the histogram bounds.

Approach: Use a monotonic increasing stack of indices. For each bar, if it is taller than the stack top, push it. If it is shorter, pop bars and calculate areas using the popped bar's height and the width between the current index and the new stack top. This ensures each bar extends as far left and right as possible.

Complexity: O(n) time, O(n) space.

Trapping Rain Water

Problem: Given an array of bar heights, compute how much water can be trapped after rain.

Approach: Use a stack that stores indices of bars in decreasing order of height. When a taller bar is found, pop bars and calculate trapped water as the difference between the current bar height and the popped bar height, multiplied by the width. Alternatively, use two pointers for O(1) space.

Complexity: O(n) time, O(n) space with stack approach, O(1) space with two pointers.

Problem Difficulty Summary