DSA · A field guide
Problem editorials
Not a solutions dump. Each entry starts where you start — a problem statement and no idea which tool to reach for — and walks the whole distance to working Java, stopping at every place the reasoning could have gone wrong.
18 editorials·7 categories·5h 30m of reading·0 read
Stacks & Monotonic Order
Problems where the thing you saw most recently is the thing you need next. The stack is almost never the interesting decision — what you choose to put on it is.
Design a min stack
Push and pop in O(1) is free. The trick is answering “what is the minimum right now?” instantly — without ever scanning.
Auxiliary stackInvariant designO(1) querieseasytime O(1) per opspace O(N)16 minEvaluating postfix expressions
This is not a string problem. It is a memory problem — and the way you are forced to remember things points straight at one data structure.
Stack machineExpression parsingOperand ordermediumtime O(n)space O(n)20 minLongest valid parentheses
The trick is not storing brackets — it is storing indices. The answer is a length, and lengths are measured between boundaries.
Stack of indicesSentinelBoundary arithmetichardtime O(n)space O(n), O(1) variant20 min
Sliding Window
A window moves one step and almost nothing changes. These are won by tracking the difference — what left, what entered — instead of recomputing the whole.
Every anagram of a pattern
An anagram is the same characters in a different order — so forget the letters and track the counts. When the counts match, you have found one.
Fixed windowCount vectorMatch countermediumtime O(N + M)space O(1) — 26 counters20 minDistinct elements in every window
Neighbouring windows share almost everything. Do not recount — track only what leaves and what enters, and keep a running tally.
Fixed windowFrequency mapAdd/remove deltamediumtime O(N)space O(B)19 min
Hashing & Frequency
Counting as a first-class step. Once you hold the totals, the question usually stops being about the sequence and turns into arithmetic on the counts.
The first unique element
You cannot tell whether the first value is one-of-a-kind until you have seen the whole array. Learn the totals first, then walk in order.
Two passesFrequency mapOrder preservationeasytime O(N)space O(N)19 minThe longest palindrome you can build
You may rearrange freely — so positions stop mattering and counts take over. It becomes pure bookkeeping: how many pairs, plus one centre.
CountingPairs plus a centreParityeasytime O(N)space O(1) — fixed alphabet16 min
Heaps & Ordering
When you need the top of an order without paying to sort everything — and when the real algorithm turns out to live inside the comparator.
Binary Search
Halving works on far more than a sorted array looking for a target. What it really needs is one yes/no question whose answer flips exactly once — and the hard part is finding that question.
First and last position of a value
One binary search finds an occurrence. To pin down the edges of a run of duplicates, don’t stop when you find it — keep leaning toward the boundary.
Boundary searchLeandon't stopTwo passesmediumtime O(log n)space O(1)19 minSearch a rotated sorted array
Rotation breaks global order in exactly one place — so around any midpoint one half is always still sorted. That surviving structure is all binary search needs.
Half-sorted invariantTwo-layer decisionPivotmediumtime O(log n)space O(1)18 minFind a peak element
There is no target and the array is not sorted. But the local slope always points toward higher ground — and uphill has to end in a summit somewhere.
Search on slopeNo targetGuaranteed descentmediumtime O(log n)space O(1)17 minPreimage of the factorial zeroes
How many x give x! exactly k trailing zeroes? You never touch a factorial — you count factors of five, notice the count only climbs, and search a number line with no array under it.
Search the answerMonotone functionLegendre's formulahardtime O(log² k)space O(1)19 min
Bit Manipulation
A small vocabulary, not a bag of tricks. Read the low bit, drop it, cancel with XOR, delete the lowest one — every classic bit problem is a sentence built from those words.
The bit vocabulary
Eight classic problems, but not eight tricks. They are all built from a handful of moves. Learn the words, and the sentences write themselves.
Six core movesXOR cancellationn & (n-1)Cheat sheetmediumtime O(n)space O(1)21 minTotal Hamming distance
Sum the differing bits over every pair. The trick is not faster pair comparison — it is refusing to look at pairs at all, and counting one bit column at a time.
Per-bit columnsCounting contributionLoop inversionmediumtime O(n)space O(1)18 minDivide two integers
No multiply, no divide, no modulo. Division is just “how many divisors fit” — counted in powers of two instead of one at a time.
DoublingShift and subtract32-bit overflowmediumtime O(log n)space O(1)18 min
Arrays & Invariants
Problems that look like they want a simulation. Each one is really asking for a property the operations cannot change — find it and the answer is a single pass, or arithmetic.
The next permutation
Reordering a sequence into the very next one in dictionary order. Not by listing all N! arrangements — by making the smallest possible change as far right as it can go.
Greedy three-step walkRightmost changeReverse the suffixmediumtime O(N)space O(1)20 minMax chunks to make it sorted
Do not simulate sorting every partition. Ask the sharper question: where can you cut so that nothing ever needs to cross the line?
Prefix maxSuffix minSafe boundaryhardtime O(N)space O(N)16 minReaching zero by split and merge
Split a number into two that sum to it; merge two into their XOR. Do not hunt for the moves — find the property the moves cannot touch.
Invariant huntingParity argumentSum vs XORmediumtime O(N)space O(1)19 min