Practice Problems

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 4 Time to complete: ~30 minutes

Table of Contents

1. Implement a Queue Using Two Stacks
2. Valid Parentheses, Formalized
3. Next Greater Element — the Monotonic Stack Pattern
4. Try It Yourself
5. Summary & Next Steps

1. Implement a Queue Using Two Stacks

A classic exercise in reasoning about access order: simulate FIFO behavior using only two LIFO stacks.

class QueueWithTwoStacks:
    def __init__(self):
        self._in_stack = []      # receives new elements
        self._out_stack = []     # serves dequeues, in reversed (FIFO) order
 
    def enqueue(self, item):
        self._in_stack.append(item)          # O(1)
 
    def dequeue(self):
        if not self._out_stack:
            while self._in_stack:
                self._out_stack.append(self._in_stack.pop())   # reverse the order
        return self._out_stack.pop()
 
q = QueueWithTwoStacks()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())   # 1 — FIFO order preserved
print(q.dequeue())   # 2
q.enqueue(4)
print(q.dequeue())   # 3

Popping everything off _in_stack and pushing it onto _out_stack reverses the order twice: once going in (LIFO), once coming back out (LIFO again) — two reversals cancel out and restore the original FIFO order. Each element is moved between the stacks at most once, so the amortized cost per operation is O(1), even though any single dequeue call might move several elements in one go.

2. Valid Parentheses, Formalized

Module 5 Chapter 2 introduced is_balanced. Here it is again, generalized to the exact interview framing — "given a string containing just the characters ()[]{}, determine if the input is valid":

def is_valid_parentheses(s):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}
 
    for char in s:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack.pop() != pairs[char]:
                return False
        # any other character is simply ignored in this formalized version
 
    return not stack
 
print(is_valid_parentheses("()[]{}"))   # True
print(is_valid_parentheses("(]"))        # False

3. Next Greater Element — the Monotonic Stack Pattern

For each element in an array, find the next element to its right that is strictly greater — or -1 if none exists. The naive approach checks every pair, O(n²); a monotonic stack (one kept in decreasing order from bottom to top) solves it in O(n).

def next_greater_element(nums):
    result = [-1] * len(nums)
    stack = []      # stores INDICES, kept in decreasing order of nums[index]
 
    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            result[stack.pop()] = num     # num is the "next greater" for stack.pop()
        stack.append(i)
 
    return result
 
print(next_greater_element([2, 1, 2, 4, 3]))
# [4, 2, 4, -1, -1]

Trace it: at i=3 (num=4), the stack holds indices for 2, 1, 2 (values nums[0]=2, nums[1]=1, nums[2]=2) — every one of them is smaller than 4, so all three get popped and assigned 4 as their answer, in one pass. Each index is pushed once and popped at most once across the entire run, which is why the total work is O(n) despite the while loop nested inside the for loop — this is the amortized-analysis idea from Chapter 1's push/pop discussion, applied across the whole array rather than a single call.

4. Try It Yourself

Using the monotonic stack pattern from Section 3, solve: given daily temperatures, return for each day how many days you'd have to wait until a warmer temperature. If there is no future day for which this is possible, put 0.

def daily_temperatures(temperatures):
    # Your solution here — this is structurally identical to
    # next_greater_element, but the answer stored is a DISTANCE (i - stack.pop()),
    # not the value itself.
    pass

def daily_temperatures(temperatures):
    result = [0] * len(temperatures)
    stack = []
 
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev_index = stack.pop()
            result[prev_index] = i - prev_index    # distance, not the value
        stack.append(i)
 
    return result
 
print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

5. Summary & Next Steps

Key Takeaways

• Two stacks can simulate a queue because reversing order twice (once per stack) restores the original FIFO sequence — amortized O(1) per operation.
• The monotonic stack pattern solves "find the next greater/smaller element" problems in O(n), versus the O(n²) naive nested-loop approach — recognize it whenever a problem asks for "next greater," "next smaller," or similar relative comparisons across an array.
• Once you can implement one structure (a queue) in terms of another (two stacks), you've internalized that these structures are defined by their access pattern, not by any specific underlying implementation.

Concept Check

1. Why does moving every element from _in_stack to _out_stack restore FIFO order, when each individual stack is LIFO?
2. In next_greater_element, why is the total work across the whole array O(n) despite the nested while loop?
3. What's the one-line change needed to turn next_greater_element into daily_temperatures?

Next Module

→ Module 6: Linked Lists

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index