~/problems

Problems

Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.

Stacks

Monotonic stack

Next greater/smaller element in O(n); histogram rectangles; trapping water.

Visual guide Quiz (10) Spot the pattern
Notes

Recognise it when: "next greater / smaller element", "how many days until warmer", "largest rectangle", "trapping water", or spans. Anything where each element needs its nearest bigger or smaller neighbour.

res = [-1] * n
stack = []                        # indexes, values decreasing
for i, x in enumerate(a):
    while stack and a[stack[-1]] < x:
        res[stack.pop()] = i      # x is the next greater for that index
    stack.append(i)
  • Each index is pushed and popped once, so it's O(n).
  • Largest rectangle: keep increasing heights. When you pop a bar, its width runs from the new stack top to i. A sentinel height of 0 at the end flushes the stack.

Gotchas: strict vs non-strict comparison when values are equal (decides left vs right ties). Store indexes, not values.

8 problems

Interview roadmap

Stacks Matching brackets, paths, next greater element.

Monotonic stack guide

esc