Blind 75

A set answers "seen before" in O(1). Walk the array adding each value to a hash set; if it is already there, return true. Sorting also works but pays O(n log n) for nothing.

O(n) time, O(n) space

Anagrams are equal letter counts. Increment 26 counters for s, decrement for t, and demand every counter ends at zero. One array beats two maps.

O(n) time, O(1) space

Each number's partner is fixed: target minus it. One pass with a hash map from value to index; before inserting nums[i], check whether target - nums[i] already sits in the map. Checking before inserting handles duplicates cleanly.

O(n) time, O(n) space

Anagrams share a canonical key. Map each word to its 26-slot letter-count tuple (or its sorted form) and bucket words under that key in a hash map; the buckets are the answer. Count keys skip the per-word sort.

O(n k) time, O(n k) space, n words of length k

A frequency can never exceed n, so you can bucket instead of sort. Count with a hash map, drop each value into buckets[count], then walk buckets from n downward collecting until you have k. That is bucket sort on frequency; a size-k heap is the O(n log k) fallback.

O(n) time, O(n) space

answer[i] is the product of everything left of i times everything right of i, no division needed. First pass writes prefix products into the output array; second pass sweeps right to left carrying a running suffix product and multiplying it in.

O(n) time, O(1) extra space beyond the output

Any fixed delimiter can appear inside the data, so make the framing unambiguous with a length header. Encode each string as len#string; decode by reading digits up to the '#', then slicing exactly that many characters. This is length-prefix framing, the same trick TCP protocols use.

O(n) time, O(n) space for the output

Only the start of a run deserves work. Pour everything into a hash set; for each x whose x-1 is absent, walk x, x+1, x+2 while present and record the streak length. Every element is touched at most twice, so no sort is needed.

O(n) time, O(n) space

Compare the string against itself from both ends. Two pointers walk inward, each skipping non-alphanumeric characters, comparing lowercased values; any mismatch ends it.

O(n) time, O(1) space

Sort first; then fixing the smallest element reduces the rest to two-sum on a sorted suffix. For each i, run left and right pointers inward: sum too small moves left up, too big moves right down. Skip duplicate values at i, left and right to keep triples unique.

O(n²) time, O(1) extra space beyond sort and output

Width only shrinks as pointers move inward, so the only hope of improvement is a taller limiting wall. Start at both ends, record the area, and always advance the pointer at the shorter line: keeping it can never beat the current area, so discarding it is safe.

O(n) time, O(1) space

The best sell on any day pairs with the cheapest buy before it. One pass carrying the minimum price so far: at each price, update best profit with price minus that minimum, then update the minimum. Nothing else to remember.

O(n) time, O(1) space

Grow the window right; when the new character repeats, shrink from the left until the duplicate is gone. A set of in-window characters (or a last-seen index map to jump the left edge) keeps the check O(1). Record the window length at every step.

O(n) time, O(min(n, alphabet)) space

A window is fixable when its length minus its most frequent letter's count is at most k. Slide right keeping per-letter counts and a running max count; when length - maxCount exceeds k, step the left edge once. The max count is allowed to go stale: the answer only cares about windows at least as good as the best already seen, so the window never needs to shrink below it.

O(n) time, O(1) space (26 counters)

Expand right until the window covers every character of t with multiplicity, then contract left as far as coverage survives, recording the span. Keep need and have count maps plus one counter of fully satisfied characters, so the coverage test is O(1) per step. This expand-contract loop is the canonical hard sliding window.

O(n + m) time, O(1) space (alphabet-sized maps)

A closer must match the most recent unmatched opener, which is exactly a stack's top. Push openers; on a closer, pop and compare, failing on mismatch or an empty stack. Valid means the stack ends empty.

O(n) time, O(n) space

The minimum is the one place order breaks, and comparing mid to the right end tells you which side of the break you stand on. If nums[mid] > nums[right] the pivot is to the right, so lo = mid + 1; otherwise the minimum is mid or left of it, so hi = mid. Stop when lo meets hi.

O(log n) time, O(1) space

At any mid, at least one half is fully sorted, and you can tell which by comparing endpoints. If the sorted half's range contains the target, recurse into it; otherwise take the other half. It is a standard binary search skeleton with one extra range test per step.

O(log n) time, O(1) space

Flip one pointer at a time. Keep prev and curr: save curr.next, point curr.next at prev, advance both. When curr falls off the end, prev is the new head. Say the three-step body out loud until it is muscle memory.

O(n) time, O(1) space

It is the merge step of merge sort with pointers. Start from a dummy head, repeatedly attach the smaller of the two front nodes and advance that list, then attach whatever list remains.

O(n + m) time, O(1) space

Three primitives glued together: find the middle with fast and slow pointers, reverse the second half in place, then interleave the two halves one node at a time. No extra list, no recursion.

O(n) time, O(1) space

Two pointers with a gap of n. Advance the leader n steps from a dummy head, then move leader and trailer together until the leader hits the end: the trailer now sits just before the victim, so splice around it. The dummy head is what makes deleting the real head a non-event.

O(n) time, O(1) space, one pass

Floyd's fast and slow pointers: slow steps one, fast steps two. On a straight chain fast reaches null; inside a cycle fast gains one node per step on slow and must catch it. Meeting proves the cycle with zero extra memory.

O(n) time, O(1) space

A min-heap over the k current heads always knows the globally smallest node. Pop it, append to the output, push its successor, repeat until the heap drains. Pairwise divide-and-conquer merging reaches the same bound with no heap, which makes a good follow-up answer.

O(N log k) time, O(k) space, N total nodes

Swap the children at every node and recursion does the rest. Null returns null; otherwise invert left, invert right, swap, return the node.

O(n) time, O(h) space on the stack

Depth is one plus the deeper subtree. Return 0 for null, else 1 + max(depth(left), depth(right)). The recursive definition is the code.

O(n) time, O(h) space

Two trees match when the roots agree and both subtree pairs match. Both null: true. One null or unequal values: false. Otherwise recurse left with left and right with right.

O(n) time, O(h) space

Use Same Tree as a subroutine. At each node of the host tree ask "is this identical to subRoot?"; if not, try both children. Empty subRoot is trivially a subtree, which is the edge case to say out loud.

O(n m) time worst case, O(h) space

The BST ordering is a compass. From the root: both values smaller, go left; both larger, go right; otherwise the paths split here (or one value is the node itself), and this node is the LCA. Iterate, no stack needed.

O(h) time, O(1) space

BFS with a queue, one level per round. Snapshot the queue's size, pop exactly that many nodes into one output row while pushing their children for the next round. The size snapshot is the whole trick.

O(n) time, O(n) space

Comparing each node with its children is the famous wrong answer; every node must respect bounds inherited from all ancestors. DFS passing (low, high): the node must lie strictly between them, the left child inherits (low, node), the right inherits (node, high). Equivalently, inorder traversal must be strictly increasing.

O(n) time, O(h) space

Inorder traversal of a BST emits values in sorted order. Run it iteratively with an explicit stack, counting pops; the kth pop is the answer and you stop right there instead of finishing the walk.

O(h + k) time, O(h) space

Preorder hands you roots in order; inorder tells you what lies left and right of each. Consume preorder left to right with a moving pointer, and for each root split the current inorder range at its position, recursing left then right. A hash map from value to inorder index makes every split O(1).

O(n) time, O(n) space

Every node computes two different numbers. The gain it offers its parent is node plus the better child gain, floored at zero; the best path bending through it is node plus both gains, which only updates a global maximum because a bent path cannot continue upward. One postorder DFS carries both.

O(n) time, O(h) space

Preorder with explicit null markers is unambiguous, so one traversal pins down the whole shape. Serialize by DFS emitting each value and a sentinel like # for null, comma separated. Deserialize by consuming tokens from an iterator in the same preorder: read one token, build the node, recurse left then right.

O(n) time, O(n) space

Each node is a child map (or a 26-slot array) plus an end-of-word flag. Insert walks the word creating missing children; search walks failing on a missing child and finally checks the flag; startsWith is search minus the flag check.

O(L) per operation, O(total characters) space

A trie where '.' means "try every child". addWord is a plain trie insert. search becomes a DFS down the trie: a letter follows its single edge, a dot branches into all children, and success is reaching the end flag at the last character.

O(L) add; search O(L), worst case the whole trie with dots

Searching each word separately re-walks the board; instead build one trie of all the words and DFS the grid once, descending the trie in lockstep with each step. Mark cells in place while exploring, collect a word whenever a terminal node is reached, and prune exhausted trie leaves as you backtrack: that pruning is what keeps it fast.

O(m n · 3^L) time worst case, O(total characters) space

Split the stream into two heaps meeting at the median: a max-heap holding the smaller half and a min-heap holding the larger half, sizes kept within one. Each add pushes into one heap, then rebalances by moving a top across if sizes or order break. The median is the bigger heap's top, or the mean of both tops when even.

O(log n) addNum, O(1) findMedian, O(n) space

Branch on "use this candidate again, or move on for good". At index i with a remaining target: include candidates[i] and stay at i (reuse is allowed), or skip to i + 1 permanently, which is what prevents duplicate combinations. Record a copy of the path when the remainder hits zero, prune when it goes negative.

Exponential time, about 2^(t/m) nodes; O(t/m) depth (t target, m smallest candidate)

DFS from every cell matching the first letter, advancing one character into the four neighbors. Overwrite the current cell with a sentinel before recursing and restore it after: that in-place mark is the visited set and the backtrack in one move.

O(m n · 3^L) time, O(L) recursion space

Each island is a connected component, so count how many times a fresh '1' starts a flood fill. Scan every cell; on unvisited land, increment the count and DFS or BFS the whole component, sinking cells to '0' in place so they never count twice.

O(m n) time, O(m n) worst-case stack or queue space

One hash map from original to clone does double duty: it stitches edges and it stops cycles from recursing forever. DFS: if the node is already in the map, return its clone; otherwise create the clone, record it before touching neighbors, then clone each neighbor into the adjacency list.

O(V + E) time, O(V) space

Tracing water downhill from every cell repeats work; flow uphill from the oceans instead. DFS or BFS from all Pacific border cells moving only to equal-or-higher neighbors, then the same from the Atlantic border. The answer is the intersection of the two reachable sets.

O(m n) time, O(m n) space

Finishable means the prerequisite digraph has no cycle. Kahn's algorithm: compute indegrees, queue every zero-indegree course, pop one at a time while decrementing its dependents and queueing new zeros. If you pop all V courses there is no cycle; DFS with a three-state visited array is the equivalent recursive answer.

O(V + E) time, O(V + E) space

A tree is exactly n - 1 edges and no cycle (that combination forces connectivity). Reject the wrong edge count immediately, then union-find over the edges: a union whose two endpoints already share a root is a cycle, so return false. All unions succeeding means valid.

O(n α(n)) time, O(n) space

Start with n components and let every successful union merge two. Union-find with path compression and union by size; each edge either merges two sets (decrement the count) or lands inside one (do nothing). DFS from each unvisited node counting starts gives the same number.

O(V + E α(V)) time, O(V) space

Each adjacent word pair yields one constraint: the first differing characters give an edge u before v. Build that digraph over every letter seen, rejecting the illegal case where a word is followed by its own prefix extension reversed (like "abc" before "ab"). Topologically sort with Kahn's algorithm; if some letters never reach indegree zero there is a cycle, so return "".

O(C) time over total characters, O(V + E) space, V at most 26

The last move was 1 step or 2, so ways(n) = ways(n - 1) + ways(n - 2). That is Fibonacci; iterate upward with two rolling variables and no array.

O(n) time, O(1) space

At each house: rob it plus 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]), rolled into two variables.

O(n) time, O(1) space

The circle adds exactly one constraint: the first and last house cannot both be robbed. So run linear House Robber twice, once excluding the last house and once excluding the first, and take the max. A single house is the special case worth saying.

O(n) time, O(1) space

Every palindrome has a center: n odd centers plus n - 1 even ones. Expand around each center while the two ends match, tracking the longest span seen. Manacher's algorithm does it in O(n), and nobody expects it in an interview.

O(n²) time, O(1) space

The same expand-around-center machine as the previous problem, but count instead of maximize. Each successful one-step expansion certifies exactly one new palindrome, over all 2n - 1 centers.

O(n²) time, O(1) space

dp[i] counts decodings of the first i characters. A nonzero digit extends every decoding counted by dp[i - 1]; a two-digit value from 10 to 26 extends dp[i - 2]. Zeros are the whole difficulty: '0' contributes nothing alone and kills strings like "30". Two rolling variables suffice.

O(n) time, O(1) space

Unbounded knapsack for minimum count. dp[a] is the fewest coins making amount a: dp[0] = 0, dp[a] = 1 + min over coins of dp[a - coin], infinity where unreachable. Fill bottom-up to dp[amount] and translate infinity to -1. Greedy by largest coin is the trap; it fails on sets like {1, 3, 4}.

O(amount · coins) time, O(amount) space

A negative number flips the biggest product into the smallest, so carry both. Track the max and min product of a subarray ending here; each new element sets them from {num, num · prevMax, num · prevMin}. The answer is the best max ever seen.

O(n) time, O(1) space

dp[i] asks whether the first i characters can be segmented. dp[0] is true, and dp[i] is true when some j < i has dp[j] true and s[j..i) in the dictionary set. Answer is dp[n]; bounding j by the longest dictionary word is the easy speedup.

O(n²) time with O(1) hashing, O(n) space

The O(n²) DP is dp[i] = 1 + max dp[j] over j < i with nums[j] < nums[i]. The better answer is patience sorting: keep tails[k], the smallest possible tail of any increasing subsequence of length k + 1, binary search each number's slot, and replace or append. tails' length is the answer; tails itself is not a real subsequence, which is the classic follow-up.

O(n log n) time, O(n) space

Paths into a cell come from above or from the left, so counts add. Keep one rolling row initialized to 1s and sweep: row[j] += row[j - 1]. The closed form C(m + n - 2, m - 1) is the flex answer.

O(m n) time, O(n) space

dp[i][j] is the LCS of the first i characters of one string and the first j of the other. Matching characters take 1 plus the diagonal; otherwise take the max of dropping the last character from either side. Two rows are enough memory.

O(m n) time, O(min(m, n)) space

Kadane: a running prefix with a negative sum can only drag the future down, so drop it. Carry cur = max(num, cur + num) and record the best cur seen. One pass, two variables.

O(n) time, O(1) space

Track the furthest index reachable so far. Scan left to right: if i ever exceeds reach you are stranded, otherwise reach = max(reach, i + nums[i]). Reachable means reach covers the last index; walking backwards moving a goalpost is the equivalent greedy from the other end.

O(n) time, O(1) space

The list is already sorted, so it splits into three phases. Copy every interval ending before the new one starts; absorb everything overlapping it by taking min start and max end; copy the rest untouched. The absorbed blob goes out as one interval.

O(n) time, O(n) space for the output

Sort by start; after that, only the most recent merged interval can overlap the next one. Sweep, extending the current interval's end while new starts fall inside it, and emit it when a gap appears.

O(n log n) time, O(n) space for the output

Minimum removals equals n minus the largest compatible set, and that is activity selection: sort by end, greedily keep every interval starting at or after the last kept end. Keeping the earliest-ending interval always leaves the most room, which is the exchange argument to say out loud.

O(n log n) time, O(1) extra space

One person attends everything only if no two meetings overlap. Sort by start and check each meeting's start against the previous meeting's end; any start before the previous end is a conflict.

O(n log n) time, O(1) space

Rooms needed is the peak number of simultaneous meetings. Sort starts and ends into separate arrays and sweep with two pointers: a start before the next end opens a room, an end frees one; track the running peak. A min-heap of end times is the equivalent phrasing.

O(n log n) time, O(n) space

A 90 degree clockwise rotation is a transpose followed by reversing each row. Both are in-place swaps, so no second matrix ever exists. The alternative is rotating four cells at a time ring by ring, which is more code for the same bound.

O(n²) time, O(1) space

Keep four shrinking bounds: top, bottom, left, right. Walk the top row then shrink top, right column then shrink right, and guard the bottom and left walks with a bounds check for the collapsed single row or column case. Loop until the bounds cross.

O(m n) time, O(1) extra space

Use the first row and first column as the marker store instead of O(m + n) sets. Two booleans remember whether they themselves must be zeroed; for every zero found, mark its row head and column head. Zero the interior from the markers, then handle the first row and column last.

O(m n) time, O(1) space

Kernighan: n & (n - 1) clears exactly the lowest set bit. Loop it until n is zero, counting iterations, so the loop runs once per set bit instead of once per bit position.

O(1) time (at most 32 iterations), O(1) space

DP on the bits themselves: bits(i) = bits(i >> 1) + (i & 1), because shifting right drops only the last bit. Fill 0 to n in one pass; every entry reads an already-computed smaller index. bits(i) = bits(i & (i - 1)) + 1 is the equally valid sibling.

O(n) time, O(1) space beyond the output

Build the answer bit by bit: 32 times, shift the result left, OR in the input's lowest bit, shift the input right. The divide-and-conquer version (swap halves, then bytes, nibbles, pairs, singles with masks) is the O(log w) flex if asked for better.

O(1) time (32 steps), O(1) space

XOR of equal numbers cancels to zero. XOR together all indices 0 to n and all array values; every present number appears in both groups and vanishes, leaving the missing one. The sum formula n(n + 1)/2 minus the array sum works too, but XOR cannot overflow.

O(n) time, O(1) space

XOR adds without carrying, and AND shifted left is exactly the carries. Loop a, b = a ^ b, (a & b) << 1 until b is zero; a is the sum. In Python, mask to 32 bits each round and sign-extend at the end, because its integers never overflow into two's complement on their own.

O(1) time (bounded by word size), O(1) space