Algorithms from zero
Lists, stacks, queues: build a sequence toolkit
Reading about pointer moves is not the same as making them yourself without losing a node. Build a small library that holds a sequence three ways — list, stack, queue — add a deque and a monotonic-stack solver, and prove every complexity claim with your own measurements.
Turn the unit’s mental model into working code: implement each structure from primitives (no built-in stack/queue/deque), defend each operation’s complexity with a test, and apply the monotonic stack to a real next-greater problem end to end.
Build a 'sequence toolkit' in the language of your choice: a singly linked list with a sentinel head, a stack and a queue, an O(1)-at-both-ends deque, and a monotonic-stack solver — each implemented from scratch, each backed by a test that demonstrates correctness and the claimed time complexity.
- All structures are implemented from primitives — no language-provided Stack/Queue/Deque/LinkedList classes used internally.
- A passing test suite: reversal mirrors a 1,000-node list, hasCycle is correct on cyclic and acyclic inputs, isBalanced handles nested and mismatched brackets, BFS prints nodes level by level, and nextGreaterElement matches the brute-force reference on all random cases.
- The complexity log shows real timings: the shift-based queue's per-op cost rises with N (quadratic total) while the pointer/circular-buffer queue stays flat (linear total) — measured, not asserted.
- A one-paragraph write-up: for each structure, name the operation that defines its cost (head insert for the list, dequeue for the queue, push-once/pop-once for the monotonic stack) and why your implementation hits the target complexity.
- Add findCycleStart using the second-pass tortoise-and-hare trick (one pointer at head, one at the meeting point, both at speed one) and test it on lists with cycles starting at different positions.
- Generalize the monotonic-stack solver into one function that computes next-greater, next-smaller, previous-greater, and previous-smaller by parameterizing the comparison and scan direction.
- Solve 'largest rectangle in a histogram' with the monotonic stack and verify against a brute-force O(n^2) reference on random bar heights.
- Implement a min-stack: a stack that also returns its current minimum in O(1), using an auxiliary stack — and explain why a single counter cannot do it.
This is the loop you run on every real sequence problem: pick the structure by the dominant operation, implement it from primitives so you actually make the pointer moves, and prove the complexity with a measurement instead of an assertion. A sentinel erases head special cases; saving the successor pointer keeps reversal honest; head/tail pointers or a circular buffer keep the queue O(1); and the push-once/pop-once invariant keeps the monotonic stack linear. Build the toolkit once and these become muscle memory in interviews and in production.