Algorithms tutorials

Algorithm articles usually fail in one of two ways: they show a solution without the reasoning that produces it, or they explain the idea and leave the implementation as an exercise. The walkthroughs here do both — the invariant first, then code that runs, then the complexity and the edge cases that break a naive version.

The material is organised by technique rather than by problem, because the technique is what transfers. Binary search on a sorted array is one problem; recognising that a problem has a monotonic predicate you can binary-search over is the skill. The same holds for the sliding window, two pointers, and the recurrence patterns behind dynamic programming.

Implementations are in Java unless a language makes a particular point clearer. Off-by-one handling is written out explicitly rather than hidden behind a helper, since that is where most of these go wrong.

Each walkthrough follows the same order, because the order is the method. First the brute-force solution, stated plainly and with its complexity, so there is a baseline. Then the observation that makes it unnecessary — the sorted property, the monotonic predicate, the overlapping subproblem. Then the improved implementation, and finally the complexity that justifies the extra work.

That structure exists because jumping straight to an optimal solution is where explanations lose people. Knowing that a problem can be solved in linear time is not the same as seeing why, and the second is the only part that helps with a problem you have not met before.

The implementations favour clarity over cleverness. A tight one-liner that computes the right answer is worse than eight readable lines when the point is to understand the method, and anything genuinely subtle is commented in place rather than explained afterwards.

Complexity notation describes how a cost grows, not how long something takes. An O(n log n) sort can lose to an O(n^2) one on a few dozen elements, because the constant factors and the memory access pattern dominate at that size. The guides state the asymptotic cost and then say where the crossover actually sits, because the second number is the one that decides which implementation you ship. Locality matters for the same reason: an array walked in order and a linked list of the same length have identical complexity and very different behaviour once the data no longer fits in cache.

A note on how these are written. Each one states the brute-force solution first, because it is the reference the fast version has to agree with, and then names the single observation that collapses the complexity: the sorted half in a rotated array, the running maximum in a sliding window, the stale frequency count that is safe to leave stale. The code is short; the paragraph explaining why the pointer moves that way is the part worth reading twice.