DSA & Coding — Cheat Sheet

Big-O describes how the running time or space of an algorithm grows as the input grows — the shape of the curve, not the time on a clock. It deliberately drops two things. Constant factors: 2n and 100n are both O(n), even though one is fifty times slower. And lower-order terms: n² + n + 500 is O(n²), because once n is large the n² term dominates everything else. That is a feature, not sloppiness. Constants depend on the machine, the language, and the compiler; growth rate does not. An O(n log n) sort beats an O(n²) sort on large input regardless of hardware. The trap: for small n the constants win. Java's Arrays.sort() switches to insertion sort — O(n²) — for subarrays under about 47 elements, because its constant factor is tiny. "Asymptotically better" and "faster on your actual data" are different claims.

They bound the growth from different sides. Big-O (O) is an upper bound — the algorithm grows no faster than this. Big-Omega (Ω) is a lower bound — it grows at least this fast. Big-Theta (Θ) is a tight bound, meaning upper and lower agree. Quicksort is O(n²) in the worst case and Ω(n log n) in the best. Since those differ, there is no single Θ for quicksort overall — but you can say its average case is Θ(n log n). In practice interviewers and engineers say "O" when they mean "Θ", because the tight bound is what anyone actually cares about. Saying merge sort is O(n²) is technically true and useless — n log n is an upper bound too, and it is the honest one. Being precise here is a cheap way to show you understand the notation rather than repeating it.

Amortised complexity is the average cost per operation across a long sequence, when occasional expensive operations are paid for by many cheap ones. ArrayList.add() is usually O(1) — write to the backing array, bump the size. But when the array is full it allocates a new one at 1.5x the size and copies everything: O(n) for that one call. The amortised argument: to trigger a resize at size n you must have performed roughly n/2 cheap appends since the last one. Spread the O(n) copy across those appends and each carries O(1) extra work. So n appends cost O(n) total, or O(1) amortised each. This is why growth must be multiplicative. If ArrayList grew by a fixed +1 each time, every add would copy and n appends would cost O(n²). Amortised is not average-case. Average-case reasons about random input; amortised is a worst-case guarantee over a sequence, with no probability involved.

Count two things: what you explicitly allocate, and the call stack. The stack is the part candidates forget. Each pending recursive call holds a frame with its parameters and locals, so the stack depth multiplied by the frame size is real memory. A recursion that goes n deep is O(n) space even if it allocates nothing. Binary search recursively: O(log n) space from the stack, though the iterative version is O(1). Naive fibonacci: exponential time but only O(n) space, because the tree is explored depth-first and only one root-to-leaf path is on the stack at a time. For a balanced binary tree, recursive traversal is O(log n) space; for a degenerate (linked-list-shaped) tree it is O(n) and can blow the stack. Tail calls would let a compiler reuse the frame, but the JVM does not do tail-call elimination — so in Java, deep recursion is a StackOverflowError waiting to happen, and you convert it to a loop with an explicit stack.

Because log n grows almost imperceptibly. For a billion elements, log₂(n) is about 30. A linear scan of a billion items does a billion comparisons. Binary search does 30. That is not a small win, it is the difference between a request that times out and one that returns instantly. The intuition: each step of an O(log n) algorithm throws away a constant fraction of the remaining work — usually half. Doubling the input adds exactly one more step. Doubling the input to an O(n) algorithm doubles the work. This is why balanced trees, binary search, and heaps matter so much: they turn "look at everything" into "halve it repeatedly". The cost is a precondition. Binary search needs sorted data; a balanced tree needs rebalancing on write. You are trading write-time work and structural constraints for read-time speed.

Arrays store elements in contiguous memory. Linked lists store nodes anywhere and connect them by references. Arrays give O(1) access by index — the address is a multiplication away. Insert or delete in the middle is O(n) because everything after shifts. Linked lists give O(1) insert or delete once you hold the node, but access by index is O(n) because you must walk from the head. The answer interviewers want but rarely hear is cache locality. An array's elements sit together, so a single cache line fetch brings several of them in. Linked list nodes are scattered across the heap, so each hop is potentially a cache miss. In practice ArrayList outperforms LinkedList even for many mid-list insertions, because the memcpy of a shift is far cheaper than chasing pointers. Reach for a linked list when you need O(1) splice with a held reference — LRU cache eviction is the classic case. Otherwise default to an array-backed list.

The tell is a nested traversal where the inner one is not obviously bounded. Common accidents: calling list.contains() inside a loop, which is O(n) per call and O(n²) overall. String concatenation in a loop in Java, where each + builds a new string and copies. Calling list.get(i) on a LinkedList inside a loop — each get walks from the head. Removing from the front of an ArrayList in a loop, shifting every time. The reliable check is empirical: run with n, then 2n, then 4n. Linear work roughly doubles each time; quadratic work roughly quadruples. That doubling test finds accidental quadratics faster than reading the code. The usual fix is a hash set or map to turn an O(n) membership test into O(1), or StringBuilder to turn repeated copying into amortised appends.

Building a heap with the bottom-up heapify is O(n), not O(n log n), and the reason is a nice piece of reasoning. The naive bound says: n elements, each sifted down up to log n levels, so O(n log n). That is a valid upper bound but not tight. The tight argument counts by level. Half the nodes are leaves and sift down zero levels. A quarter are one level up and sift at most one. An eighth sift at most two. Summing n/2·0 + n/4·1 + n/8·2 + ... converges to n. Most nodes are near the bottom and barely move. Contrast with inserting n elements one at a time, which really is O(n log n) — each insert sifts up from the bottom, and the tree is at full height for most of them. This is why heapsort builds the heap in O(n) then extracts n times at O(log n) each: O(n log n) overall, dominated by the extraction, not the build.

Two pointers walk the array from different positions, letting you replace a nested loop with a single pass. The opposite-ends variant needs sorted data. For "find a pair summing to target": start at both ends, and if the sum is too small move left rightwards, if too large move right leftwards. Sortedness guarantees the discarded element could not have been part of any answer, which is what makes discarding safe. The same-direction variant uses a slow and a fast pointer. Removing duplicates in place: slow marks the write position, fast scans ahead, and you copy only when you see something new. The precondition is the important part. Opposite-ends two pointers is only correct when moving a pointer monotonically changes the quantity you are testing. On unsorted data the invariant breaks and you need a hash map instead. O(n) time, O(1) space, against O(n²) brute force.

A sliding window maintains a contiguous range and moves it across the array, updating a running state incrementally instead of recomputing it. Fixed window: the size k is given. Compute the state for the first k elements, then for each step add the entering element and subtract the leaving one. Maximum sum subarray of size k is O(n) this way instead of O(n·k). Variable window: the size is governed by a condition. Expand with the right pointer; while the condition is violated, shrink from the left. "Longest substring with at most k distinct characters" grows until a (k+1)-th character appears, then shrinks until it does not. The correctness requirement is that the state be incrementally updatable — you must be able to remove the leaving element's contribution cheaply. Sums and frequency maps qualify. A maximum does not, which is why the sliding window maximum problem needs a monotonic deque rather than a plain window.

A prefix sum array stores the cumulative total up to each index, so prefix[i] is the sum of the first i elements. It turns repeated range-sum queries from O(n) each into O(1). The sum of the range [l, r] is prefix[r+1] - prefix[l]. Build cost is O(n) once, and every query afterwards is two array reads and a subtraction. The trade is O(n) extra space, and staleness: if the underlying array changes you must rebuild. For a read-heavy workload with rare writes that is an excellent bargain. For interleaved reads and writes you want a Fenwick tree or segment tree, which give O(log n) for both. The pattern generalises well. Prefix XOR answers range-XOR queries. A 2D prefix sum answers submatrix sums in O(1) with an inclusion-exclusion of four corners. Combined with a hash map it solves "count subarrays summing to k" in a single O(n) pass.

Kadane's walks the array once, tracking the best subarray ending at the current position. The recurrence is the whole idea: at each element you either extend the previous best-ending-here, or start fresh from the current element. current = max(nums[i], current + nums[i]). Keep a separate best seen so far. The insight behind it: if the best subarray ending at the previous position is negative, carrying it forward can only hurt. So drop it and start over. That single observation collapses an O(n²) search into O(n) with O(1) space. The edge case interviewers probe is an all-negative array. Initialising the running best to 0 makes the answer wrongly 0; initialise both to nums[0] and start the loop at index 1. To return the indices rather than just the sum, record a tentative start whenever you restart, and commit it when you update the global best.

The reversal trick. Reverse the whole array, then reverse the first k elements, then reverse the rest. For [1,2,3,4,5] rotated right by 2: reverse everything to [5,4,3,2,1], reverse the first two to [4,5,3,2,1], reverse the remaining three to [4,5,1,2,3]. Done, in O(n) time and O(1) space. Why it works: reversing the whole array puts the last k elements at the front but in the wrong order, and the first n-k at the back, also reversed. The two local reversals undo that. Two details that catch people. Take k modulo n first, or a k larger than the array walks off the end. And for a right rotation the split is at k; for a left rotation it is at n-k — mixing those up is the most common bug here. The alternative is a cyclic-replacement walk following gcd(n,k) cycles, which is also O(1) space but far fiddlier to get right under pressure.

A String's backing array is final and never mutated. Any operation that looks like a change returns a new String. The reasons are security (a path or URL cannot be altered after validation), thread safety for free, and the string pool — literals can be shared safely only if nobody can modify them. Immutability also lets hashCode be cached, which is why Strings are excellent HashMap keys. The algorithmic cost is severe if you ignore it. Concatenating in a loop with + allocates and copies the entire accumulated string every iteration, making n appends O(n²). Building a 100,000-character string that way does billions of character copies. Use StringBuilder, which wraps a mutable char array and appends in amortised O(1), giving O(n) overall. The compiler rewrites simple single-expression concatenations into StringBuilder for you, but it cannot do that across loop iterations — which is exactly where it matters.

Two approaches, and the trade between them is the point. Sorting: sort both and compare. O(n log n) time, trivially correct, three lines. Good when n is small or you want obviously-right code. Counting: build a frequency map of the first string, decrement for the second, and check everything lands on zero. O(n) time. For lowercase ASCII an int[26] beats a HashMap by a wide margin — no boxing, no hashing, perfect cache locality. Check lengths first and return early; unequal lengths cannot be anagrams and it costs nothing. The follow-up is usually Unicode. int[26] silently breaks on anything outside a-z. For full Unicode you need a HashMap keyed by code point, and you must iterate code points rather than chars, since characters outside the Basic Multilingual Plane occupy two chars in Java. Mentioning that unprompted signals real-world experience.

It sorts an array of three distinct values in one pass with O(1) space — the "sort colours" problem. Three pointers partition the array into four regions: everything before low is 0, between low and mid is 1, after high is 2, and between mid and high is unclassified. Walk mid forward. If you see a 0, swap with low and advance both. If a 1, just advance mid. If a 2, swap with high and decrement high — but do not advance mid, because the value swapped in from the back has not been examined yet. That last detail is the bug everyone writes at least once. Advancing mid after a swap with high skips an unclassified element. It beats counting sort here only in that it is a single pass rather than two, but the real reason it is asked is the invariant discipline: you have to state precisely what each region means and prove every branch preserves it.

Treat the array as a linked list and use cycle detection — Floyd's tortoise and hare. The mapping: from index i, follow to index nums[i]. Because values are in [1, n] and there are n+1 of them, this traversal must eventually revisit a node, and the entry point of that cycle is the duplicate value. Phase one: advance slow by one and fast by two until they meet inside the cycle. Phase two: reset slow to the start, then advance both one step at a time; they meet at the cycle entrance, which is the answer. O(n) time, O(1) space, array untouched — which is what makes it the right answer when sorting (modifies), a hash set (O(n) space), and marking indices negative (modifies) are all ruled out by the constraints. The reason it is a good interview question is that the constraints are what force the insight. Ask which constraints are real before reaching for this.

They differ in whether elements must be contiguous and whether order matters, and confusing them produces the wrong algorithm entirely. A subarray is contiguous — a slice. [1,2,3] has subarrays [1], [2], [3], [1,2], [2,3], [1,2,3]. There are n(n+1)/2 of them, so O(n²). A subsequence keeps relative order but allows gaps. [1,3] is a subsequence of [1,2,3] but not a subarray. There are 2ⁿ of them. A subset ignores order entirely; for distinct elements there are also 2ⁿ, and for a set the terms subset and subsequence coincide in count but not in meaning. The practical consequence: subarray problems usually yield to sliding window or prefix sums in O(n). Subsequence problems usually need dynamic programming, because the exponential space of choices has to be collapsed by overlapping subproblems. Hearing "subsequence" and reaching for a sliding window is a classic wrong turn.

A hash function maps a key to a bucket index, so you jump straight to the right bucket instead of searching. O(1) is the average case and it rests on assumptions: the hash distributes keys roughly uniformly, and the load factor stays bounded so buckets hold a constant number of entries. Degradation comes from collisions. If many keys hash to the same bucket you are scanning a list, and in the pathological case where every key collides, lookup is O(n). Java 8 mitigates this by converting a bucket to a red-black tree once it exceeds eight entries, capping the worst case at O(log n) rather than O(n). The other cost is resizing. When size exceeds capacity times load factor (0.75 by default), HashMap doubles capacity and rehashes everything — an O(n) pause. Sizing the map up front avoids repeated rehashing in a hot path. Worth naming the security angle: adversarially chosen colliding keys were a real denial-of-service vector, which is part of why treeification exists.

The contract: equal objects must have equal hash codes. The converse is not required — unequal objects may share a hash code, that is just a collision. Break it by overriding equals() without hashCode() and your object becomes unfindable in a HashMap. You put it in, then look it up with an equal object, the default identity hashCode sends you to a different bucket, and the map reports absent. The entry is there; you simply never visit its bucket. The second rule is stability: an object's hash must not change while it is a key. Mutating a field used by hashCode after insertion strands the entry in the old bucket — it is in the map, contains() says no, and it is not even removable. Hence the practical rule: use immutable objects as keys. Java records generate both methods correctly from the components, which is why they make such good map keys.

Separate chaining puts colliding entries in a secondary structure at the bucket — a linked list, or a tree in Java 8+ HashMap. Open addressing keeps everything in the array itself. On collision you probe for another slot: linear probing checks the next slot, quadratic probing steps by increasing squares, double hashing uses a second hash for the stride. Chaining tolerates load factors above 1 and makes deletion trivial — unlink the node. It costs a pointer per entry and scatters entries across the heap, hurting cache locality. Open addressing is cache-friendly because probing walks contiguous memory, and it has no per-entry pointer overhead. But it degrades sharply as the load factor approaches 1, and deletion is genuinely awkward: you cannot just empty a slot or you break probe chains that pass through it, so you need tombstones. Java's HashMap chains. Python's dict and many high-performance C++ maps use open addressing, which is largely a cache-locality bet.

Keep a hash set of what you have already seen. For each element x, check whether target - x is in the set; if so you have your pair, otherwise add x and continue. O(n) time, O(n) space, one pass. The key move is that you look for the complement rather than the value — the answer is defined by what is missing, not what is present. Order matters. Check before inserting, or a single element equal to half the target will match itself and report a false pair. If you need the indices rather than a yes/no, use a HashMap from value to index. If duplicates matter — counting all pairs rather than finding one — use a frequency map and handle the x == target-x case separately, where the count is c·(c-1)/2 rather than c₁·c₂. The two-pointer alternative is O(1) space but needs sorted input, so it is O(n log n) overall unless the array arrives sorted.

When you need order, or bounded worst-case behaviour. HashMap gives O(1) average operations and no ordering guarantee at all — iteration order can change across runs and versions, and relying on it is a bug waiting to surface. TreeMap is a red-black tree with O(log n) operations and keys held in sorted order. That buys you range queries: firstKey, lastKey, headMap, tailMap, subMap, floorKey, ceilingKey. "All events between two timestamps" is one call on a TreeMap and a full scan on a HashMap. TreeMap also has a genuine O(log n) worst case rather than a degraded one, which matters when keys can be adversarial. LinkedHashMap sits between them: O(1) like HashMap but preserving insertion order, or access order — which is what makes it a two-line LRU cache when you override removeEldestEntry. Default to HashMap; move to TreeMap the moment you need ordering or ranges.

Build a canonical key that all anagrams of a word share, and group by it in a hash map. The simple key is the sorted characters: "eat", "tea" and "ate" all become "aet". Cost is O(n · k log k) for n words of length k. The faster key is a character count signature — a 26-length count rendered as a string like "1#0#0#...". That is O(n · k), dropping the log factor, and it wins when words are long. Either way the grouping itself is a single pass into a Map<String, List<String>>, using computeIfAbsent to avoid the null check. Which to pick depends on k. For short words the sort is faster in practice despite the worse bound, because sorting 5 characters is trivial and building a 26-slot signature string is not free. That trade — better asymptotics losing to smaller constants at realistic input sizes — is worth saying out loud.

Put everything in a hash set, then for each element only start counting if it is the beginning of a run. The trick is that guard. For element x, check whether x-1 is in the set; if it is, x is in the middle of some sequence and will be counted when its run's start is reached, so skip it. If x-1 is absent, x starts a run — walk x+1, x+2 and so on, counting. Without the guard this is O(n²): every element walks its whole sequence. With it, each element is visited at most twice overall — once by the outer loop, once by the inner walk of its own run — so the total is O(n). That amortised argument is the entire point of the question. Candidates often write the inner walk correctly and cannot explain why the nested loop is not quadratic. Sorting gives O(n log n) and is a perfectly reasonable answer to state first before improving it.

A variable sliding window plus a map from character to its last seen index. Expand the right pointer one character at a time. When you hit a character already inside the window, jump the left pointer to one past that character's previous position. Track the best window length as you go. The subtlety is that jump. Take the maximum of the current left and the stored index plus one — never move left backwards. Without that guard, a repeat whose previous occurrence is already outside the window drags left back and corrupts the count. For "abba" the naive version gets it wrong. O(n) time with each pointer moving forward only, and O(min(n, alphabet)) space. The alternative is shrinking left one step at a time while the duplicate remains. Also O(n) amortised and easier to argue correct — worth offering as the simpler version before optimising to the jump.

Sort the array, then fix each element and run a two-pointer scan over the remainder looking for the complement. Sorting costs O(n log n) but buys two things. It makes the opposite-ends two-pointer valid, turning the inner search from O(n²) into O(n) and the whole algorithm into O(n²). And it puts duplicates adjacent, which is what makes deduplication tractable. Deduplication is where most attempts fail. Skip a fixed element if it equals the previous one, and after recording a triplet advance both pointers past their duplicates. Otherwise [0,0,0,0] emits the same triplet repeatedly. One useful early exit: once the fixed element is positive, no triplet of sorted values beyond it can sum to zero, so break. The hash-set alternative avoids sorting but needs a set of triplets to dedupe, which costs more space and is fiddlier. Sorting is the cleaner answer.

Water above any position is bounded by the shorter of the tallest bar to its left and the tallest to its right, minus its own height. The O(n) space version precomputes leftMax and rightMax arrays, then sums min(leftMax[i], rightMax[i]) - height[i] across the array. The O(1) space version uses two pointers and one observation: if leftMax is currently less than rightMax, then whatever lies between cannot change the fact that the left side is the binding constraint for the left pointer. So you can safely settle the left position now and advance. Symmetrically on the right. That is the insight the question exists to test — you do not need to know the exact rightMax, only that it is at least as large as leftMax. The monotonic stack solution also works, accumulating water in horizontal layers, but the two-pointer version is shorter and easier to defend.

A stack kept deliberately sorted — increasing or decreasing — by popping anything that would break the order before pushing. It answers "next greater element" style questions in O(n). Walk the array; while the stack top is smaller than the current element, pop it and record the current element as its next greater. Then push the current index. Each element is pushed once and popped at most once, so despite the inner while loop the total work is O(n). That amortised argument is what interviewers are checking. The family is large: next greater or smaller element, daily temperatures, largest rectangle in a histogram, trapping rain water, and the stock span problem all reduce to it. Store indices rather than values on the stack. You almost always end up needing the distance between positions, and recovering an index from a value is impossible with duplicates.

A variable sliding window with a frequency map and a counter of how many required characters are currently satisfied. Expand right, decrementing the needed count for each character. When a character's requirement reaches exactly zero, increment a "formed" counter. Once formed equals the number of distinct required characters, the window is valid — record it if it is the smallest so far, then shrink from the left while it stays valid. Two details decide correctness. Track distinct requirements satisfied, not total characters, or duplicates in the pattern break the count. And when shrinking, only decrement formed when a character drops strictly below its requirement — going from three copies to two when you need two is still satisfied. O(n + m) time; each pointer traverses once. O(alphabet) space. It is a hard problem mostly because of bookkeeping rather than insight, so narrating the invariant as you code it matters more here than usual.

Fill from the back, not the front. The forward approach forces you to shift elements to make room, which is O(n·m). Writing backwards means the destination cells you overwrite are ones you have already consumed or were empty to begin with. Start three pointers: one at the last real element of the first array, one at the end of the second, one at the very end of the first array's capacity. Compare and write the larger to the write pointer, stepping backwards. When the first array runs out you must keep draining the second. When the second runs out you can stop — the remaining elements of the first are already in place. That asymmetry is the detail interviewers watch for: only one of the two leftover loops is actually necessary. O(n + m) time, O(1) extra space.

Two pointers from both ends, skipping anything that is not alphanumeric, comparing case-insensitively. Advance left while the character is not alphanumeric, retreat right the same way, then compare the two normalised characters. If they differ, return false. Continue until the pointers cross. The reason this beats "strip and reverse" is space. Building a cleaned copy and comparing to its reverse is O(n) extra memory; the two-pointer version is O(1). Boundary safety is the common bug: the inner skip loops must also check that left is still less than right, or a string of only punctuation walks off the end. The follow-up is usually Unicode and locale. Character.toLowerCase is not locale-safe for every alphabet — Turkish dotted and dotless i is the standard counterexample. Naming that shows you have thought past the ASCII happy path.

Iteratively: walk the list with three references — previous, current, and next. Save current.next before you overwrite it, point current.next at previous, then shift previous and current forward. When current is null, previous is the new head. Saving next first is the whole trick. Overwrite current.next before saving it and you have severed the rest of the list and cannot recover it. Recursively: recurse to the end to get the new head, then on the way back set current.next.next = current and current.next = null. The second assignment matters — skip it and the last two nodes point at each other, giving you a cycle. Iterative is O(1) space and is what you should write in production. Recursive is O(n) stack and will overflow on a long list, but interviewers ask for it to see whether you can reason about what happens on the unwind.

Two pointers move at different speeds — slow one step, fast two. If there is a cycle, fast laps slow and they meet; if fast reaches null, there is no cycle. They must meet because once both are inside the loop the gap between them shrinks by exactly one each step, so it eventually reaches zero. It cannot be jumped over. Finding the entry point is the second phase, and the maths is worth knowing. Let the distance from head to the cycle start be a, and from the cycle start to the meeting point be b. When they meet, slow has walked a+b and fast has walked twice that. Working through it, the remaining distance from the meeting point back round to the cycle start equals a. So reset one pointer to the head, advance both one step at a time, and they meet exactly at the cycle entrance. O(n) time, O(1) space — beating the hash-set approach on memory.

Because it removes the special case where the head itself changes. Without one, every operation that might modify the first node needs a separate branch: deleting the head, inserting before the head, merging when one list is empty. That branch is where the bugs live. With a dummy node sitting before the real head, the first node is no longer special — it has a predecessor like everything else. You do the uniform thing throughout and return dummy.next at the end. It is the standard opening for merging two sorted lists, removing all nodes with a given value, removing the nth node from the end, and partitioning a list. Cost is one stack-allocated node and one extra line. The payoff is that the loop body handles every position identically, which is exactly what you want when writing under time pressure.

Slow and fast pointers. Advance slow one node and fast two; when fast reaches the end, slow is at the middle. The alternative is counting the length then walking half of it, which is two passes. The two-pointer version is one pass and reads better. The question to ask is which middle you want for an even-length list. Loop while fast != null && fast.next != null and slow lands on the second of the two middles. Loop while fast.next != null && fast.next.next != null and it lands on the first. For splitting a list in merge sort you want the first middle, or the recursion never shrinks and you get infinite recursion on a two-node list. That infinite-recursion trap is the real reason this gets asked — it is where the choice actually bites. Order the null checks as written; reversing them dereferences null on an even-length list.

A dummy head plus a tail pointer. Compare the two list heads, append the smaller to the tail, advance that list, and repeat. When one list runs out, append the remainder of the other wholesale — no need to walk it node by node, since it is already sorted and already linked. That single line replaces a loop. O(n + m) time, O(1) extra space, because you relink existing nodes rather than allocating new ones. That is the advantage over merging arrays, where you need a destination buffer. The recursive version is elegantly short — return the smaller head with its next set to the merge of the rest — but it uses O(n + m) stack and will overflow on long lists. This is the merge step of merge sort on lists, which is why linked-list merge sort is O(1) auxiliary space beyond the recursion, unlike the array version.

Two pointers separated by a gap of n. Advance the first pointer n steps ahead, then move both together until the first reaches the end. The second is now sitting at the node before the one to remove. The gap is the whole idea: maintaining a fixed distance means when the leader hits the end, the follower is exactly n from it, without ever knowing the length. Use a dummy head. Removing the first node is otherwise a special case, and n equal to the list length is exactly that case. Off-by-one is the standard bug. To delete a node you must stop at its predecessor, so start the follower at the dummy rather than the head, and advance the leader n+1 times from the dummy — or n times from the head with the follower at the dummy. Validate n against the length if the input is untrusted; otherwise the leader walks off into a null dereference.

Walk both, and when one runs out, jump it to the head of the other. Both pointers then travel exactly a+b+c and meet at the intersection. The reason it works: if the lists have lengths a+c and b+c where c is the shared tail, then a pointer that walks the first list then the second covers a+c+b, and one that walks the second then the first covers b+c+a. Equal distances, so they arrive at the junction together. If there is no intersection, both hit null at the same time and you return null — the same loop handles it with no special case. O(n + m) time, O(1) space. The alternatives — a hash set of visited nodes (O(n) space) or measuring both lengths and advancing the longer by the difference (two extra passes) — both work and are worth mentioning as the obvious first answer. Compare node identity, not values. Two nodes holding the same number are not the intersection.

Because the two algorithms depend on opposite properties. Quicksort wants random access to partition efficiently around a pivot. On a linked list you cannot index, so partitioning means repeated traversal and the constant factor collapses. Quicksort's cache advantage on arrays also vanishes, since list nodes are scattered anyway. Merge sort only ever walks sequentially, which is exactly what a linked list supports well. And crucially, merging lists needs no auxiliary buffer — you relink existing nodes. On arrays merge sort needs O(n) extra space, which is its main drawback; on lists that drawback disappears. So list merge sort is O(n log n) time with O(log n) space for the recursion, or O(1) with a bottom-up iterative merge. It is also stable, which matters when sorting records by a secondary key. This is why Java's Collections.sort() converts to an array and uses TimSort, while a hand-written list sort is almost always merge sort.

Keep an input stack and an output stack. Push always goes to the input stack. Pop takes from the output stack, and when the output stack is empty, pour the entire input stack into it first. Pouring reverses the order, which converts LIFO into FIFO. That is the entire mechanism. The cost analysis is the interesting part. A single pop can be O(n) when it triggers a transfer, but each element is moved from input to output exactly once in its lifetime, so amortised cost per operation is O(1). The critical rule: only transfer when the output stack is empty. Transferring while it still holds elements interleaves old and new items and destroys the ordering. The mirror question — a stack from two queues — is worse: one of push or pop is unavoidably O(n) with no amortised escape, because a queue cannot reverse itself the way a stack can.

Carry the minimum alongside each element rather than computing it on demand. The simple version uses a second stack of minimums. On push, push the smaller of the new value and the current top of the min stack. On pop, pop both. The top of the min stack is always the minimum of everything currently in the main stack. That works because a stack only ever removes the most recent element, so the minimum history is itself a stack — you can always restore the previous minimum by popping. The space-optimised variant stores pairs of value and running minimum in a single stack, or encodes the difference from the current minimum to avoid a second structure entirely. O(1) for push, pop, top and getMin; O(n) space. The follow-up is often "now do it for a queue", which is genuinely harder — a queue removes from the far end, so the min history is not a stack, and you need a monotonic deque instead.

Push opening brackets onto a stack; on a closing bracket, pop and check it matches. Three failure modes, and missing any one of them is the usual bug. A closing bracket with an empty stack means one too many closers. A closing bracket that does not match the popped opener means a mismatch. And a non-empty stack at the end means unclosed openers. A map from closing to opening bracket keeps the matching logic to one comparison instead of a chain of conditionals. O(n) time, O(n) space in the worst case of all openers. The reason a stack is exactly right here: nesting is last-opened-first-closed, which is the definition of LIFO. Any correctly nested structure — HTML tags, JSON, expression parsing — has the same shape, which is why this generalises well beyond brackets. A counter only works for a single bracket type; the moment there are three types you need the stack to know what you are closing.

A double-ended queue — insert and remove at both ends in O(1). It subsumes both a stack and a queue, which is why Java's documentation recommends ArrayDeque over the legacy Stack class. Stack extends Vector and is synchronised on every operation, so it is slower and its iteration order is bottom-to-top, which surprises people. ArrayDeque is a circular buffer: no per-node allocation, excellent cache locality, and no capacity limit. It refuses null elements, which is deliberate — null is the sentinel returned by poll() on an empty deque. The algorithmic use is the sliding window maximum, where you keep a monotonic deque of indices: push at the back, evict from the back anything smaller than the incoming element, and evict from the front anything that has fallen out of the window. The front is then always the window maximum, giving O(n) overall. That need to evict from both ends is precisely what a plain stack or queue cannot do.

Walk left to right with a stack. Push operands. On an operator, pop two operands, apply, push the result. At the end the stack holds one value — the answer. Operand order matters for non-commutative operators. The first pop is the right operand, the second is the left. Getting that backwards passes tests on addition and fails on subtraction and division, which is exactly the bug interviewers look for. O(n) time, O(n) space. The reason postfix exists: it needs no parentheses and no precedence rules, because the order of operations is encoded in the position of the operators. That is why compilers and calculators convert infix to postfix — the shunting-yard algorithm — before evaluating. Worth mentioning the practical edge cases: division by zero, integer overflow, and unary minus, which is ambiguous with binary minus unless the tokeniser distinguishes them.

A fixed-size array where the head and tail wrap around using modulo arithmetic, so space freed at the front is reused instead of abandoned. A naive array queue moves the head forward on every dequeue and eventually reports "full" while most of the array sits empty. Shifting everything back down to fix that is O(n) per operation. The circular version wraps instead: index = (index + 1) % capacity. The classic ambiguity is that head == tail means both empty and full. Two standard fixes: keep an explicit size counter, or deliberately waste one slot so full means (tail + 1) % capacity == head. O(1) enqueue and dequeue, fixed memory, no allocation after construction. That last property is why it is everywhere in systems work — ring buffers for I/O, audio, logging, and producer-consumer pipelines all want bounded memory and predictable latency with no garbage collection pressure.

A monotonic increasing stack of indices, in one pass. For each bar, while the stack top is taller than the current bar, pop it and compute the rectangle where that popped bar is the limiting height. Its width runs from the element below it on the stack up to the current index. The insight: a bar's rectangle extends left and right until it meets something shorter. The stack is exactly the set of bars whose right boundary has not been found yet, and the current bar is the right boundary for everything taller than it. Width is where people slip. After popping, the width is current index minus the new stack top minus one — not simply the number of pops. Using a sentinel of -1 at the bottom of the stack removes the empty-stack special case. Append a zero-height bar at the end to flush anything still on the stack. O(n), since each bar is pushed and popped once. It generalises to maximal rectangle in a binary matrix by treating each row as a histogram.

Depth-first comes in three flavours defined by when you visit the node relative to its children. Inorder — left, node, right. On a binary search tree this emits values in sorted order, which is why it is the traversal for anything order-dependent. Preorder — node, left, right. Visits the root first, so it is what you use to serialise or copy a tree: the output can be replayed to rebuild the same structure. Postorder — left, right, node. Children before parents, so it is what you use to delete a tree, compute subtree sizes or heights, or evaluate an expression tree. Level-order (BFS) uses a queue instead of recursion and visits by depth, which is what you want for shortest path in an unweighted tree or printing level by level. The mapping matters: choosing postorder for a height calculation is not a style preference, it is a requirement, because you cannot compute a node's height before its children's.

Pass down a valid range for each node rather than comparing to its immediate children. The naive check — node.left.val < node.val < node.right.val at every node — is wrong, and this is the entire point of the question. A tree can satisfy it locally and still violate the BST property globally: a node deep in the left subtree can exceed the root, and a purely local check never notices. The correct version recurses with a low and high bound. Going left tightens the upper bound to the current value; going right tightens the lower bound. A node outside its inherited range fails. Use Long bounds, or nullable Integers, so a node holding Integer.MIN_VALUE or MAX_VALUE does not falsely fail at the boundary. The alternative is an inorder traversal checking that values come out strictly increasing, tracking only the previous value. Equally valid, O(n) time either way, and often easier to explain.

Balanced means the height stays O(log n) rather than degrading toward O(n). It matters because every BST operation costs O(height). Insert sorted data into an unbalanced BST and you get a linked list — every search walks all n nodes, and the structure you chose for its log n guarantee now performs worse than an array. Different structures define balance differently. AVL trees require the height difference between siblings to be at most one, giving stricter balance and faster lookups. Red-black trees allow the longest path to be up to twice the shortest, which is looser but needs fewer rotations on write. That is the trade: AVL for read-heavy workloads, red-black for write-heavy. Java's TreeMap and HashMap treeification both use red-black. B-trees generalise the idea for disk: high branching factor to minimise the number of node reads, which is why databases index with them rather than binary trees.

Recurse and let the answer bubble up. At each node: if it is null or matches either target, return it. Otherwise recurse both sides. If both sides return non-null, this node is the split point — return it. If only one side returns non-null, pass that up: either the LCA is deeper on that side, or that is the one target found so far. O(n) time, O(h) space for the stack. On a BST you can do much better by exploiting ordering. Walk from the root; if both targets are smaller go left, if both larger go right, and the first node where they diverge — or which equals one of them — is the LCA. O(h), and iterative with O(1) space. The assumption worth surfacing: this returns a node even if one target is absent from the tree. If existence is not guaranteed you need a second pass to confirm, or a variant that counts matches found.

Preorder with explicit null markers is the standard answer. Write the node value, then recurse left, then right, emitting a sentinel such as "#" for every null. The nulls are what make it unambiguous — without them, a preorder sequence does not determine a unique tree. Deserialising mirrors it: read tokens in order, and on a sentinel return null, otherwise build the node and recursively fill left then right. The recursion consumes exactly the right tokens because the structure is encoded in the null positions. Level-order with nulls works too and is what LeetCode uses for display, but it needs a queue on both sides and produces trailing nulls you must trim. The classic wrong answer is inorder plus preorder without nulls. That does reconstruct a tree uniquely — but only when all values are distinct, so it silently fails on duplicates. O(n) both ways.

A prefix tree, where each edge is a character and a path from the root spells a prefix. Nodes carry a flag marking the end of a real word. Lookup is O(k) in the key length, independent of how many words are stored — a hash map is also roughly O(k) once you count hashing the string, so raw lookup is not the reason to choose one. The reason is prefix operations. "All words starting with pre" is a single subtree walk in a trie and a full scan in a hash map. Autocomplete, spell check, IP routing tables and word games all want exactly that. A trie also shares storage across common prefixes, which saves memory on dense dictionaries. Sparse ones go the other way — a node per character with 26 child slots is heavy, and a HashMap of children per node trades speed for space. If you never query by prefix, use a hash set. The trie earns its cost only when prefixes are the access pattern.

The diameter is the longest path between any two nodes, and it need not pass through the root — that is what makes it more than a height calculation. The trick is to compute height and diameter in the same postorder pass. For each node, recursively get the left and right heights. The longest path through this node is leftHeight + rightHeight. Update a global maximum with that, then return 1 + max(left, right) as this node's height to the parent. So the function returns height but has the side effect of tracking the best diameter seen. Trying to return both directly, or calling a separate height() inside the recursion, gives O(n²) because heights get recomputed at every level. O(n) time, O(h) stack. Be explicit about units — diameter measured in edges is leftHeight + rightHeight; in nodes it is one more. Interviewers do ask which you are returning.

BFS with a queue, processing one full level per outer iteration. The technique that makes levels explicit: at the top of each outer loop, record the current queue size. That count is exactly the number of nodes on this level. Dequeue precisely that many, enqueueing their children as you go. When the inner loop ends, the queue holds exactly the next level. Without that size snapshot you can still traverse, but you cannot tell where one level ends and the next begins. O(n) time; O(w) space where w is the maximum width — which for a complete tree is about n/2 at the bottom level, so BFS can use substantially more memory than DFS on wide trees. Variants fall out naturally: zigzag order by reversing alternate levels, right-side view by taking the last node of each level, and maximum width by tracking indices rather than counts.

They enforce different invariants and answer different questions. A heap enforces only a parent-child relationship: every parent is smaller than its children in a min-heap. Siblings are unordered, so the structure tells you nothing about global ordering beyond the root. That weaker invariant is cheap to maintain and gives O(1) access to the minimum. A BST enforces a global ordering: everything left is smaller, everything right is larger. That supports search for an arbitrary value in O(log n), ordered traversal, and range queries — none of which a heap can do. Finding an arbitrary value in a heap is O(n). A heap is a complete tree, so it packs into an array with no pointers: children of index i are at 2i+1 and 2i+2. A BST needs real nodes and rebalancing. Use a heap when you only ever need the extreme element — priority queues, scheduling, top-k. Use a BST when you need ordering or search.

Preorder gives you the root; inorder tells you how the remainder splits. Take the first preorder element as the root, find it in the inorder array, and everything to its left is the left subtree while everything to its right is the right subtree. The sizes of those halves tell you how to slice the preorder array. Recurse on both. The naive version scans the inorder array to locate the root each time, giving O(n²). Precompute a value-to-index hash map and it drops to O(n). Track ranges with indices rather than copying subarrays, or you add O(n) allocation per level. The precondition worth stating: values must be distinct, otherwise the split point is ambiguous and the tree is not uniquely determined. Inorder plus postorder works the same way, taking the root from the end. Preorder plus postorder does not uniquely determine a tree at all unless it is full — a good detail to raise.

Identical is a straightforward simultaneous recursion: both null means true, one null means false, differing values means false, otherwise recurse on both left and right pairs. O(n). Subtree is the harder variant. For each node of the larger tree, check whether the tree rooted there is identical to the candidate. That is O(n·m) in the worst case, since the identity check can run at every node. The efficient approach serialises both trees with null markers and asks whether one string contains the other. With a linear-time substring search such as KMP that is O(n + m). The null markers are essential. Without them, serialisation is ambiguous and unrelated trees produce matching substrings — the classic false positive where a subtree "matches" because its values happen to appear consecutively. Delimiters between values matter too, or the value 12 matches inside 123.

A heap is a complete binary tree — every level full except possibly the last, which fills left to right. That completeness is what allows an array representation with no gaps. With zero-based indexing, the children of index i sit at 2i+1 and 2i+2, and the parent is at (i-1)/2. Navigation becomes arithmetic, so there are no child or parent pointers at all. The savings are real: no per-node allocation, no pointer chasing, and excellent cache locality since a parent and its children are close together in memory. Insert appends at the end and sifts up; extract-min swaps the root with the last element, shrinks the array, and sifts the new root down. Both are O(log n) because the height of a complete tree is log n. This is exactly why heapsort can sort in place with O(1) extra space, unlike merge sort.

Keep a min-heap of size k. For each incoming element, push it; if the heap exceeds size k, pop the minimum. The counterintuitive part is using a min-heap to track maxima. The heap holds the k best seen so far, and its root is the weakest of those — so it is exactly the element to evict when a better one arrives. Comparing against the root also gives an O(1) rejection test for elements that cannot qualify. O(n log k) time and O(k) space, which is what makes it viable on a stream where n is unbounded or unknown. Sorting everything is O(n log n) and requires holding all n elements, so it is strictly worse here. If all data fits in memory and you want a single answer rather than a running one, Quickselect gives O(n) average time — better asymptotically, but it needs random access and does not work incrementally.

Two heaps facing each other. A max-heap holds the smaller half, a min-heap holds the larger half. Invariants: every element in the max-heap is at most every element in the min-heap, and their sizes differ by at most one. The median is then the root of the larger heap, or the average of the two roots when sizes are equal. On insert, push to one heap based on comparison with its root, then rebalance by moving a root across if the sizes drift by more than one. A common simplification is to always push to the max-heap, immediately move its root to the min-heap, then move back if the min-heap has grown too large — fewer branches, harder to get wrong. O(log n) per insertion, O(1) to read the median, O(n) space. The alternative, keeping a sorted list, is O(n) per insert because of the shift. A balanced BST with subtree counts also works and generalises to arbitrary percentiles, which two heaps cannot do.

A min-heap holding one node from each list. Pop the smallest, append it to the output, and push that node's successor from the same list. The heap holds at most k elements, so each of the n total elements costs O(log k) to insert and remove: O(n log k) overall, O(k) space. The naive alternative — scanning all k list heads each time — is O(n·k). The heap replaces that linear scan with a logarithmic one, which is the entire improvement. Divide and conquer gives the same O(n log k) by merging lists pairwise in rounds, and it avoids the heap entirely. Often simpler to write correctly and it parallelises naturally. Concatenating everything and sorting is O(N log N) where N is the total, which is worse and throws away the sortedness you were handed. This is the merge step behind external sorting, where k sorted runs on disk are combined in one pass.

A priority queue is an abstract data type — a contract saying you can insert elements and remove the highest-priority one. A heap is a concrete data structure that implements it, and the usual choice. Other implementations exist and have different trade-offs. A sorted array gives O(1) peek but O(n) insert. An unsorted array gives O(1) insert but O(n) extract. A balanced BST gives O(log n) for both plus ordered traversal, which a heap cannot provide. Java's PriorityQueue is a binary min-heap by default; pass a comparator or reverse order for a max-heap. Two behaviours surprise people: iteration order is heap order, not sorted order, and it is unbounded but not thread-safe — PriorityBlockingQueue is the concurrent version. For Dijkstra at very large scale a Fibonacci heap gives amortised O(1) decrease-key and improves the theoretical bound, but its constants are bad enough that binary heaps win in practice.

BFS explores level by level with a queue; DFS goes as deep as possible with a stack or recursion. Use BFS when distance matters. It finds the shortest path in an unweighted graph, because it reaches every node by the fewest edges before ever considering longer routes. Also for level-order processing and for finding the nearest anything. Use DFS when you need to explore structure: cycle detection, topological sort, connected components, path existence, and anything naturally recursive like backtracking. Both are O(V + E). The difference is memory. BFS holds an entire frontier, which on a wide graph can be enormous. DFS holds one path, so it is O(depth) — but on a deep graph that overflows the stack, which is when you convert it to an explicit stack. The rule of thumb: wide and shallow favours DFS on memory, deep and narrow favours BFS. And if the question says "shortest" with unweighted edges, it is BFS, full stop.

For a directed graph, DFS with three colours: unvisited, in-progress, and finished. A back edge to a node currently in progress means a cycle. Tracking only "visited" is the classic mistake. Reaching an already-visited node in a directed graph is perfectly normal — it may simply be a node you finished exploring down another branch. Only an edge back into the current recursion stack is a cycle. For an undirected graph, plain visited tracking does work, but you must skip the edge you arrived on. Otherwise every edge looks like a two-node cycle back to the parent. So the two cases need genuinely different bookkeeping: directed needs the recursion stack, undirected needs the parent. Kahn's algorithm gives an alternative for directed graphs: run a topological sort and if fewer than V nodes come out, the leftovers form a cycle. Union-Find is the neat alternative for undirected — an edge whose endpoints already share a root closes a cycle.

A linear ordering of a directed acyclic graph where every edge points forward — every prerequisite appears before what depends on it. Kahn's algorithm is the BFS version. Compute in-degrees, enqueue every node with in-degree zero, and repeatedly dequeue a node, append it to the order, and decrement its neighbours' in-degrees, enqueueing any that hit zero. If you emit fewer than V nodes, the graph has a cycle. The DFS version runs a depth-first search and pushes each node onto a stack after all its descendants are finished. Popping the stack gives the topological order, because a node is only finished once everything it points to is already recorded. Both are O(V + E). Kahn's detects cycles naturally and can produce a lexicographically smallest order with a priority queue; DFS is shorter to write. The order is generally not unique. Build systems, task schedulers, course prerequisites and dependency resolution all reduce to this.

A greedy shortest-path search using a priority queue. Repeatedly extract the unvisited node with the smallest known distance, finalise it, and relax its outgoing edges. The correctness argument rests on one assumption: once a node is extracted with the minimum tentative distance, no shorter path to it can exist, because any alternative route would have to pass through a node that is already at least as far away, and adding non-negative edges can only increase the total. Negative edges break exactly that step. A longer-looking route can later become shorter via a negative edge, but Dijkstra has already finalised the node and never revisits it — producing a confidently wrong answer rather than an error, which is the dangerous part. Use Bellman-Ford for negative weights: O(V·E), and it detects negative cycles, where "shortest path" stops being meaningful at all. With a binary heap Dijkstra is O((V + E) log V).

A disjoint-set structure supporting two operations: find which set an element belongs to, and union two sets. Each set is a tree, identified by its root. Two optimisations do the work. Path compression flattens the tree during find by pointing every node visited directly at the root. Union by rank or size always attaches the smaller tree under the larger, keeping trees shallow. Together they give amortised O(α(n)) per operation, where α is the inverse Ackermann function — under 5 for any input that fits in the universe. Effectively constant, though not literally. Either optimisation alone gives O(log n); it is the combination that collapses it. It is the natural fit for dynamic connectivity — Kruskal's minimum spanning tree, detecting cycles in an undirected graph, counting connected components, and account-merging problems. The limitation worth stating: it cannot split sets. Union-Find is one-directional, so problems requiring disconnection need a different approach.

Adjacency list: an array or map from each vertex to a list of its neighbours. Space is O(V + E). Iterating a vertex's neighbours is proportional to its degree, which is what BFS and DFS do constantly. Adjacency matrix: a V×V grid where cell [i][j] indicates an edge. Space is O(V²) regardless of edge count. Checking whether a specific edge exists is O(1); listing a vertex's neighbours is O(V) because you scan a whole row. Choose by density. Real graphs — road networks, social graphs, dependency trees — are sparse, where E is far closer to V than V². A matrix on a million-vertex sparse graph is a terabyte of mostly zeros, so the list wins overwhelmingly. The matrix earns its place on dense graphs, when you need O(1) edge lookup, or when the algorithm is matrix-shaped anyway — Floyd-Warshall all-pairs shortest paths being the standard example. Edge lists are a third option, and they are what Kruskal's wants since it sorts edges directly.

Treat the grid as an implicit graph where each land cell connects to its four neighbours. Scan every cell; when you find unvisited land, increment the count and flood-fill the entire connected region so it is never counted again. The flood fill can be DFS or BFS — either works, and the count increments once per region, not once per cell. O(rows × cols), since every cell is visited a constant number of times. The practical choice is how to mark visited. A separate boolean grid is O(mn) extra space and non-destructive. Overwriting land with water mutates the input but uses O(1) extra space — always ask whether mutation is acceptable before doing it. On a large grid, recursive DFS can overflow the stack: a 1000×1000 all-land grid means a million-deep recursion. BFS with an explicit queue avoids that, which is the answer worth giving unprompted. Union-Find is a third approach and is the one to reach for if the follow-up asks for islands after each added cell.

Both build a minimum spanning tree greedily, but they grow it differently. Prim's grows a single connected tree. Start anywhere, and repeatedly add the cheapest edge connecting the tree to a vertex outside it, using a priority queue. O(E log V) with a binary heap. Kruskal's sorts all edges by weight and adds each one unless it would form a cycle, using Union-Find to test that. The intermediate state is a forest of disconnected components that merge over time. O(E log E), dominated by the sort. Density decides. Prim's is better on dense graphs, where E approaches V² and sorting all edges is expensive. Kruskal's is better on sparse graphs and is trivially parallel to sort. Kruskal's also handles disconnected graphs gracefully, producing a minimum spanning forest, whereas Prim's only ever covers the component it started in. Both are correct because of the cut property: the lightest edge crossing any cut is in some MST.

DFS or BFS with a hash map from original node to its copy, and the map doubles as the visited set. The order of operations is what makes cycles safe. Create the copy and put it in the map before recursing into neighbours. When the traversal comes back around to an already-copied node, the map returns the existing copy instead of recursing forever. Invert those two steps and a cycle causes infinite recursion — which is precisely the bug the question is testing for. O(V + E) time and space. The map is doing double duty deliberately: it answers "have I seen this?" and "what is its copy?" with the same lookup. A separate visited set would work but is redundant. The same pattern generalises to deep-copying any object graph with shared or circular references, which is exactly how serialisation libraries handle object identity.

A graph whose vertices can be split into two sets with every edge crossing between them — no edge inside a set. Test by two-colouring. Run BFS or DFS, colouring each node the opposite of its parent. If you ever reach an already-coloured node holding the same colour as the current one, the graph is not bipartite. The equivalent characterisation is that a graph is bipartite exactly when it contains no odd-length cycle. The two-colouring fails precisely when an odd cycle forces a node to take both colours. O(V + E). The detail people miss: the graph may be disconnected, so you must restart the colouring from every uncoloured vertex rather than assuming one traversal covers everything. It matters in practice for matching problems — assigning jobs to workers, students to schools — where bipartite structure unlocks maximum-matching algorithms like Hopcroft-Karp.

A* is Dijkstra plus a heuristic estimate of the remaining distance to the goal. Dijkstra prioritises by g(n), the known cost from the start, so it expands outward in all directions equally. A* prioritises by f(n) = g(n) + h(n), where h estimates the cost from n to the goal, which biases the search toward the target. The correctness condition is that h must be admissible — never overestimating the true remaining cost. An admissible heuristic guarantees A* finds the optimal path. Overestimate and it becomes fast but potentially wrong. With h always zero, A* degenerates exactly into Dijkstra. With a perfect heuristic it walks straight to the goal. Straight-line distance is the standard admissible heuristic for maps, since actual roads can only be longer. The practical difference is nodes expanded, not asymptotic complexity. On a game map or road network A* can explore a small fraction of what Dijkstra does, which is why pathfinding uses it.

Quicksort partitions around a pivot and recurses on both sides. O(n log n) average, O(n²) worst case when pivots are consistently terrible. In place, so O(log n) space for the recursion. Not stable. Merge sort splits in half, sorts both, and merges. O(n log n) guaranteed in every case. Needs O(n) auxiliary space for arrays. Stable. Quicksort is usually faster in practice despite the worse bound, because its inner loop is tight and it has excellent cache locality — it works on contiguous regions that shrink. The worst case is avoidable with a randomised or median-of-three pivot, which makes adversarial input effectively impossible. Choose merge sort when stability matters, when you need a guaranteed bound, or when sorting linked lists where the O(n) space penalty disappears. Choose quicksort for in-memory arrays of primitives. That is exactly what Java does: Arrays.sort() uses dual-pivot quicksort for primitives, and TimSort — a merge sort variant — for objects, where stability is contractual.

A stable sort preserves the relative order of elements that compare equal. If two records both have priority 3 and A came before B in the input, A still comes before B in the output. It matters when you sort by multiple keys in sequence. Sort employees by name, then stably by department, and within each department they remain alphabetical. Without stability the first sort is destroyed by the second, and you must instead write one comparator handling all keys. It also matters whenever elements carry data outside the comparison key — which is most real records. For primitives stability is meaningless, since equal values are indistinguishable. Merge sort, insertion sort and TimSort are stable. Quicksort and heapsort are not, because they swap distant elements. This is exactly why Java uses dual-pivot quicksort for primitive arrays and TimSort for object arrays: stability is unobservable for the former and contractually guaranteed for the latter.

The n log n bound applies only to comparison-based sorts. It comes from a decision-tree argument: n! possible orderings need at least log(n!) ≈ n log n comparisons to distinguish. Sorts that do not compare elements escape it by exploiting structure in the keys. Counting sort is O(n + k) for integers in a known range k — count occurrences, then write out. Excellent when k is small relative to n, catastrophic when k is huge, since it allocates a k-sized array. Radix sort is O(d·(n + k)) for d-digit keys, sorting digit by digit with a stable counting sort at each pass. It works on fixed-width integers and strings. Bucket sort is O(n) average when input is uniformly distributed across buckets. The catch in all three: they need assumptions about the keys. Given arbitrary objects with only a comparator, n log n is genuinely the floor.

Maintain low and high bounds, compute the midpoint, and discard half based on the comparison. Three recurring bugs. First, overflow: computing (low + high) / 2 overflows for large indices in a fixed-width integer. Use low + (high - low) / 2. This was a real bug in Java's own binary search for nearly a decade. Second, the loop condition. Using low <= high with an inclusive high, versus low < high with an exclusive high, changes whether the final candidate is ever examined. Mixing the two conventions leaves one element unchecked. Third, the update. With an inclusive high you must move to mid - 1 and mid + 1; failing to exclude mid means the range never shrinks and you loop forever. Pick one convention and stay in it. The safest habit is to state the invariant out loud — "the answer, if it exists, is always within [low, high]" — and check every branch preserves it. O(log n), and it requires sorted input.

A modified binary search. At each step, at least one half is still properly sorted — compare the midpoint against an endpoint to work out which. If the left half is sorted, check whether the target lies within its range; if so search left, otherwise search right. Mirror the logic when the right half is sorted. Either way you still halve the search space each iteration, so it stays O(log n). The insight is that rotation breaks global sortedness but never breaks both halves at once. Duplicates ruin the guarantee. When the midpoint equals both endpoints you cannot tell which side is sorted, and the fallback is to shrink the bounds by one — degrading to O(n) in the worst case. Interviewers frequently add duplicates as the follow-up specifically to see whether you notice. The alternative is finding the rotation pivot first with its own binary search, then searching the appropriate segment. Two passes, both logarithmic, and often easier to reason about.

Instead of searching an array, you binary search over the range of possible answers, using a feasibility check to decide which half to keep. It applies when the answer space is monotonic: if a candidate value works, everything above it works too — or everything below. That monotonicity is what makes halving valid, and it is the condition to state explicitly. The classic shape is a minimisation problem: "the minimum capacity to ship packages in D days", "the smallest largest sum when splitting an array into k parts", "the minimum eating speed to finish in H hours". In each, you can check a candidate in O(n) and the check is monotonic. Total cost is O(n log(range)), which turns an apparently intractable optimisation into something routine. The giveaway phrasing is "minimise the maximum" or "maximise the minimum". When you hear that and a candidate is cheap to verify, this is almost certainly the intended approach.

It is quicksort that only recurses into the side containing the answer. Partition around a pivot. If the pivot lands at index k you are done. If k is smaller, recurse left only; if larger, recurse right only. Discarding one side entirely is the whole saving. The cost analysis: each partition is O(n), and with a good pivot the remaining work halves. n + n/2 + n/4 + ... converges to 2n, so O(n) average — strictly better than sorting for a single order statistic. Worst case is O(n²) with consistently bad pivots. Random pivot selection makes that vanishingly unlikely; median-of-medians guarantees O(n) worst case but with constants bad enough that nobody uses it in practice. It mutates the input, which is worth flagging before you write it. Compared to a size-k heap at O(n log k), Quickselect wins for a one-shot query on an in-memory array; the heap wins on streams and when you need all k elements rather than just the kth.

Two binary searches with deliberately biased tie-breaking. For the first occurrence, when you find the target do not stop — record it and continue searching left by setting high to mid - 1. For the last occurrence, record and continue right by setting low to mid + 1. That is the entire trick: a standard binary search returns an arbitrary matching index among duplicates, so you keep searching in the direction of the boundary you want. O(log n) for each search, O(log n) overall, against the O(n) of finding one match and then scanning outward — which is the tempting wrong answer and degrades badly when the array is all one value. Return a sentinel such as [-1, -1] when absent, and run the second search only if the first found something. The same bounded-search idea underlies lowerBound and upperBound, which is how you count occurrences in O(log n) by subtracting the two.

A base case, a recursive case, and progress toward the base case. The base case terminates. The recursive case solves a smaller instance and combines the result. Progress is the part people omit: each call must move measurably closer to the base case, or you recurse forever regardless of how correct the base case looks. The practical discipline is to trust the recursion. Assume the recursive call returns the right answer for the smaller input, and focus only on combining correctly. Trying to trace the entire call tree mentally is where people get lost. In Java the stack is the hard limit — roughly ten to twenty thousand frames by default. Deep recursion on a linked list or degenerate tree throws StackOverflowError, so anything with unbounded depth should be iterative with an explicit stack. The JVM does not eliminate tail calls, so writing a tail-recursive function buys you nothing here, unlike in Scala or functional languages.

Backtracking builds candidates incrementally and abandons a partial candidate the moment it cannot possibly lead to a valid solution. The difference from brute force is pruning. Brute force generates every complete candidate then tests it. Backtracking tests partial candidates and cuts entire subtrees of the search space at once. N-Queens illustrates it: brute force would place all queens then check, exploring an astronomical space. Backtracking rejects a placement as soon as two queens attack, eliminating every arrangement below that node. The skeleton is always the same three steps: choose, explore, un-choose. The un-choose is what makes it backtracking — you mutate shared state on the way down and restore it on the way up, so siblings see a clean slate. Forgetting to undo the choice is the standard bug, and it produces answers that are subtly contaminated by earlier branches rather than obviously wrong. Worst case is still exponential; pruning changes the constant and, in practice, feasibility.

Two standard approaches. Recursive: for each element, branch on including it or not. The recursion tree has depth n and 2ⁿ leaves, one per subset. Add the current partial set to the results at every node, not just the leaves. Bit manipulation: iterate an integer mask from 0 to 2ⁿ - 1 and treat each bit as "include this index". Elegant, iterative, and avoids recursion depth entirely — though it caps out around n = 31 for an int. O(n · 2ⁿ) either way, since there are 2ⁿ subsets each costing O(n) to materialise. That is optimal — you cannot enumerate 2ⁿ things faster than 2ⁿ. Duplicates are the usual follow-up. Sort first, then at each level skip an element equal to its predecessor unless it is the first choice at that level. Without that, [1,2,2] emits the subset [1,2] twice. The same pattern generates permutations and combinations with different branching rules.

Place one queen per row, and for each row try every column that is not attacked, recursing to the next row and undoing the placement on the way back. One queen per row is itself a pruning decision — it removes row conflicts from consideration entirely and collapses the search space before you start. The efficient conflict check uses three boolean arrays rather than scanning the board: one for columns, one for the descending diagonals indexed by row + col, one for the ascending diagonals indexed by row - col + n - 1. Each is O(1) to test and update, turning an O(n) check into constant time. Those diagonal index formulas are the part worth memorising — cells on the same diagonal share exactly that sum or difference. Complexity is roughly O(n!) with pruning making it far better in practice than the naive bound suggests. It is asked because it forces you to design the state representation, not just write a loop.

Two common approaches. Swap-based: for each index i, swap it with every index from i to the end, recurse on i+1, then swap back. No extra visited array, and it mutates in place. Used-array based: maintain a boolean array of which elements are already in the current permutation, and at each level try every unused element. Slightly more allocation but easier to extend when handling duplicates. O(n · n!) — there are n! permutations, each costing O(n) to copy into the result. Duplicates need the used-array version. Sort first, then skip an element if it equals the previous one and the previous one is not currently used at this level. That condition is fiddly and worth stating carefully: it ensures identical elements are always consumed in a fixed left-to-right order, so no arrangement repeats. The swap version cannot easily dedupe, because swapping destroys the sorted order the skip condition depends on.

Three triggers. Depth. If the recursion can go deeper than a few thousand frames, the JVM stack will overflow. Traversing a degenerate tree or a long linked list recursively is a production incident waiting to happen. Performance in a hot path. Each call has frame setup cost. For a tight, frequently-executed routine an explicit loop is measurably faster. Control. An explicit stack lets you pause, resume, or inspect the traversal state — impossible with the call stack. The mechanical conversion is to replace the call stack with an explicit Deque holding whatever the frame held. Preorder traversal converts trivially: push the root, then pop-and-push children with the right child first so the left is processed first. Inorder is fiddlier, and postorder fiddlier still. Against that, recursion is usually clearer, and clarity is worth real money. Convert when you have a concrete reason, not on principle — an iterative postorder traversal is genuinely harder to read and to get right.

Optimal substructure and overlapping subproblems. Both are required, and confusing them with each other is common. Optimal substructure means the optimal solution is built from optimal solutions to subproblems. The shortest path from A to C through B contains the shortest path from A to B. Without this, solving subproblems optimally tells you nothing about the whole. Overlapping subproblems means the same subproblem is solved repeatedly. Naive fibonacci recomputes fib(3) an exponential number of times. Caching turns that exponential into linear. If you have optimal substructure but no overlap, you want divide and conquer instead — merge sort has optimal substructure but every subproblem is distinct, so memoising it would waste memory for no gain. If you have overlap but no optimal substructure, DP gives wrong answers. Longest simple path in a graph is the standard counterexample: combining optimal subpaths can revisit a vertex, which is why that problem is NP-hard.

Both cache subproblem results; they differ in direction and in what gets computed. Memoisation is top-down. Write the natural recursion and add a cache lookup at the top. Only the subproblems actually reachable from the target are ever computed, which is a genuine advantage when the state space is sparse. Tabulation is bottom-up. Fill a table from the base cases upward in dependency order. No recursion, so no stack overflow, and the tight loops are usually faster with better cache behaviour. Memoisation is easier to write — you start from the brute-force recursion and add three lines. Tabulation requires working out the correct iteration order up front, which is where the thinking goes. Tabulation also enables space optimisation. If each row depends only on the previous one, you keep two rows instead of the full table, dropping O(n·m) to O(m). Knapsack and edit distance both do this. Start with memoisation in an interview, then convert if asked to optimise.

State is dp[i][w] — the maximum value using the first i items within capacity w. For each item you either skip it, inheriting dp[i-1][w], or take it if it fits, giving value[i] + dp[i-1][w - weight[i]]. Take the larger. That binary choice per item is what "0/1" names. O(n·W) time and space. Note this is pseudo-polynomial, not polynomial: W is a numeric value, so the cost grows with the magnitude of the capacity, not the size of the input. For enormous W it is impractical, which is consistent with knapsack being NP-hard. The space optimisation is a favourite follow-up. Each row depends only on the row above, so a single array suffices — but you must iterate capacity in decreasing order. Ascending order lets an item be used twice, which silently solves the unbounded knapsack problem instead. That direction detail is the entire difference between 0/1 and unbounded knapsack, and it is worth stating explicitly.

dp[i][j] is the LCS length of the first i characters of one string and the first j of the other. If the characters at those positions match, the answer is 1 + dp[i-1][j-1] — extend the previous match. If they differ, take the larger of dp[i-1][j] and dp[i][j-1], meaning skip a character from one string or the other. O(n·m) time and space. To recover the actual subsequence rather than its length, walk backwards from dp[n][m], moving diagonally on matches and toward the larger neighbour otherwise. Space drops to O(min(n,m)) with two rows if you only need the length, but reconstruction needs the full table — a trade worth naming. The reason it appears everywhere: diff tools, version control merges and DNA sequence alignment are all LCS. Edit distance is the same recurrence with different transition costs, which is why solving one gets you the other.

dp[amount] is the fewest coins making that amount. Initialise dp[0] to zero and everything else to infinity, then for each amount try every coin: dp[a] = min(dp[a], dp[a - coin] + 1). O(amount × coins) time, O(amount) space. Greedy — always take the largest coin that fits — works for well-formed currency systems like Indian rupees or US coins, which is why it feels right. It fails on arbitrary denominations. With coins [1, 3, 4] making 6, greedy takes 4 then 1 then 1 for three coins; the optimum is 3 + 3, two coins. The reason greedy fails is that taking the largest coin now can leave a remainder that is awkward to fill, and greedy never reconsiders. DP explores every combination and so cannot be trapped that way. Be careful to distinguish this from counting the number of ways to make the amount, which is a different recurrence — and one where loop order matters, since iterating coins outermost counts combinations while amounts outermost counts permutations.

The straightforward DP is O(n²): dp[i] is the LIS length ending at i, computed by scanning every earlier j with a smaller value and taking the best. The O(n log n) approach maintains an array where position k holds the smallest possible tail value of an increasing subsequence of length k+1. For each element, binary search for the first tail that is greater than or equal to it and overwrite it; if none exists, append. The crucial caveat: that array is not the LIS itself. It is a set of best-possible tails and often contains values that never co-occur in any single subsequence. Its length is correct; its contents are not the answer. Recovering the actual subsequence requires tracking predecessor indices alongside the binary search. Use lower bound for strictly increasing and upper bound for non-decreasing — that one-line difference is a frequent follow-up.

The signals are fairly reliable. The problem asks for an optimum — minimum, maximum, longest, fewest — or for a count of ways, rather than for one specific item. Optimisation and counting are the two DP shapes. You can describe the answer in terms of a choice at each step, where the remaining problem is the same problem on a smaller input. The brute-force solution is exponential and visibly recomputes the same states. The practical method: write the brute-force recursion first, without worrying about efficiency. Then identify which parameters actually vary — those are your state. Then add a cache. That sequence gets you to a correct DP far more reliably than trying to write the table directly, and it gives the interviewer something correct to look at early. The anti-signal is a greedy choice that is provably safe, or a problem asking for any valid answer rather than the best one. Those usually have simpler solutions and DP is over-engineering.

Both are linear DP scans, but the constraint differs and so does the recurrence. Maximum subarray (Kadane's) requires contiguity. The choice at each element is extend the current run or restart: current = max(nums[i], current + nums[i]). House robber forbids adjacency. The choice is rob this house and add the best from two back, or skip it and keep the best from one back: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). So one is about where a contiguous run starts, the other about skipping alternate positions. Contiguity versus exclusion. Both reduce to O(1) space by keeping two scalars instead of an array. The circular variant of house robber is the good follow-up: with houses in a circle the first and last are adjacent, so you run the linear solution twice — once excluding the first house, once excluding the last — and take the better. Handle the single-house case separately or that split breaks.

Greedy is correct when the problem has the greedy choice property: a locally optimal choice is part of some globally optimal solution. Combined with optimal substructure, that makes the greedy sequence optimal. The standard proof technique is an exchange argument. Assume an optimal solution differs from the greedy one, find the first point of difference, and show you can swap in the greedy choice without making the solution worse. Repeating that converts the optimal solution into the greedy one, so greedy must also be optimal. The danger is that greedy always produces an answer, and a wrong one looks exactly like a right one. Coin change with denominations [1,3,4] making 6 is the standard trap. So the discipline is: never assume greedy works because it feels right. Either construct the exchange argument, or actively search for a counterexample. If you can do neither quickly in an interview, say so and fall back to DP, which is correct whenever greedy is and also when it is not.

For maximum non-overlapping activities: sort by end time and greedily take each activity that starts after the last one taken ended. Sorting by end time is the crux. Finishing earliest leaves the most remaining time for everything after, which is exactly the exchange argument that proves it optimal. Sorting by start time or by duration both produce counterexamples — a single long meeting starting first blocks several short ones. For the different question of how many rooms are needed for all meetings, use a min-heap of end times. For each meeting in start order, pop any room whose meeting has ended, then allocate. The heap size is the answer. The alternative for room counting is a sweep line: mark +1 at each start and -1 at each end, sort the events, and track the running maximum. O(n log n) in all cases, dominated by the sort. Decide carefully whether touching endpoints count as overlapping — it changes a comparison from < to <=.

Sort by start time, then sweep once. Keep the current merged interval; if the next interval starts at or before the current end, extend the end to the maximum of the two, otherwise close the current interval and start a new one. Sorting by start is what makes a single pass sufficient — you never need to look backwards, because anything overlapping the current interval must start before its end and therefore appears next in order. The detail people get wrong is extending to max(currentEnd, nextEnd) rather than just nextEnd. A fully nested interval such as [1,10] followed by [2,3] would otherwise shrink the merged range. O(n log n) for the sort, O(n) for the sweep. Decide explicitly whether [1,2] and [2,3] merge. Using <= merges touching intervals, < does not — and the right answer depends entirely on whether the intervals are inclusive, which is worth asking rather than assuming.

Both need optimal substructure. The difference is whether you can commit to a choice without looking ahead. Greedy makes one locally best choice at each step and never reconsiders. One pass, no table, typically O(n log n) dominated by a sort, O(1) extra space. DP explores every choice and keeps the best, which is why it is slower and heavier but correct in strictly more cases. Anywhere greedy works, DP also works — greedy is the optimisation available when you can prove the extra exploration is unnecessary. Fractional knapsack is greedy: you can take fractions, so taking the best value-per-weight first is provably optimal. 0/1 knapsack is DP, because the all-or-nothing constraint means a locally attractive item can block a better combination. The practical interview approach: try greedy first because it is simpler, actively hunt for a counterexample, and fall back to DP when you find one or cannot convince yourself none exists.