Arrays & Hashing 22 · Count, look up and group in O(1) with hash maps and sets. Contains Duplicate Easy ★★★ #217 Hash map lookup Compare every pair ⏱ O(n²) ▦ O(1) Hash set of seen values ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 3 edge cases · 5 testsEmpty array: nothing can repeat. 'Seen before?' → hash set: one pass, O(n) time and space. If memory is tight, sort and compare neighbours: O(n log n) time, O(1) extra. new Valid Anagram Easy ★★★ #242 Hash map lookup Sort both strings ⏱ O(n log n) ▦ O(n) Count letters ⏱ O(n) ▦ O(1) O(n) from O(n log n) · space O(1) 3 edge cases · 5 testsDifferent lengths can never be anagrams: check length first. Same multiset of letters → frequency count in one hash map (or a 26-slot array): O(n) time, O(1) space for a fixed alphabet. new Two Sum Easy ★★★ #1 quant Hash map lookup Try every pair ⏱ O(n²) ▦ O(1) One-pass hash map of complements ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 4 edge cases · 5 tests3 + 3 = 6 but there's only one 3: you can't reuse index 0. Pair with a target sum → complement lookup in a hash map: O(n) time, O(n) space. If the array were sorted, two pointers would do it in O(1) space. new Group Anagrams Medium ★★★ #49 Hash map lookup Compare with each existing group ⏱ O(n·g·k log k) ▦ O(n·k) Hash map from letter signature to group ⏱ O(n·k log k) ▦ O(n·k) O(n·k log k) from O(n·g·k log k) · space O(n·k) 3 edge cases · 4 testsAn empty string is a valid word and forms its own group. Group by an invariant → hash map keyed by a canonical signature (sorted letters or a count tuple): O(n·k log k), or O(n·k) with counts. new Top K Frequent Elements Medium ★★★ #347 quant Hash map lookup Count, then sort by frequency ⏱ O(n log n) ▦ O(n) Bucket sort by frequency ⏱ O(n) ▦ O(n) O(n) from O(n log n) · space O(n) 3 edge cases · 5 testsA single element is the most frequent. Top-k by frequency → count with a hash map, then bucket by count for O(n) (or a size-k min-heap for O(n log k) when n is huge or streaming). new Product of Array Except Self Medium ★★★ #238 quant Prefix sums Multiply everything else, per index ⏱ O(n²) ▦ O(1) Prefix × suffix products ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 3 edge cases · 4 testsOne zero: only the zero's position gets a non-zero product. 'All except self' → prefix and suffix products in two passes: O(n) time, O(1) extra space, no division (so zeros are safe). new Valid Sudoku Medium ★★★ #36 Hash map lookup Check each unit separately ⏱ O(1) ▦ O(1) One pass with row, column and box sets ⏱ O(1) ▦ O(1) O(1) from O(1) · space O(1) 3 edge cases · 4 testsTwo 8s in the first column and in the top-left box. Constraint checking → one pass with a set per unit; the box index (r//3)*3 + c//3 is the key trick. new Longest Consecutive Sequence Medium ★★★ #128 Hash map lookup Sort, then count runs ⏱ O(n log n) ▦ O(n) Hash set, start only at run beginnings ⏱ O(n) ▦ O(n) O(n) from O(n log n) · space O(n) 3 edge cases · 5 testsEmpty input has no run at all. Runs in an unsorted array → hash set and only expand from run starts (x − 1 absent): each value is touched O(1) times, so O(n). new Majority Element Easy ★★★ #169 quant Hash map lookup Count with a hash map ⏱ O(n) ▦ O(n) Boyer–Moore voting ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 2 edge cases · 4 testsA single element is trivially the majority. Majority (> n/2) in O(1) space → Boyer–Moore voting: pairs of different values cancel and the majority survives. new Sort Colors Medium ★★★ #75 Two pointers Count, then overwrite ⏱ O(n) ▦ O(1) Dutch national flag (one pass) ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 3 edge cases · 5 testsOne element is already sorted. Three-way partition → Dutch national flag with low/mid/high pointers: one pass, O(1) space. new Subarray Sum Equals K Medium ★★★ #560 quant Prefix sums Every start, running sum ⏱ O(n²) ▦ O(1) Prefix sums + hash map of counts ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 3 edge cases · 5 testsBoth [1,2] and [3] sum to 3. Count subarrays with sum k (negatives allowed) → prefix sums + hash map of prefix counts, seeded with {0: 1}: O(n). new Rotate Array Medium ★★★ #189 Two pointers Copy into new positions ⏱ O(n) ▦ O(n) Three reversals ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 3 edge cases · 5 testsk > n: rotating by 3 is the same as rotating by 3 mod 2 = 1. In-place rotation → three reversals (k %= n first): O(n) time, O(1) space. new First Missing Positive Hard ★★★ #41 quant In-place index marking Hash set, then count up from 1 ⏱ O(n) ▦ O(n) Cyclic placement (value v goes to index v − 1) ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 3 edge cases · 5 tests1 is missing even though larger numbers are present. Smallest missing positive in O(1) space → the answer is in 1..n+1, so use the array as its own hash table: cyclic swaps to index v − 1. new Merge Sorted Array Easy ★★★ #88 Two pointers Append, then sort ⏱ O((m+n) log(m+n)) ▦ O(1) Fill from the back with three pointers ⏱ O(m+n) ▦ O(1) O(m+n) from O((m+n) log(m+n)) · space O(1) 3 edge cases · 4 testsNothing to merge: nums1 stays as it is. Merge two sorted arrays in place when the space is at the end → three pointers writing from the back: O(m + n), O(1) space. new Encode and Decode Strings Medium ★★★ #271 quant String building & parsing Spell every character as a number ⏱ O(n) ▦ O(n) Length prefix ⏱ O(n) ▦ O(n) O(n) from O(n) · space O(n) 3 edge cases · 4 testsEmpty strings must survive. Serialise a list of arbitrary strings → length-prefix framing (like HTTP chunking or protobuf): O(n). new Range Sum Query - Immutable Easy ★★★ #303 quant Prefix sums Sum the slice every time ⏱ O(n) per query ▦ O(1) Prefix sums ⏱ O(1) per query ▦ O(n) O(1) per query from O(n) per query · space O(n) 2 edge cases · 3 testsSingle-element range. Many range-sum queries on a static array → prefix sums: O(n) build, O(1) query. (Updates → Fenwick / segment tree.) new Next Permutation Medium ★★★ #31 quant Two pointers List every permutation ⏱ O(n!·n) ▦ O(n!·n) Pivot, swap, reverse the suffix ⏱ O(n) ▦ O(1) O(n) from O(n!·n) · space O(1) 2 edge cases · 5 testsAlready the largest: wrap around to the smallest. Next lexicographic permutation → find pivot from the right, swap with the next larger, reverse the suffix: O(n), O(1). new Contiguous Array Medium ★★★ #525 quant Prefix sums Check every subarray ⏱ O(n²) ▦ O(1) Running balance + first-seen index ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 1 edge cases · 5 testsNo balanced subarray exists. Longest balanced subarray → map 0 → −1, prefix sum + first-occurrence map: O(n). new Continuous Subarray Sum Medium ★★★ #523 quant Prefix sums Check every subarray of length ≥ 2 ⏱ O(n²) ▦ O(1) Prefix sums mod k + first index ⏱ O(n) ▦ O(min(n, k)) O(n) from O(n²) · space O(min(n, k)) 4 edge cases · 6 testsThe whole array sums to 42 = 7 × 6. Subarray sum divisible by k → prefix sums mod k + first-seen map (pigeonhole): O(n). new Find All Duplicates in an Array Medium ★★★ #442 In-place index marking Count with a hash map ⏱ O(n) ▦ O(n) Mark visits by negating ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 1 edge cases · 4 testsNo duplicates. Values 1..n, O(1) space → use the array as its own hash set by negating at index v − 1. new Isomorphic Strings Easy ★★★ #205 Hash map lookup Compare every pair of positions ⏱ O(n²) ▦ O(1) Two direction maps ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 1 edge cases · 5 testsb and d would both have to map to b: not one-to-one. Bijection between two strings → two maps (s→t and t→s): O(n). new Ransom Note Easy ★★★ #383 Hash map lookup Remove letters from a list ⏱ O(n·m) ▦ O(m) Count letters ⏱ O(n+m) ▦ O(1) O(n+m) from O(n·m) · space O(1) 2 edge cases · 4 testsOnly one 'a' available. Can multiset A be drawn from multiset B → count B, subtract A, check non-negative: O(n + m). new Strings 12 · Parsing, building and comparing text without wasted copies. Longest Common Prefix Easy ★★★ #14 String building & parsing Try prefixes from longest to shortest ⏱ O(m·S) ▦ O(m) Vertical scan ⏱ O(S) ▦ O(1) O(S) from O(m·S) · space O(1) 3 edge cases · 5 testsThe first letters already differ. Common prefix → vertical scan column by column, stop at the first mismatch: O(total characters). new Roman to Integer Easy ★★★ #13 String building & parsing Expand subtractive pairs, then add ⏱ O(n) ▦ O(n) Subtract when a smaller symbol precedes a larger one ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 2 edge cases · 5 testsThree subtractive pairs: CM = 900, XC = 90, IV = 4. Roman → integer: add each value, subtract when the next is larger: O(n). new Integer to Roman Medium ★★★ #12 Greedy Additive symbols, then fix subtractive forms ⏱ O(1) ▦ O(1) Greedy over 13 value–symbol pairs ⏱ O(1) ▦ O(1) O(1) from O(1) · space O(1) 1 edge cases · 5 testsSubtractive form, not IIII. Integer → Roman: greedy over the 13 value/symbol pairs (subtractives included): O(1). new Reverse Words in a String Medium ★★★ #151 Two pointers Split, reverse, join ⏱ O(n) ▦ O(n) Scan from the right with two pointers ⏱ O(n) ▦ O(n) O(n) from O(n) · space O(n) 2 edge cases · 4 testsLeading and trailing spaces are dropped. Reverse word order → scan from the right collecting words (or reverse all, then each word, in place): O(n). new Find the Index of the First Occurrence in a String Easy ★★★ #28 quant String building & parsing Compare at every position ⏱ O(n·m) ▦ O(1) Knuth–Morris–Pratt (KMP) ⏱ O(n+m) ▦ O(m) O(n+m) from O(n·m) · space O(m) 2 edge cases · 6 testsA partial match at index 1 fails; the search must fall back correctly. Substring search in linear time → KMP failure table (or Rabin–Karp rolling hash / Z-algorithm): O(n + m). new Minimum Remove to Make Valid Parentheses Medium ★★★ #1249 Stack BFS over removals ⏱ O(2ⁿ·n) ▦ O(2ⁿ) Stack of open indices ⏱ O(n) ▦ O(n) O(n) from O(2ⁿ·n) · space O(n) 3 edge cases · 5 testsEvery bracket must go. Fix brackets with minimum deletions → one pass with a stack of open indices; delete stray ')' immediately and leftover '(' at the end: O(n). new Text Justification Hard ★★★ #68 Probability & simulation Hand out spaces one at a time ⏱ O(n·W) ▦ O(W) Greedy packing + divmod spacing ⏱ O(n·W) ▦ O(W) O(n·W) from O(n·W) · space O(W) 2 edge cases · 4 testsA line with a single word is left-justified; so is the last line. Text layout → greedy line packing + divmod space distribution, with special last-line rules: O(total characters). new Longest Palindrome Easy ★★★ #409 Hash map lookup Sort and pair neighbours ⏱ O(n log n) ▦ O(n) Count letters ⏱ O(n) ▦ O(1) O(n) from O(n log n) · space O(1) 2 edge cases · 4 testsCase-sensitive: A and a don't pair. Max palindrome from a multiset → sum of pairs + 1 if any odd count: O(n). new String to Integer (atoi) Medium ★★★ #8 quant String building & parsing Extract the number, then clamp ⏱ O(n) ▦ O(n) Single pass with an overflow guard ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 5 edge cases · 8 testsLeading spaces, then a sign. Robust number parsing → explicit state machine (spaces → sign → digits) with pre-multiplication overflow checks: O(n). new Zigzag Conversion Medium ★★★ #6 Probability & simulation Draw the zigzag on a grid ⏱ O(n·r) ▦ O(n·r) One bucket per row ⏱ O(n) ▦ O(n) O(n) from O(n·r) · space O(n) 2 edge cases · 5 testsOne row: no zigzag (and the direction must not flip). Zigzag layout → per-row buckets with a bouncing row index: O(n). new Add Binary Easy ★★★ #67 Math & number tricks Convert to big integers ⏱ O(n) ▦ O(n) Column addition from the right ⏱ O(max(m, n)) ▦ O(max(m, n)) O(max(m, n)) from O(n) · space O(max(m, n)) 2 edge cases · 4 testsNo leading zeros beyond a single 0. Add numbers stored as strings → column addition from the right with a carry: O(max length). new Word Pattern Easy ★★★ #290 Hash map lookup Compare every pair of positions ⏱ O(n²) ▦ O(n) Two maps (letter → word, word → letter) ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 2 edge cases · 5 testsOne-to-one: a and b can't both map to dog. Bijection check between two sequences → two hash maps (or first-occurrence signatures): O(n). new Two Pointers 10 · Two indexes walking toward or after each other. Valid Palindrome Easy ★★★ #125 Two pointers Clean, then compare with the reverse ⏱ O(n) ▦ O(n) Two pointers from both ends ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 3 edge cases · 5 testsOnly non-alphanumeric characters: the cleaned string is empty, which is a palindrome. Symmetry check → two pointers from both ends, skipping junk: O(n) time, O(1) space. new Two Sum II (Sorted Input) Medium ★★★ #167 quant Two pointers Try every pair ⏱ O(n²) ▦ O(1) Two pointers squeezing inward ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 2 edge cases · 4 testsNegative numbers and a two-element array. Sorted array + pair sum + O(1) space → two pointers from both ends: O(n). new 3Sum Medium ★★★ #15 Two pointers Every triple, deduplicated with a set ⏱ O(n³) ▦ O(n) Sort, fix one, two-pointer the rest ⏱ O(n²) ▦ O(1) O(n²) from O(n³) · space O(1) 3 edge cases · 5 testsNo triplet sums to zero: return an empty list. kSum → sort, fix one element, two-pointer the rest, skip duplicates: O(n²) for 3Sum. new Container With Most Water Medium ★★★ #11 Two pointers Every pair of lines ⏱ O(n²) ▦ O(1) Squeeze from both ends, move the shorter line ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 3 edge cases · 5 testsTwo lines: the only container is width 1 × height 1. Max area between two boundaries → two pointers from the ends, always move the shorter side: O(n). new Trapping Rain Water Hard ★★★ #42 quant Two pointers For each bar, scan left and right walls ⏱ O(n²) ▦ O(1) Two pointers with running max walls ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 3 edge cases · 5 testsA rising slope has no walls on both sides: no water. Water above each bar = min(left max, right max) − height → prefix maxima, or two pointers moving the lower side: O(n), O(1). new Move Zeroes Easy ★★★ #283 Two pointers Copy non-zeros to a new list ⏱ O(n) ▦ O(n) Write pointer for non-zeros ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 3 edge cases · 4 testsA single zero stays put. Stable in-place partition → read/write pointers: O(n), O(1). new Valid Palindrome II Easy ★★★ #680 Two pointers Try deleting each character ⏱ O(n²) ▦ O(n) Two pointers, branch once on the first mismatch ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 3 edge cases · 5 testsAlready a palindrome: zero deletions needed. Palindrome with one allowed edit → two pointers, branch into two checks at the first mismatch: O(n). new Squares of a Sorted Array Easy ★★★ #977 Two pointers Square, then sort ⏱ O(n log n) ▦ O(n) Two pointers, fill from the back ⏱ O(n) ▦ O(n) O(n) from O(n log n) · space O(n) 2 edge cases · 4 testsAll negative: squares come out in reverse order. Sorted input whose transform is V-shaped → two pointers from the ends, filling the answer from the back: O(n). new Is Subsequence Easy ★★★ #392 Two pointers Recursive matching ⏱ O(2ⁿ) ▦ O(n) Greedy two pointers ⏱ O(n) ▦ O(1) O(n) from O(2ⁿ) · space O(1) 2 edge cases · 5 testsThe empty string is a subsequence of every string. Subsequence check → greedy two pointers in one pass: O(|t|). For many queries, index t's character positions and binary search. new 3Sum Closest Medium ★★★ #16 Two pointers Every triple ⏱ O(n³) ▦ O(1) Sort, fix one, two pointers ⏱ O(n²) ▦ O(1) O(n²) from O(n³) · space O(1) 3 edge cases · 4 testsOnly one triple exists. Closest kSum → same sort + two pointers as 3Sum, tracking the best distance: O(n²). new Sliding Window 10 · Grow and shrink a range to keep it valid. Best Time to Buy and Sell Stock Easy ★★★ #121 quant Kadane's running best Every buy/sell pair ⏱ O(n²) ▦ O(1) Track the cheapest price so far ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 3 edge cases · 5 testsPrices only fall: the best trade is no trade. Max difference with order (buy before sell) → one pass tracking the running minimum: O(n), O(1). It's Kadane's algorithm on daily price changes. new Longest Substring Without Repeating Characters Medium ★★★ #3 Sliding window Every start, extend until a repeat ⏱ O(n²) ▦ O(k) Sliding window with last-seen positions ⏱ O(n) ▦ O(k) O(n) from O(n²) · space O(k) 4 edge cases · 5 testsAll the same character: any single character is the answer. Longest substring with a constraint → sliding window; store last positions so the left edge jumps: O(n). new Longest Repeating Character Replacement Medium ★★★ #424 Sliding window Every substring, count replacements ⏱ O(n²) ▦ O(1) Sliding window keeping the top letter count ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 3 edge cases · 4 testsChange the middle A of 'BABB'-style windows: only one replacement allowed. Longest window that's 'almost uniform' → sliding window with condition length − maxFreq ≤ k: O(n). new Permutation in String Medium ★★★ #567 Sliding window Sort every window ⏱ O(n·m log m) ▦ O(m) Fixed-size window with letter counts ⏱ O(n) ▦ O(1) O(n) from O(n·m log m) · space O(1) 3 edge cases · 5 testsb and a are present but not next to each other. Anagram-of-pattern inside text → fixed-size sliding window with frequency counts: O(n). new Minimum Window Substring Hard ★★★ #76 Sliding window Check every substring ⏱ O(n²·k) ▦ O(k) Expand to cover, shrink to minimise ⏱ O(n + m) ▦ O(k) O(n + m) from O(n²·k) · space O(k) 2 edge cases · 5 testsThe whole string is the window. Shortest window covering a multiset → expand right until valid, shrink left while valid, with a 'missing' counter: O(n + m). new Sliding Window Maximum Hard ★★★ #239 quant Monotonic stack Scan every window ⏱ O(n·k) ▦ O(1) Monotonic deque of candidates ⏱ O(n) ▦ O(k) O(n) from O(n·k) · space O(k) 4 edge cases · 5 testsOne element, one window. Max of every window → monotonic deque (decreasing), front = max: O(n). new Find All Anagrams in a String Medium ★★★ #438 Sliding window Sort every window ⏱ O(n·m log m) ▦ O(m) Fixed window with counts ⏱ O(n) ▦ O(1) O(n) from O(n·m log m) · space O(1) 2 edge cases · 4 testsOverlapping matches all count. All anagram positions → fixed-size sliding window of letter counts: O(n). new Minimum Size Subarray Sum Medium ★★★ #209 quant Sliding window Every start, extend until the target ⏱ O(n²) ▦ O(1) Shrinking window ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 3 edge cases · 4 testsA single element already meets the target. Shortest subarray with sum ≥ target and positive values → variable sliding window: O(n). (With negatives: prefix sums + monotonic deque.) new Max Consecutive Ones III Medium ★★★ #1004 Sliding window Every start, count zeros ⏱ O(n²) ▦ O(1) Window with at most k zeros ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 3 edge cases · 5 testsNo flips and no ones. 'Flip at most k' → longest window containing at most k bad items: sliding window, O(n). new Fruit Into Baskets Medium ★★★ #904 Sliding window Every start ⏱ O(n²) ▦ O(1) Window with at most two types ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 2 edge cases · 5 testsBest run starts at index 1: [1, 2, 2]. Longest window with at most K distinct values → sliding window + count map: O(n). Here K = 2. new Stack 16 · Last in, first out: matching, undo and monotonic stacks. Valid Parentheses Easy ★★★ #20 Stack Repeatedly delete adjacent pairs ⏱ O(n²) ▦ O(n) Stack of open brackets ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 4 edge cases · 6 testsWrong partner type. Nested matching → stack of openers; closer must match the top: O(n). new Min Stack Medium ★★★ #155 Data structure design Scan for the min ⏱ O(n) ▦ O(n) Store the running minimum with each element ⏱ O(1) ▦ O(n) O(1) from O(n) · space O(n) 2 edge cases · 3 testsDuplicate minimums: popping one copy must keep the other as the min. O(1) min with a stack → store the running minimum alongside each entry (or a second min-stack). new Evaluate Reverse Polish Notation Medium ★★★ #150 quant Stack Rewrite the list in place ⏱ O(n²) ▦ O(n) Operand stack ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 2 edge cases · 5 testsTruncation toward zero: −3.5 → −3, not −4 (Python's // floors). Postfix evaluation → operand stack, pop right then left: O(n). new Generate Parentheses Medium ★★★ #22 Backtracking Generate all 2^(2n) strings, keep the valid ones ⏱ O(2²ⁿ·n) ▦ O(n) Backtracking with open/close counts ⏱ O(4ⁿ / sqrt(n)) ▦ O(n) O(4ⁿ / sqrt(n)) from O(2²ⁿ·n) · space O(n) 2 edge cases · 4 testsSmallest case. Generate all valid combinations → backtracking that only makes legal moves (prune early): O(Catalan(n)·n). new Daily Temperatures Medium ★★★ #739 quant Monotonic stack Scan forward from each day ⏱ O(n²) ▦ O(1) Monotonic stack of waiting days ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 3 edge cases · 5 testsStrictly rising: each day's answer is 1 except the last. Next greater element → monotonic decreasing stack of indexes: O(n). new Car Fleet Medium ★★★ #853 Monotonic stack Simulate time steps ⏱ O(n²·T) ▦ O(n) Sort by position, stack arrival times ⏱ O(n log n) ▦ O(n) O(n log n) from O(n²·T) · space O(n) 3 edge cases · 4 testsOne car is one fleet. Merging by catch-up → sort by position, compare arrival times from the front (monotonic stack): O(n log n). new Largest Rectangle in Histogram Hard ★★★ #84 quant Monotonic stack Expand around each bar ⏱ O(n²) ▦ O(1) Monotonic stack: pop when a shorter bar arrives ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 3 edge cases · 5 testsEqual bars: the whole histogram is one rectangle. Nearest smaller on both sides → monotonic increasing stack; area computed on pop: O(n). new Basic Calculator II Medium ★★★ #227 quant Stack Two passes over a token list ⏱ O(n²) ▦ O(n) Single pass with a stack of terms ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 3 edge cases · 5 testsSpaces are ignored; 3/2 truncates to 1. Precedence without parentheses → stack of signed terms; apply * and / immediately, sum at the end: O(n). new Decode String Medium ★★★ #394 Stack Expand the innermost bracket repeatedly ⏱ O(n·L) ▦ O(L) Stack of (prefix, count) ⏱ O(L) ▦ O(L) O(L) from O(n·L) · space O(L) 3 edge cases · 5 testsNested brackets: decode the inside first. Nested repetition → stack of (prefix, count) or recursion: O(output length). new Asteroid Collision Medium ★★★ #735 Stack Repeat passes until stable ⏱ O(n²) ▦ O(n) Stack of survivors ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 3 edge cases · 5 testsEqual sizes destroy each other. Cascading cancellations → stack of survivors, resolve against the top: O(n). new Online Stock Span Medium ★★★ #901 quant Monotonic stack Store all prices, scan back ⏱ O(n) ▦ O(n) Monotonic stack of (price, span) ⏱ O(1) ▦ O(n) O(1) from O(n) · space O(n) 2 edge cases · 3 testsEqual prices count toward the span. Streaming 'previous greater element' → monotonic stack storing absorbed spans: amortized O(1) per update. new Simplify Path Medium ★★★ #71 Stack Repeated string rewriting ⏱ O(n²) ▦ O(n) Stack of directory names ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 3 edge cases · 4 testsGoing up from the root stays at the root. Path normalisation → split and use a stack of names: O(n). new Basic Calculator Hard ★★★ #224 quant Stack Evaluate the innermost parentheses and substitute ⏱ O(n²) ▦ O(n) One pass with a stack of (result, sign) ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 5 edge cases · 7 testsSpaces anywhere must be ignored. Expression with + − and parentheses → running total + sign, and a stack of (total, sign) per open parenthesis. new Sum of Subarray Minimums Medium ★★★ #907 quant Monotonic stack Every subarray with a running minimum ⏱ O(n²) ▦ O(1) Count each element's reach with monotonic stacks ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 3 edge cases · 5 testsOne element: one subarray. Sum over subarrays of min/max → contribution technique: each element counts (i − prevSmaller) × (nextSmaller − i) times, found with monotonic stacks. new Remove K Digits Medium ★★★ #402 Monotonic stack Try every single removal, k times ⏱ O(k·n²) ▦ O(n) Greedy increasing stack ⏱ O(n) ▦ O(n) O(n) from O(k·n²) · space O(n) 3 edge cases · 5 testsRemoving the 1 leaves 0200: leading zeros are dropped. Smallest number after deleting k digits → monotonic increasing stack: pop bigger previous digits while k > 0, then trim the end and strip zeros. new Longest Valid Parentheses Hard ★★★ #32 Stack Every start with a running balance ⏱ O(n²) ▦ O(1) Stack of indices with a base ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 4 edge cases · 6 testsEmpty string. Longest balanced substring → stack of indices with a base sentinel (or DP on 'longest valid ending at i', or two counters left-to-right and right-to-left). new Binary Search 12 · Halve the search space each step, on indexes or on answers. Binary Search Easy ★★★ #704 Binary search Linear scan ⏱ O(n) ▦ O(1) Halve the search range ⏱ O(log n) ▦ O(1) O(log n) from O(n) · space O(1) 4 edge cases · 5 testsMissing value between two elements. Sorted + find → binary search with an invariant on [lo, hi]: O(log n). new Search a 2D Matrix Medium ★★★ #74 Binary search Scan every cell ⏱ O(m·n) ▦ O(1) Binary search the flattened matrix ⏱ O(log(m·n)) ▦ O(1) O(log(m·n)) from O(m·n) · space O(1) 4 edge cases · 5 testsFalls between two rows. Fully sorted 2-D grid → binary search on the virtual flattened array: O(log(mn)). new Koko Eating Bananas Medium ★★★ #875 quant Binary search on the answer Try every speed from 1 up ⏱ O(n·M) ▦ O(1) Binary search on the speed ⏱ O(n log M) ▦ O(1) O(n log M) from O(n·M) · space O(1) 3 edge cases · 5 testsh equals the number of piles: must finish the biggest pile in one hour. Minimise a parameter whose feasibility is monotonic → binary search on the answer: O(n log M). new Find Minimum in Rotated Sorted Array Medium ★★★ #153 Binary search Linear scan ⏱ O(n) ▦ O(1) Binary search against the right end ⏱ O(log n) ▦ O(1) O(log n) from O(n) · space O(1) 2 edge cases · 5 testsNot rotated (or rotated n times). Rotated sorted array → binary search comparing mid with the right end: O(log n). new Search in Rotated Sorted Array Medium ★★★ #33 Binary search Linear scan ⏱ O(n) ▦ O(1) Binary search on the sorted half ⏱ O(log n) ▦ O(1) O(log n) from O(n) · space O(1) 3 edge cases · 5 testsValue not present. Rotated sorted search → one half is always sorted; check if target is in it: O(log n). new Time Based Key-Value Store Medium ★★★ #981 quant Binary search Scan all versions ⏱ O(n) ▦ O(n) Per-key sorted list + binary search ⏱ O(log n) ▦ O(n) O(log n) from O(n) · space O(n) 2 edge cases · 3 testsQuery earlier than every stored timestamp. Versioned lookup 'as of time t' → per-key sorted timestamps + binary search (floor): O(log n) reads. new Median of Two Sorted Arrays Hard ★★★ #4 quant Binary search Merge, then take the middle ⏱ O(m + n) ▦ O(m + n) Binary search the partition ⏱ O(log(min(m, n))) ▦ O(1) O(log(min(m, n))) from O(m + n) · space O(1) 4 edge cases · 5 testsEven total: average the two middle values. Median / k-th of two sorted arrays → binary search the partition of the shorter array: O(log min(m, n)). new Find First and Last Position of Element Medium ★★★ #34 Binary search Linear scan ⏱ O(n) ▦ O(1) Two boundary binary searches ⏱ O(log n) ▦ O(1) O(log n) from O(n) · space O(1) 3 edge cases · 5 testsAbsent value. Range of equal values → lower_bound(target) and lower_bound(target + 1) − 1: O(log n). new Search Insert Position Easy ★★★ #35 Binary search Linear scan ⏱ O(n) ▦ O(1) Lower-bound binary search ⏱ O(log n) ▦ O(1) O(log n) from O(n) · space O(1) 3 edge cases · 4 testsBelongs between 1 and 3. Insert position = lower bound: binary search with half-open range: O(log n). new Find Peak Element Medium ★★★ #162 Binary search Linear scan for a descent ⏱ O(n) ▦ O(1) Climb uphill with binary search ⏱ O(log n) ▦ O(1) O(log n) from O(n) · space O(1) 4 edge cases · 5 testsTwo peaks: either index is accepted. Any local maximum → binary search on the slope (go uphill): O(log n). new Capacity to Ship Packages Within D Days Medium ★★★ #1011 quant Binary search on the answer Try capacities upward ⏱ O(n·S) ▦ O(1) Binary search on capacity ⏱ O(n log S) ▦ O(1) O(n log S) from O(n·S) · space O(1) 2 edge cases · 5 testsOne day per package: capacity must be the heaviest package. Minimum capacity to meet a deadline → binary search on the answer with a greedy feasibility check: O(n log S). new Split Array Largest Sum Hard ★★★ #410 quant Binary search on the answer Try every split recursively ⏱ O(nᵏ) ▦ O(k) Binary search the cap + greedy split ⏱ O(n log S) ▦ O(1) O(n log S) from O(nᵏ) · space O(1) 2 edge cases · 5 testsk equals the length: each element alone. Minimise the maximum → binary search the cap with a greedy feasibility check (same as Ship Packages): O(n log S). new Linked List 17 · Pointer surgery, dummy heads and fast/slow runners. Reverse Linked List Easy ★★★ #206 Linked-list pointer surgery Copy values to an array, rebuild ⏱ O(n) ▦ O(n) Iterative pointer reversal ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 2 edge cases · 4 testsEmpty list: return null. Reverse in place → three pointers prev/cur/next, save next before rewiring: O(n), O(1). new Merge Two Sorted Lists Easy ★★★ #21 Linked-list pointer surgery Collect, sort, rebuild ⏱ O((m+n) log(m+n)) ▦ O(m+n) Dummy head + splice the smaller node ⏱ O(m+n) ▦ O(1) O(m+n) from O((m+n) log(m+n)) · space O(1) 3 edge cases · 4 testsBoth empty. Merge sorted lists → dummy head + tail pointer splicing the smaller node: O(m + n), O(1). new Linked List Cycle Easy ★★★ #141 Fast & slow pointers Remember visited nodes ⏱ O(n) ▦ O(n) Floyd's tortoise and hare ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 4 edge cases · 5 testsTwo-node cycle back to the head. Cycle detection in O(1) space → Floyd's fast/slow pointers. new Reorder List Medium ★★★ #143 Linked-list pointer surgery Array of nodes, relink ⏱ O(n) ▦ O(n) Find middle, reverse second half, weave ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 3 edge cases · 4 testsEven length. Reorder from both ends in O(1) space → find middle + reverse second half + weave (three classic sub-routines). new Remove Nth Node From End of List Medium ★★★ #19 Fast & slow pointers Count, then walk to the node before ⏱ O(L) ▦ O(1) Two pointers n apart ⏱ O(L) ▦ O(1) O(L) from O(L) · space O(1) 3 edge cases · 4 testsRemoving the only node. k-th from the end in one pass → two pointers with a k-node gap and a dummy head. new Copy List with Random Pointer Medium ★★★ #138 Hash map lookup Copy nodes, then find each random by walking ⏱ O(n²) ▦ O(n) Old → new hash map ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 3 edge cases · 4 testsA node whose random points to itself. Deep copy of a graph-like structure → old→new hash map, two passes: O(n). (O(1) space: interleave clones.) new Add Two Numbers Medium ★★★ #2 quant Linked-list pointer surgery Convert to integers and back ⏱ O(m+n) ▦ O(m+n) Digit-by-digit with carry ⏱ O(max(m,n)) ▦ O(1) O(max(m,n)) from O(m+n) · space O(1) 2 edge cases · 4 testsDifferent lengths and a final carry creates a new digit. Big-number arithmetic on lists → simulate column addition with a carry: O(max(m, n)). new Find the Duplicate Number Medium ★★★ #287 quant Fast & slow pointers Hash set ⏱ O(n) ▦ O(n) Floyd's cycle detection on index → value ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 2 edge cases · 4 testsSmallest input. Duplicate in 1..n with O(1) space and no modification → Floyd's cycle detection on i → nums[i]. new Merge k Sorted Lists Hard ★★★ #23 quant Heap / top-k Merge one list at a time ⏱ O(k·N) ▦ O(1) Min-heap of current heads ⏱ O(N log k) ▦ O(k) O(N log k) from O(k·N) · space O(k) 3 edge cases · 4 testsNo lists at all. Merge k sorted streams → min-heap of k heads: O(N log k). (Divide-and-conquer pairing also gives O(N log k).) new Reverse Nodes in k-Group Hard ★★★ #25 Linked-list pointer surgery Collect values, reverse chunks ⏱ O(n) ▦ O(n) Reverse each full group in place ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 3 edge cases · 4 testsLeftover group of 2 (< k) is not reversed. Reverse in blocks → dummy + for each full group: locate kth, reverse k links, reconnect: O(n), O(1). new Linked List Cycle II Medium ★★★ #142 Fast & slow pointers Visited set ⏱ O(n) ▦ O(n) Floyd, then walk from head and meeting point ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 2 edge cases · 4 testsNo cycle. Cycle entrance → Floyd phase 1 to meet, phase 2 from head and meeting point: O(n), O(1). new Palindrome Linked List Easy ★★★ #234 Fast & slow pointers Copy to an array ⏱ O(n) ▦ O(n) Reverse the second half and compare ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 2 edge cases · 4 testsOdd length: the middle element pairs with itself. Palindrome on a singly linked list with O(1) space → middle (fast/slow) + reverse second half + compare. new Middle of the Linked List Easy ★★★ #876 Fast & slow pointers Count, then walk half ⏱ O(n) ▦ O(1) Fast & slow ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 2 edge cases · 3 testsEven length: return the second middle. Middle in one pass → slow/fast pointers. new Odd Even Linked List Medium ★★★ #328 Linked-list pointer surgery Collect nodes into two arrays ⏱ O(n) ▦ O(n) Two running tails ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 1 edge cases · 4 testsPositions matter, not values. Partition a list by position in place → two tails leapfrogging, then join: O(n), O(1). new Sort List Medium ★★★ #148 quant Linked-list pointer surgery Copy values, sort, write back ⏱ O(n log n) ▦ O(n) Merge sort on the list ⏱ O(n log n) ▦ O(log n) O(n log n) from O(n log n) · space O(log n) 2 edge cases · 4 testsEmpty list. Sort a linked list → merge sort (split with fast/slow, merge with a dummy): O(n log n). new Rotate List Medium ★★★ #61 Linked-list pointer surgery Move the tail to the front k times ⏱ O(n·k) ▦ O(1) Close into a ring, cut at n − k mod n ⏱ O(n) ▦ O(1) O(n) from O(n·k) · space O(1) 5 edge cases · 6 testsk is larger than the length: rotating by 4 on 3 nodes is the same as rotating by 1. Rotate a list → length n, k %= n, link tail to head, cut after node n − k. new Swap Nodes in Pairs Medium ★★★ #24 Linked-list pointer surgery Copy values, swap, rebuild ⏱ O(n) ▦ O(n) Relink with a dummy head ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 3 edge cases · 5 testsEmpty list. Pairwise relinking → dummy head + prev pointer; for each pair rewire prev→b→a→next. new Trees 25 · Recursion on left and right, plus level-by-level BFS. Invert Binary Tree Easy ★★★ #226 Tree DFS (recursion) BFS level by level ⏱ O(n) ▦ O(w) Recursive swap ⏱ O(n) ▦ O(h) O(n) from O(n) · space O(h) 2 edge cases · 4 testsEmpty tree. Transform every node → recursive DFS (or BFS): O(n) time, O(h) stack. new Maximum Depth of Binary Tree Easy ★★★ #104 Tree DFS (recursion) BFS counting levels ⏱ O(n) ▦ O(w) Recursive DFS ⏱ O(n) ▦ O(h) O(n) from O(n) · space O(h) 2 edge cases · 4 testsEmpty tree has depth 0. Aggregate over a tree → post-order DFS combining children: O(n). new Diameter of Binary Tree Easy ★★★ #543 Tree DFS (recursion) Height from every node ⏱ O(n²) ▦ O(h) One DFS returning height, tracking the best ⏱ O(n) ▦ O(h) O(n) from O(n²) · space O(h) 2 edge cases · 4 testsOne node: no edges. Longest path in a tree → post-order DFS returns height and updates a global best at each bend: O(n). new Balanced Binary Tree Easy ★★★ #110 Tree DFS (recursion) Height at every node ⏱ O(n²) ▦ O(h) Height DFS with early −1 ⏱ O(n) ▦ O(h) O(n) from O(n²) · space O(h) 3 edge cases · 4 testsLeft side is two levels deeper at the root. Check a property needing subtree heights → one post-order DFS returning height or a failure sentinel: O(n). new Same Tree Easy ★★★ #100 Tree DFS (recursion) Serialize and compare ⏱ O(n) ▦ O(n) Simultaneous DFS ⏱ O(n) ▦ O(h) O(n) from O(n) · space O(h) 3 edge cases · 4 testsSame values, different shape. Compare two trees → parallel recursion with null checks first: O(n). new Subtree of Another Tree Easy ★★★ #572 Tree DFS (recursion) Same-tree check at every node ⏱ O(m·n) ▦ O(h) Serialize and substring-search ⏱ O(m + n) ▦ O(m + n) O(m + n) from O(m·n) · space O(m + n) 2 edge cases · 4 testsMatching values but the candidate subtree has an extra node (0). Subtree match → Same Tree at each node (O(mn)) or serialize with null markers and substring-search (O(m + n) with KMP). new Lowest Common Ancestor of a BST Medium ★★★ #235 BST property Root-to-node paths ⏱ O(h) ▦ O(h) Walk down until p and q split ⏱ O(h) ▦ O(1) O(h) from O(h) · space O(1) 2 edge cases · 4 testsA node can be its own ancestor. LCA in a BST → walk from the root until p and q fall on different sides: O(h), O(1). new Binary Tree Level Order Traversal Medium ★★★ #102 Tree BFS (level order) DFS with a depth index ⏱ O(n) ▦ O(h) BFS with a queue, one level per round ⏱ O(n) ▦ O(w) O(n) from O(n) · space O(w) 2 edge cases · 4 testsEmpty tree: no levels. Level-by-level → BFS with a queue, processing len(queue) nodes per round: O(n). new Binary Tree Right Side View Medium ★★★ #199 Tree BFS (level order) Full level order, take last of each ⏱ O(n) ▦ O(n) DFS right-first, record the first node per depth ⏱ O(n) ▦ O(h) O(n) from O(n) · space O(h) 1 edge cases · 4 testsA left node is visible when the right side is shorter. One node per level → BFS (last per level) or right-first DFS (first per depth): O(n). new Count Good Nodes in Binary Tree Medium ★★★ #1448 Tree DFS (recursion) Store each path explicitly ⏱ O(n·h) ▦ O(h) DFS carrying the path maximum ⏱ O(n) ▦ O(h) O(n) from O(n·h) · space O(h) 2 edge cases · 4 testsEqual values still count as good. Property depending on ancestors → pass state down in DFS (here, the path max): O(n). new Validate Binary Search Tree Medium ★★★ #98 BST property Check each node against its whole subtrees ⏱ O(n²) ▦ O(h) DFS with (low, high) bounds ⏱ O(n) ▦ O(h) O(n) from O(n²) · space O(h) 4 edge cases · 5 tests4 is right of 5 but smaller. Validate BST → DFS with inherited (low, high) bounds, or in-order traversal must be strictly increasing: O(n). new Kth Smallest Element in a BST Medium ★★★ #230 BST property Collect all values and sort ⏱ O(n log n) ▦ O(n) Iterative in-order, stop at k ⏱ O(h + k) ▦ O(h) O(h + k) from O(n log n) · space O(h) 1 edge cases · 4 testsk equals the number of nodes: the maximum. Kth smallest in a BST → in-order traversal, stop at k: O(h + k). new Construct Binary Tree from Preorder and Inorder Medium ★★★ #105 Tree DFS (recursion) Recursive slicing with linear root search ⏱ O(n²) ▦ O(n²) Index map + preorder pointer ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 3 edge cases · 4 testsSingle node. Rebuild a tree from traversals → preorder gives roots, inorder gives left/right split; index map makes it O(n). new Binary Tree Maximum Path Sum Hard ★★★ #124 quant Tree DFS (recursion) Try every node as the top ⏱ O(n²) ▦ O(h) Post-order DFS: gain upward, best through each node ⏱ O(n) ▦ O(h) O(n) from O(n²) · space O(h) 2 edge cases · 5 testsAll negative: the best path is the single largest node. Max path anywhere in a tree → post-order DFS returning best single-branch gain, updating a global best at each bend: O(n). new Serialize and Deserialize Binary Tree Hard ★★★ #297 Tree DFS (recursion) Level order with nulls ⏱ O(n) ▦ O(n) Preorder with null markers (recursive) ⏱ O(n) ▦ O(n) O(n) from O(n) · space O(n) 2 edge cases · 3 testsEmpty tree must survive the round trip. Serialize a tree → preorder with null markers (or BFS with nulls); deserialize by consuming tokens in the same order: O(n). new Symmetric Tree Easy ★★★ #101 Tree DFS (recursion) Invert a copy and compare ⏱ O(n) ▦ O(n) Mirror comparison of two pointers ⏱ O(n) ▦ O(h) O(n) from O(n) · space O(h) 1 edge cases · 4 testsSame values, but both 3s are on the right: not mirrored. Mirror check → compare two subtrees crosswise (outer/inner pairs): O(n). new Lowest Common Ancestor of a Binary Tree Medium ★★★ #236 Tree DFS (recursion) Parent pointers + ancestor set ⏱ O(n) ▦ O(n) Single recursive search ⏱ O(n) ▦ O(h) O(n) from O(n) · space O(h) 2 edge cases · 4 testsp is an ancestor of q. LCA in a general binary tree → post-order search returning found nodes; first node with hits on both sides wins: O(n). new Binary Tree Zigzag Level Order Traversal Medium ★★★ #103 Tree BFS (level order) Level order, then reverse odd levels ⏱ O(n) ▦ O(n) BFS writing into a deque per level ⏱ O(n) ▦ O(w) O(n) from O(n) · space O(w) 2 edge cases · 4 testsEmpty tree: no levels. Alternating level order → BFS with a per-level deque, flipping the insert side: O(n). new Flatten Binary Tree to Linked List Medium ★★★ #114 Tree DFS (recursion) Collect preorder, relink ⏱ O(n) ▦ O(n) Morris-style rewiring ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 2 edge cases · 4 testsEmpty tree. In-place preorder flattening → for each node, splice right subtree after the left subtree's rightmost node (Morris-style): O(n), O(1). new All Nodes Distance K in Binary Tree Medium ★★★ #863 Graph BFS / DFS Distance from target to every node ⏱ O(n²) ▦ O(h) Add parent links, BFS k steps ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 3 edge cases · 4 testsNothing that far away. Distance in a tree including upward moves → add parent pointers, BFS from the target: O(n). new Convert Sorted Array to Binary Search Tree Easy ★★★ #108 Tree DFS (recursion) Recursive slicing ⏱ O(n log n) ▦ O(n) Recursive build on index ranges ⏱ O(n) ▦ O(log n) O(n) from O(n log n) · space O(log n) 2 edge cases · 4 testsEven length: the left middle becomes the root. Sorted array → balanced BST by taking the middle as root recursively: O(n). new Binary Tree Inorder Traversal Easy ★★★ #94 Tree DFS (recursion) Recursive ⏱ O(n) ▦ O(h) Iterative with an explicit stack ⏱ O(n) ▦ O(h) O(n) from O(n) · space O(h) 1 edge cases · 4 testsA BST comes out sorted. Iterative in-order → stack: dive left, pop & visit, go right: O(n), O(h). new Path Sum II Medium ★★★ #113 Backtracking List every root-to-leaf path, then filter ⏱ O(n·h) ▦ O(n·h) Backtracking with a running remainder ⏱ O(n + P·h) ▦ O(h) O(n + P·h) from O(n·h) · space O(h) 4 edge cases · 6 testsThe root alone sums to 1 but is not a leaf: paths must end at a leaf. All root-to-leaf paths with a property → DFS + backtracking with one shared path; copy it only when a leaf matches. new House Robber III Medium ★★★ #337 Tree DFS (recursion) Plain recursion: rob this node or not ⏱ O(1.62ⁿ) on a chain ▦ O(h) Post-order DP returning (rob, skip) ⏱ O(n) ▦ O(h) O(n) from O(1.62ⁿ) on a chain · space O(h) 3 edge cases · 6 testsOne house: rob it. DP on a tree with a take/skip choice → post-order DFS returning a (take, skip) pair per node. new Maximum Width of Binary Tree Medium ★★★ #662 Tree BFS (level order) Materialise every level with null placeholders ⏱ O(2^h) ▦ O(2^h) BFS with heap-style positions ⏱ O(n) ▦ O(w) O(n) from O(2^h) · space O(w) 2 edge cases · 5 testsThe gaps under missing nodes still count: positions 0 and 6 on the last level give width 7. Width with gaps → BFS carrying heap indices (2p, 2p+1); width = last − first + 1, renormalising each level. new Tries 6 · Prefix trees for words and autocomplete. Implement Trie (Prefix Tree) Medium ★★★ #208 Trie (prefix tree) List of words ⏱ O(N·L) ▦ O(N·L) Tree of character nodes ⏱ O(L) ▦ O(N·L) O(L) from O(N·L) · space O(N·L) 2 edge cases · 3 testsEmpty trie: nothing found. Prefix queries → trie: insert/search/startsWith in O(L) each. new Design Add and Search Words Medium ★★★ #211 Trie (prefix tree) Regex-style scan of all words ⏱ O(N·L) ▦ O(N·L) Trie + DFS on wildcards ⏱ O(L) add, O(26ᵈ·L) search ▦ O(N·L) O(L) add, O(26ᵈ·L) search from O(N·L) · space O(N·L) 2 edge cases · 3 testsA dot still needs exactly one letter. Wildcard search over a dictionary → trie + DFS branching at wildcards. new Word Search II Hard ★★★ #212 Trie (prefix tree) Word Search for each word ⏱ O(W·m·n·4ᴸ) ▦ O(L) Trie of words + one DFS over the board ⏱ O(m·n·4ᴸ) ▦ O(W·L) O(m·n·4ᴸ) from O(W·m·n·4ᴸ) · space O(W·L) 3 edge cases · 4 testsReusing a cell isn't allowed. Many words on a grid → trie of words + backtracking DFS with pruning (remove found words/branches). new Search Suggestions System Medium ★★★ #1268 Binary search Filter all products per prefix ⏱ O(L·n·m log n) ▦ O(n) Sort once + binary search each prefix ⏱ O(n log n + L log n) ▦ O(1) O(n log n + L log n) from O(L·n·m log n) · space O(1) 1 edge cases · 4 testsNo product matches: every step returns an empty list. Autocomplete top-k lexicographic → sort + binary search (lower bound) per prefix, or a trie storing top 3 at each node. new Replace Words Medium ★★★ #648 Trie (prefix tree) Check every root for every word ⏱ O(W·D·L) ▦ O(S) Trie of roots, stop at the first root end ⏱ O(R + S) ▦ O(R) O(R + S) from O(W·D·L) · space O(R) 3 edge cases · 5 testsTwo roots match 'cattle': the shorter one wins, whatever the dictionary order. Shortest prefix from a dictionary → trie of roots with end markers; walk each word and stop at the first end. new Maximum XOR of Two Numbers in an Array Medium ★★★ #421 quant Trie (prefix tree) Try every pair ⏱ O(n²) ▦ O(1) Binary trie, greedy opposite bit ⏱ O(31·n) ▦ O(31·n) O(31·n) from O(n²) · space O(31·n) 2 edge cases · 5 testsOne number: the only pair is the number with itself, and x XOR x = 0. Maximize XOR of a pair → binary trie on bits from the top; greedily take the opposite bit at each level (or the prefix-set trick). new Heap / Priority Queue 11 · Always grab the smallest (or largest) next item. Kth Largest Element in a Stream Easy ★★★ #703 quant Heap / top-k Sorted list ⏱ O(n) ▦ O(n) Min-heap of size k ⏱ O(log k) ▦ O(k) O(log k) from O(n) · space O(k) 2 edge cases · 3 testsStarts empty; k = 1 tracks the maximum. Kth largest in a stream → size-k min-heap; the top is the answer: O(log k) per add. new Last Stone Weight Easy ★★★ #1046 Heap / top-k Sort every turn ⏱ O(n² log n) ▦ O(1) Max-heap ⏱ O(n log n) ▦ O(n) O(n log n) from O(n² log n) · space O(n) 2 edge cases · 4 testsOne stone: nothing to smash. Repeatedly take the largest items → max-heap (negated min-heap in Python): O(n log n). new K Closest Points to Origin Medium ★★★ #973 quant Heap / top-k Sort by distance ⏱ O(n log n) ▦ O(n) Max-heap of size k ⏱ O(n log k) ▦ O(k) O(n log k) from O(n log n) · space O(k) 2 edge cases · 4 testsk equals the number of points. k smallest by a key → max-heap of size k (O(n log k)) or quickselect (O(n) average). new Kth Largest Element in an Array Medium ★★★ #215 quant Heap / top-k Sort ⏱ O(n log n) ▦ O(n) Size-k min-heap ⏱ O(n log k) ▦ O(k) O(n log k) from O(n log n) · space O(k) 2 edge cases · 4 testsDuplicates count separately. Kth largest → size-k min-heap O(n log k), or quickselect O(n) average. new Task Scheduler Medium ★★★ #621 Greedy Simulate with a max-heap and cooldown queue ⏱ O(T log 26) ▦ O(26) Count the most frequent task's frames ⏱ O(T) ▦ O(1) O(T) from O(T log 26) · space O(1) 3 edge cases · 4 testsEnough variety: no idle time needed. Cooldown scheduling → frame count from the most frequent task: max(T, (f − 1)(n + 1) + ties), O(T); or simulate with a max-heap. new Design Twitter Medium ★★★ #355 Heap / top-k Global tweet list, filter on read ⏱ O(T) ▦ O(T + F) Per-user timelines + k-way merge with a heap ⏱ O(F + 10·log F) ▦ O(T + F) O(F + 10·log F) from O(T) · space O(T + F) 2 edge cases · 3 testsFollowing yourself must not duplicate tweets; no tweets yet. News feed = merge the newest items of k sorted per-user timelines with a heap, stop at 10 (pull model). new Find Median from Data Stream Hard ★★★ #295 quant Heap / top-k Keep a sorted list ⏱ O(n) ▦ O(n) Two heaps (low max-heap, high min-heap) ⏱ O(log n) ▦ O(n) O(log n) from O(n) · space O(n) 2 edge cases · 3 testsOne number is its own median. Running median → two heaps (max-heap low, min-heap high), balanced: O(log n) add, O(1) query. new Top K Frequent Words Medium ★★★ #692 Heap / top-k Count and sort ⏱ O(n log n) ▦ O(n) Size-k heap with a tie-aware comparator ⏱ O(n log k) ▦ O(n) O(n log k) from O(n log n) · space O(n) 1 edge cases · 4 testsAll tied: purely alphabetical. Top-k with tie-breaks → counts + size-k heap whose comparator puts the eviction candidate on top: O(n log k). new Reorganize String Medium ★★★ #767 Heap / top-k Try permutations ⏱ O(n!·n) ▦ O(n) Greedy max-heap, holding back the last letter ⏱ O(n log k) ▦ O(k) O(n log k) from O(n!·n) · space O(k) 2 edge cases · 4 testsA letter appearing more than ⌈n/2⌉ times makes it impossible. Separate equal neighbours → greedy max-heap of counts, holding the last-used letter out for one turn: O(n log k). new IPO (Maximize Capital) Hard ★★★ #502 quant Heap / top-k Scan all projects each round ⏱ O(k·n) ▦ O(n) Sort by capital + max-heap of affordable profits ⏱ O(n log n + k log n) ▦ O(n) O(n log n + k log n) from O(k·n) · space O(n) 2 edge cases · 4 testsNothing is affordable: capital stays at 0. Greedy with unlocking thresholds → sort by threshold + max-heap of unlocked values: O((n + k) log n). new Kth Smallest Element in a Sorted Matrix Medium ★★★ #378 quant Heap / top-k Flatten and sort ⏱ O(n² log n) ▦ O(n²) K-way merge with a min-heap ⏱ O(n + k log n) ▦ O(n) O(n + k log n) from O(n² log n) · space O(n) 3 edge cases · 5 testsA 1 × 1 matrix. Kth smallest across sorted rows → k-way merge with a min-heap of row heads (or binary search on the value with an O(n) staircase count). new Backtracking 11 · Build choices step by step and undo dead ends. Subsets Medium ★★★ #78 Backtracking Bitmask enumeration ⏱ O(n·2ⁿ) ▦ O(n) Backtracking: include or skip from each start ⏱ O(n·2ⁿ) ▦ O(n) O(n·2ⁿ) from O(n·2ⁿ) · space O(n) 2 edge cases · 4 testsThe empty set is always a subset. All subsets → backtracking with a start index (or bitmasks): O(n·2ⁿ), the size of the output. new Combination Sum Medium ★★★ #39 Backtracking Generate all multisets up to target, deduplicate ⏱ Exponential ▦ O(target) Backtracking with a start index (reuse allowed) ⏱ O(N^(T/m)) ▦ O(T/m) O(N^(T/m)) from Exponential · space O(T/m) 2 edge cases · 4 testsNo combination reaches an odd target with only 2s. Combinations with reuse → backtracking with start index i (recurse on i, not i + 1), sort to prune: exponential but output-sensitive. new Combination Sum II Medium ★★★ #40 Backtracking All subsets, deduplicate ⏱ O(n·2ⁿ) ▦ O(2ⁿ) Sorted backtracking, skip equal siblings ⏱ O(2ⁿ) ▦ O(n) O(2ⁿ) from O(n·2ⁿ) · space O(n) 2 edge cases · 4 testsDuplicate 2s may appear in one combination but the combination is listed once. Combinations without reuse and with duplicate inputs → sort + skip equal siblings at the same level + recurse with i + 1. new Permutations Medium ★★★ #46 Backtracking Insert each new element at every position ⏱ O(n·n!) ▦ O(n·n!) Backtracking with a used[] mask ⏱ O(n·n!) ▦ O(n) O(n·n!) from O(n·n!) · space O(n) 1 edge cases · 3 testsOne element, one permutation. All orderings → backtracking with a used set: O(n·n!). new Subsets II Medium ★★★ #90 Backtracking All subsets into a set ⏱ O(n·2ⁿ) ▦ O(n·2ⁿ) Sorted backtracking, skip equal siblings ⏱ O(n·2ⁿ) ▦ O(n) O(n·2ⁿ) from O(n·2ⁿ) · space O(n) 2 edge cases · 4 testsAll duplicates: only counts differ. Unique subsets with duplicates → sort + backtracking with i > start and nums[i] == nums[i−1] skip. new Word Search Medium ★★★ #79 Backtracking DFS with a visited set per start ⏱ O(m·n·4ᴸ·L) ▦ O(L²) In-place marking backtracking ⏱ O(m·n·4ᴸ) ▦ O(L) O(m·n·4ᴸ) from O(m·n·4ᴸ·L) · space O(L) 3 edge cases · 5 testsWould need to reuse the B cell. Path search on a grid → backtracking DFS with in-place visited marking: O(m·n·3^L). new Palindrome Partitioning Medium ★★★ #131 Backtracking Every cut pattern ⏱ O(n·2ⁿ) ▦ O(n) Backtracking on palindromic prefixes ⏱ O(n·2ⁿ) ▦ O(n) O(n·2ⁿ) from O(n·2ⁿ) · space O(n) 1 edge cases · 4 testsThe whole string can be one piece. All palindrome partitions → backtracking over palindromic prefixes (precompute an isPal table for speed). new Letter Combinations of a Phone Number Medium ★★★ #17 Backtracking Iterative product ⏱ O(4ⁿ·n) ▦ O(4ⁿ·n) Backtracking one digit at a time ⏱ O(4ⁿ·n) ▦ O(n) O(4ⁿ·n) from O(4ⁿ·n) · space O(n) 2 edge cases · 4 testsNo digits: no combinations (not one empty string). Cartesian product of choices → backtracking one position at a time: O(4ⁿ·n). new N-Queens Hard ★★★ #51 quant Backtracking Try every permutation of columns ⏱ O(n!·n) ▦ O(n) Row-by-row backtracking with column/diagonal sets ⏱ O(n!) ▦ O(n) O(n!) from O(n!·n) · space O(n) 2 edge cases · 4 testsA 1 × 1 board has one solution. Constraint placement → row-by-row backtracking with column, r − c and r + c sets for O(1) safety checks. new Combinations Medium ★★★ #77 quant Backtracking Filter all subsets by size ⏱ O(n·2ⁿ) ▦ O(n) Backtracking with pruning ⏱ O(k·C(n,k)) ▦ O(k) O(k·C(n,k)) from O(n·2ⁿ) · space O(k) 1 edge cases · 4 testsk = n: only one combination. Choose k of n → backtracking in increasing order with an upper-bound prune: O(k·C(n, k)). new Permutations II Medium ★★★ #47 Backtracking All permutations into a set ⏱ O(n·n!) ▦ O(n·n!) Sorted backtracking with a duplicate rule ⏱ O(n·n!) ▦ O(n) O(n·n!) from O(n·n!) · space O(n) 2 edge cases · 3 testsNo duplicates: all n! orderings. Unique permutations → sort + used[] + skip nums[i] == nums[i−1] and not used[i−1]. new Graphs 19 · BFS, DFS, union-find and topological order on networks and grids. Number of Islands Medium ★★★ #200 Graph BFS / DFS Grow each island one ring per full scan ⏱ O((m·n)²) ▦ O(m·n) DFS that sinks each island ⏱ O(m·n) ▦ O(m·n) O(m·n) from O((m·n)²) · space O(m·n) 3 edge cases · 5 testsNo land at all: zero islands. Count connected components in a grid → scan + DFS/BFS flood fill that marks visited cells: O(m·n). new Clone Graph Medium ★★★ #133 Graph BFS / DFS Two passes: copy nodes, then wire edges ⏱ O(V+E) ▦ O(V) DFS with an original → copy map ⏱ O(V+E) ▦ O(V) O(V+E) from O(V+E) · space O(V) 3 edge cases · 5 testsOne node with no neighbours. Deep copy of a graph with cycles → DFS/BFS plus an original→clone hash map: O(V+E). new Max Area of Island Medium ★★★ #695 Graph BFS / DFS Measure from every land cell ⏱ O((m·n)²) ▦ O(m·n) DFS that returns the island's size ⏱ O(m·n) ▦ O(m·n) O(m·n) from O((m·n)²) · space O(m·n) 3 edge cases · 4 testsNo land: area 0. Largest connected component in a grid → DFS that returns component size, marking visited: O(m·n). new Pacific Atlantic Water Flow Medium ★★★ #417 Graph BFS / DFS Search from every cell ⏱ O((m·n)²) ▦ O(m·n) Reverse flow from each ocean ⏱ O(m·n) ▦ O(m·n) O(m·n) from O((m·n)²) · space O(m·n) 2 edge cases · 4 testsA single cell touches all four edges, so both oceans. "Which cells reach X" with many sources → search backwards from X (multi-source, reversed edges): O(m·n). new Surrounded Regions Medium ★★★ #130 Graph BFS / DFS Check each O's region separately ⏱ O((m·n)²) ▦ O(m·n) Rescue border-connected O's first ⏱ O(m·n) ▦ O(m·n) O(m·n) from O((m·n)²) · space O(m·n) 3 edge cases · 5 testsEvery O touches the border, so nothing is captured. "Enclosed" regions → invert the problem: flood from the border to find what is NOT enclosed, then flip the rest: O(m·n). new Rotting Oranges Medium ★★★ #994 Graph BFS / DFS Simulate minute by minute ⏱ O((m·n)²) ▦ O(m·n) Multi-source BFS by levels ⏱ O(m·n) ▦ O(m·n) O(m·n) from O((m·n)²) · space O(m·n) 4 edge cases · 5 testsThe orange in the bottom-left corner has no neighbours that can rot it. Simultaneous spread from many sources, measured in steps → multi-source BFS by layers: O(m·n). new Walls and Gates Medium ★★★ #286 Graph BFS / DFS BFS from every room ⏱ O((m·n)²) ▦ O(m·n) Multi-source BFS from all gates ⏱ O(m·n) ▦ O(m·n) O(m·n) from O((m·n)²) · space O(m·n) 2 edge cases · 5 testsNo gate anywhere: the room stays at infinity. Nearest of many sources on an unweighted grid → multi-source BFS from all sources: O(m·n). new Course Schedule Medium ★★★ #207 Topological sort DFS from every course looking for a cycle ⏱ O(V·(V+E)) ▦ O(V+E) Kahn's algorithm (topological sort) ⏱ O(V+E) ▦ O(V+E) O(V+E) from O(V·(V+E)) · space O(V+E) 3 edge cases · 5 testsEach course needs the other first: a cycle. Dependencies + "is an order possible?" → topological sort / cycle detection: O(V+E). new Course Schedule II Medium ★★★ #210 Topological sort Repeatedly scan for a takeable course ⏱ O(V·(V+E)) ▦ O(V+E) Kahn's algorithm, recording the order ⏱ O(V+E) ▦ O(V+E) O(V+E) from O(V·(V+E)) · space O(V+E) 2 edge cases · 5 testsA cycle makes any order impossible: return []. Produce a dependency-respecting order → Kahn's topological sort (or reverse DFS post-order): O(V+E). new Redundant Connection Medium ★★★ #684 Union–find DFS before adding each edge ⏱ O(E·(V+E)) ▦ O(V+E) Union-find ⏱ O(E·α(V)) ▦ O(V) O(E·α(V)) from O(E·(V+E)) · space O(V) 2 edge cases · 4 testsReturn the last edge that is on the cycle, not the last edge overall. Detect the edge that creates a cycle in an undirected graph → union-find over edges in order: O(E·α(V)). new Number of Connected Components Medium ★★★ #323 Union–find Label propagation ⏱ O(V·E) ▦ O(V) Union-find with a running count ⏱ O(V + E·α(V)) ▦ O(V) O(V + E·α(V)) from O(V·E) · space O(V) 2 edge cases · 5 testsNo edges: every node is its own component. Count connected components → union-find with a counter (or DFS from each unvisited node): near O(V+E). new Graph Valid Tree Medium ★★★ #261 Union–find DFS before each edge, then a reachability check ⏱ O(E·(V+E)) ▦ O(V+E) Edge count + union-find ⏱ O(V + E·α(V)) ▦ O(V) O(V + E·α(V)) from O(E·(V+E)) · space O(V) 4 edge cases · 5 tests1–2–3 forms a cycle. Tree check → exactly n − 1 edges and no cycle (union-find): O(V + E·α). new Word Ladder Hard ★★★ #127 Graph BFS / DFS BFS comparing against every word ⏱ O(N²·L) ▦ O(N) BFS generating one-letter mutations ⏱ O(N·L²·26) ▦ O(N·L) O(N·L²·26) from O(N²·L) · space O(N·L) 3 edge cases · 5 testsendWord is not in the list, so it can never be reached. Shortest transformation sequence → BFS on an implicit graph; generate neighbours by mutation + hash set: O(N·L²·26). new Accounts Merge Medium ★★★ #721 quant Union–find Merge pairs until nothing changes ⏱ O(n³·k) ▦ O(n·k) Union-find over emails ⏱ O(N·α(N) + N log N) ▦ O(N) O(N·α(N) + N log N) from O(n³·k) · space O(N) 3 edge cases · 5 testsAccounts 1 and 2 share nothing directly but are linked through account 3. Merge records that share any key, transitively → union-find (or DFS) over the keys: ~O(N log N) with sorting. new Evaluate Division Medium ★★★ #399 quant Union–find DFS per query ⏱ O(Q·(V+E)) ▦ O(V+E) Weighted union-find ⏱ O((E+Q)·α(V)) ▦ O(V) O((E+Q)·α(V)) from O(Q·(V+E)) · space O(V) 1 edge cases · 4 testsa and d are in different groups: no chain of known ratios connects them. Chained ratios / conversions → weighted graph: DFS per query, or weighted union-find for many queries. new Flood Fill Easy ★★★ #733 Graph BFS / DFS Spread until stable ⏱ O((m·n)²) ▦ O(m·n) DFS from the start pixel ⏱ O(m·n) ▦ O(m·n) O(m·n) from O((m·n)²) · space O(m·n) 2 edge cases · 4 testsNew colour equals the old colour: nothing changes (a naive DFS would loop forever). Paint-bucket fill → DFS/BFS from the start cell over same-valued neighbours: O(m·n). new Shortest Path in Binary Matrix Medium ★★★ #1091 Graph BFS / DFS Relax distances until nothing changes ⏱ O(n⁴) ▦ O(n²) BFS from the start ⏱ O(n²) ▦ O(n²) O(n²) from O(n⁴) · space O(n²) 4 edge cases · 6 testsThe start cell is blocked. Shortest path, unweighted grid → BFS from the start; the first time the target is popped gives the answer. new Is Graph Bipartite? Medium ★★★ #785 Graph BFS / DFS Try every two-colouring ⏱ O(2ⁿ·E) ▦ O(n) BFS two-colouring per component ⏱ O(V + E) ▦ O(V) O(V + E) from O(2ⁿ·E) · space O(V) 4 edge cases · 6 testsA disconnected graph: the isolated node 0 can go in either group. Can it be split into two sides with no edge inside a side → BFS/DFS two-colouring; a same-colour edge (odd cycle) means no. new Minimum Height Trees Medium ★★★ #310 Topological sort BFS from every node ⏱ O(n²) ▦ O(n) Peel leaves layer by layer ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 3 edge cases · 5 testsA single node with no edges is its own best root. Centre of a tree / roots of minimum height → trim leaves layer by layer (topological peel); the last one or two nodes remain. new Advanced Graphs 8 · Weighted shortest paths and minimum spanning trees. Network Delay Time Medium ★★★ #743 quant Dijkstra shortest path Bellman–Ford ⏱ O(V·E) ▦ O(V) Dijkstra with a min-heap ⏱ O(E log V) ▦ O(V+E) O(E log V) from O(V·E) · space O(V+E) 3 edge cases · 5 testsEdges are one-way: node 1 can never hear from node 2. Single-source shortest paths, non-negative weights → Dijkstra with a heap: O(E log V); answer = max distance. new Reconstruct Itinerary Hard ★★★ #332 Graph BFS / DFS Backtracking in lexical order ⏱ O(Eᵈ) worst case ▦ O(E) Hierholzer's algorithm (Eulerian path) ⏱ O(E log E) ▦ O(E) O(E log E) from O(Eᵈ) worst case · space O(E) 2 edge cases · 4 testsThe alphabetically first choice (KUL) is a dead end; you must fly to NRT first to use every ticket. Use every edge exactly once → Eulerian path via Hierholzer (post-order DFS), with smallest-first ordering: O(E log E). new Min Cost to Connect All Points Medium ★★★ #1584 Minimum spanning tree Kruskal on all pairs ⏱ O(n² log n) ▦ O(n²) Prim's algorithm with an array (dense graph) ⏱ O(n²) ▦ O(n) O(n²) from O(n² log n) · space O(n) 2 edge cases · 5 testsA single point needs no connections. Connect everything at minimum total cost → minimum spanning tree; complete graph → array-based Prim O(n²). new Swim in Rising Water Hard ★★★ #778 Dijkstra shortest path Try every time t ⏱ O(n⁴) ▦ O(n²) Dijkstra on the bottleneck (min-heap) ⏱ O(n² log n) ▦ O(n²) O(n² log n) from O(n⁴) · space O(n²) 2 edge cases · 4 testsStart is the end: no waiting needed. Minimise the maximum along a path (bottleneck) → Dijkstra with max instead of +, or binary search + BFS: O(n² log n). new Alien Dictionary Hard ★★★ #269 Topological sort Try every permutation of the letters ⏱ O(k!·N·L) ▦ O(k) Build letter edges, then topological sort ⏱ O(C) ▦ O(1) O(C) from O(k!·N·L) · space O(1) 3 edge cases · 5 testsz < x and x < z at the same time: a cycle, so no order exists. Recover an ordering from pairwise rules → build a DAG from adjacent comparisons, then topological sort: O(total chars). new Cheapest Flights Within K Stops Medium ★★★ #787 quant Dijkstra shortest path DFS over all routes with at most k + 1 flights ⏱ O(n^(k+1)) ▦ O(n) Bellman–Ford limited to k + 1 rounds ⏱ O(k·E) ▦ O(n) O(k·E) from O(n^(k+1)) · space O(n) 2 edge cases · 4 testsk = 0 allows direct flights only, so the cheaper connection is not allowed. Shortest path with a hop limit → Bellman–Ford for k + 1 rounds with a snapshot (or BFS by levels): O(k·E). new Path With Minimum Effort Medium ★★★ #1631 Dijkstra shortest path Try each candidate effort ⏱ O((m·n)²) ▦ O(m·n) Dijkstra on the max-step cost ⏱ O(m·n·log(m·n)) ▦ O(m·n) O(m·n·log(m·n)) from O((m·n)²) · space O(m·n) 2 edge cases · 4 testsA winding route along the 1's never changes height. Minimise the worst edge on a path → Dijkstra with max (bottleneck), or binary search + BFS, or union-find by edge weight. new Critical Connections in a Network Hard ★★★ #1192 quant Graph BFS / DFS Remove each edge and test connectivity ⏱ O(E·(V+E)) ▦ O(V+E) Tarjan's bridge-finding (low-link) ⏱ O(V+E) ▦ O(V+E) O(V+E) from O(E·(V+E)) · space O(V+E) 3 edge cases · 5 testsA cycle has no bridges: every edge has a backup route. Bridges / single points of failure → Tarjan's low-link DFS: edge (u, v) is a bridge iff low[v] > disc[u]; O(V+E). new 1-D Dynamic Programming 15 · Reuse answers to smaller prefixes. Climbing Stairs Easy ★★★ #70 1-D dynamic programming Plain recursion ⏱ O(2ⁿ) ▦ O(n) Bottom-up with two variables ⏱ O(n) ▦ O(1) O(n) from O(2ⁿ) · space O(1) 2 edge cases · 5 testsOne step: only one way. Count ways where the last choice splits the problem → 1-D DP recurrence (here Fibonacci): O(n) time, O(1) space. new Min Cost Climbing Stairs Easy ★★★ #746 1-D dynamic programming Recursion from each start ⏱ O(2ⁿ) ▦ O(n) Bottom-up, two variables ⏱ O(n) ▦ O(1) O(n) from O(2ⁿ) · space O(1) 3 edge cases · 5 testsTwo stairs: pay once and jump to the top. Minimum cost with 1- or 2-step moves → DP: reach(i) = min(reach(i − 1) + cost[i − 1], reach(i − 2) + cost[i − 2]). new House Robber Medium ★★★ #198 1-D dynamic programming Include-or-skip recursion ⏱ O(2ⁿ) ▦ O(n) Rolling DP ⏱ O(n) ▦ O(1) O(n) from O(2ⁿ) · space O(1) 3 edge cases · 5 testsA single house: take it. Pick non-adjacent items to maximise a sum → 1-D DP take/skip: O(n) time, O(1) space. new House Robber II Medium ★★★ #213 1-D dynamic programming Recursion remembering whether house 0 was taken ⏱ O(2ⁿ) ▦ O(n) Two linear passes ⏱ O(n) ▦ O(1) O(n) from O(2ⁿ) · space O(1) 3 edge cases · 5 testsOne house is not its own neighbour: take it. Circular adjacency → break the circle into two linear cases and reuse the line DP: O(n). new Longest Palindromic Substring Medium ★★★ #5 Two pointers Check every substring ⏱ O(n³) ▦ O(1) Expand around every centre ⏱ O(n²) ▦ O(1) O(n²) from O(n³) · space O(1) 3 edge cases · 5 testsA single letter is a palindrome. Longest palindromic substring → expand around 2n − 1 centres: O(n²) time, O(1) space (Manacher is O(n)). new Palindromic Substrings Medium ★★★ #647 Two pointers Test every substring ⏱ O(n³) ▦ O(1) Expand around centres and count ⏱ O(n²) ▦ O(1) O(n²) from O(n³) · space O(1) 2 edge cases · 4 testsOne letter, one palindrome. Count palindromic substrings → expand around 2n − 1 centres, counting each match: O(n²). new Decode Ways Medium ★★★ #91 1-D dynamic programming Recursion on one or two digits ⏱ O(2ⁿ) ▦ O(n) Rolling DP over prefixes ⏱ O(n) ▦ O(1) O(n) from O(2ⁿ) · space O(1) 4 edge cases · 7 testsA leading 0 cannot be decoded, and "06" is not a valid code. Count segmentations with local validity rules → 1-D DP over prefixes, like Climbing Stairs with conditions: O(n). new Coin Change Medium ★★★ #322 quant 1-D dynamic programming Recursion over the last coin ⏱ O(k^(a/m)) ▦ O(a/m) Bottom-up DP over amounts ⏱ O(a·k) ▦ O(a) O(a·k) from O(k^(a/m)) · space O(a) 3 edge cases · 5 testsAn odd amount cannot be made from 2's. Minimum items to hit a target with unlimited reuse → unbounded-knapsack DP over amounts: O(amount·coins). new Maximum Product Subarray Medium ★★★ #152 quant Kadane's running best Every subarray's product ⏱ O(n²) ▦ O(1) Track max and min ending here ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 3 edge cases · 5 testsZero beats every negative product. Max product subarray → Kadane variant tracking both max and min ending here (sign flips): O(n). new Word Break Medium ★★★ #139 1-D dynamic programming Recursion on every prefix ⏱ O(2ⁿ) ▦ O(n) DP over prefixes ⏱ O(n·L²) ▦ O(n) O(n·L²) from O(2ⁿ) · space O(n) 3 edge cases · 5 testsWords can be reused (apple twice). Can a string be segmented into dictionary words → prefix DP (or memoised DFS); bound the look-back by the longest word. new Longest Increasing Subsequence Medium ★★★ #300 quant 1-D dynamic programming O(n²) DP over every earlier element ⏱ O(n²) ▦ O(n) Patience sorting (tails + binary search) ⏱ O(n log n) ▦ O(n) O(n log n) from O(n²) · space O(n) 2 edge cases · 5 testsStrictly increasing: equal values cannot both be used. LIS → O(n²) DP, or patience sorting with binary search over tails: O(n log n). new Partition Equal Subset Sum Medium ★★★ #416 quant 1-D dynamic programming Include/exclude every element ⏱ O(2ⁿ) ▦ O(n) 0/1 knapsack over reachable sums ⏱ O(n·S) ▦ O(S) O(n·S) from O(2ⁿ) · space O(S) 4 edge cases · 6 testsThe total (11) is odd, so it cannot be halved. Split into equal halves → subset-sum to total/2 via a 0/1-knapsack boolean DP: O(n·sum). new Perfect Squares Medium ★★★ #279 quant 1-D dynamic programming Recursion over the largest square used ⏱ O(sqrt(n)ⁿ) ▦ O(n) Bottom-up DP (coin change with square coins) ⏱ O(n·sqrt(n)) ▦ O(n) O(n·sqrt(n)) from O(sqrt(n)ⁿ) · space O(n) 3 edge cases · 5 testsGreedy would pick 9 + 4 = 13 here, but it fails for 12 (9 + 1 + 1 + 1). Fewest perfect squares → coin-change DP with square coins: O(n√n). (Number theory: the answer is always ≤ 4.) new Maximum Subarray Medium ★★★ #53 quant Kadane's running best Every subarray with a running sum ⏱ O(n²) ▦ O(1) Kadane's algorithm ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 2 edge cases · 4 testsThe whole array is best: the −1 is worth crossing. Max-sum contiguous subarray → Kadane: run = max(x, run + x), best = max(best, run): O(n), O(1). new Maximum Profit in Job Scheduling Hard ★★★ #1235 quant 1-D dynamic programming Take or skip each job (no memo) ⏱ O(2ⁿ·n) ▦ O(n) Sort by end time, DP + binary search ⏱ O(n log n) ▦ O(n) O(n log n) from O(2ⁿ·n) · space O(n) 3 edge cases · 5 testsAll jobs overlap: the answer is the single best job. Weighted non-overlapping intervals → sort by end, dp[i] = max(dp[i−1], profit + dp[last compatible]), with binary search. new 2-D Dynamic Programming 14 · Tables over two indexes: grids and pairs of strings. Unique Paths Medium ★★★ #62 quant 2-D dynamic programming Recursion from the target ⏱ O(2^(m+n)) ▦ O(m+n) Row-by-row DP ⏱ O(m·n) ▦ O(n) O(m·n) from O(2^(m+n)) · space O(n) 3 edge cases · 5 testsAlready at the target: one (empty) path. Count lattice paths → grid DP (above + left) in O(m·n) with one row, or C(m + n − 2, m − 1). new Longest Common Subsequence Medium ★★★ #1143 quant 2-D dynamic programming Recursion on the first characters ⏱ O(2^(m+n)) ▦ O(m+n) 2-D DP table ⏱ O(m·n) ▦ O(m·n) O(m·n) from O(2^(m+n)) · space O(m·n) 2 edge cases · 5 testsNo common letters. Two sequences, align/compare → 2-D DP on prefixes: match → diagonal + 1, else max(up, left): O(m·n). new Best Time to Buy and Sell Stock with Cooldown Medium ★★★ #309 quant 2-D dynamic programming Recursion on (day, holding?) ⏱ O(2ⁿ) ▦ O(n) Three-state machine ⏱ O(n) ▦ O(1) O(n) from O(2ⁿ) · space O(1) 3 edge cases · 5 testsOne day: no trade possible. Stock with constraints (cooldown, fee, k trades) → state-machine DP over days: O(n) for a fixed number of states. new Coin Change II Medium ★★★ #518 quant 2-D dynamic programming Use-or-skip recursion per coin ⏱ Exponential ▦ O(a) 1-D DP, coins in the outer loop ⏱ O(a·k) ▦ O(a) O(a·k) from Exponential · space O(a) 3 edge cases · 5 tests3 cannot be made from 2's. Count combinations to reach a target with unlimited reuse → unbounded knapsack counting, coins outer loop: O(amount·coins). new Target Sum Medium ★★★ #494 quant 2-D dynamic programming Try every sign pattern ⏱ O(2ⁿ) ▦ O(n) Reduce to subset-sum counting ⏱ O(n·S) ▦ O(S) O(n·S) from O(2ⁿ) · space O(S) 3 edge cases · 5 testsUnreachable target. ± assignments to hit a target → algebra turns it into counting subsets with sum (S + T)/2: O(n·S). new Interleaving String Medium ★★★ #97 2-D dynamic programming Recursion: take the next letter from s1 or s2 ⏱ O(2^(m+n)) ▦ O(m+n) 2-D DP on (letters used from s1, letters used from s2) ⏱ O(m·n) ▦ O(m·n) O(m·n) from O(2^(m+n)) · space O(m·n) 3 edge cases · 6 testsThree empty strings trivially interleave. Merge two sequences preserving order → 2-D DP over (i, j) consumed: O(m·n). new Longest Increasing Path in a Matrix Hard ★★★ #329 2-D dynamic programming DFS from every cell, no memo ⏱ Exponential ▦ O(m·n) DFS with memoisation ⏱ O(m·n) ▦ O(m·n) O(m·n) from Exponential · space O(m·n) 2 edge cases · 5 testsStrictly increasing: equal neighbours don't extend a path. Longest path in a DAG (implicit via strict increase) → DFS + memo (or topological peeling): O(m·n). new Distinct Subsequences Hard ★★★ #115 quant 2-D dynamic programming Recursion: use or skip s[i] ⏱ O(2ᵐ) ▦ O(m) 1-D DP over t, updated right to left ⏱ O(m·n) ▦ O(n) O(m·n) from O(2ᵐ) · space O(n) 3 edge cases · 5 testst's letter never appears in s. Count ways to form t as a subsequence of s → 2-D DP (use/skip on match), compressible to 1-D: O(m·n). new Edit Distance Medium ★★★ #72 quant 2-D dynamic programming Recursion over the three operations ⏱ O(3^(m+n)) ▦ O(m+n) Wagner–Fischer DP table ⏱ O(m·n) ▦ O(m·n) O(m·n) from O(3^(m+n)) · space O(m·n) 3 edge cases · 5 testsFrom empty: insert every letter. Minimum edits between two strings → Levenshtein DP: diagonal on match, else 1 + min(up, left, diag): O(m·n). new Burst Balloons Hard ★★★ #312 2-D dynamic programming Try every burst order ⏱ O(n!) ▦ O(n) Interval DP on the LAST balloon burst ⏱ O(n³) ▦ O(n²) O(n³) from O(n!) · space O(n²) 2 edge cases · 4 testsOne balloon: 1 × 5 × 1. Order-dependent merges → interval DP choosing the last action in each interval: O(n³). new Regular Expression Matching Hard ★★★ #10 2-D dynamic programming Plain recursion ⏱ Exponential ▦ O(m+n) Bottom-up DP on suffixes ⏱ O(m·n) ▦ O(m·n) O(m·n) from Exponential · space O(m·n) 3 edge cases · 6 tests".*" matches anything, including different letters. Pattern matching with * → DP on (i, j) suffix states; 'x*' = skip it or consume one and stay: O(m·n). new Unique Paths II Medium ★★★ #63 2-D dynamic programming Recursion from the target ⏱ O(2^(m+n)) ▦ O(m+n) Row DP with obstacles zeroed ⏱ O(m·n) ▦ O(n) O(m·n) from O(2^(m+n)) · space O(n) 3 edge cases · 5 testsThe start itself is blocked. Grid path counting with blocked cells → same DP, zero out obstacles: O(m·n), O(n) space. new Minimum Path Sum Medium ★★★ #64 2-D dynamic programming Recursion over every path ⏱ O(2^(m+n)) ▦ O(m+n) Row DP ⏱ O(m·n) ▦ O(n) O(m·n) from O(2^(m+n)) · space O(n) 2 edge cases · 5 testsSingle cell. Min-cost monotone grid path → DP: cell + min(above, left): O(m·n), O(n) space. new Maximal Square Medium ★★★ #221 2-D dynamic programming Grow a square from every cell ⏱ O((m·n)²) ▦ O(1) DP: side = 1 + min(up, left, up-left) ⏱ O(m·n) ▦ O(n) O(m·n) from O((m·n)²) · space O(n) 2 edge cases · 4 testsNo 1's: area 0. Largest square of 1's → DP on bottom-right corners: 1 + min(three neighbours): O(m·n). new Greedy 9 · Take the locally best step when it provably stays optimal. Jump Game Medium ★★★ #55 Greedy DP from the end ⏱ O(n²) ▦ O(n) Greedy farthest reach ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 2 edge cases · 5 testsEvery route lands on index 3, whose jump length is 0. Reachability with max jump lengths → greedy farthest-reach scan: O(n), O(1). new Jump Game II Medium ★★★ #45 Greedy DP over earlier indices ⏱ O(n²) ▦ O(n) Greedy levels (implicit BFS) ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 2 edge cases · 5 testsAlready at the end: zero jumps. Min jumps → BFS by levels where each level is a contiguous window: greedy O(n). new Gas Station Medium ★★★ #134 quant Greedy Simulate from every start ⏱ O(n²) ▦ O(1) One pass with a reset ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 2 edge cases · 5 testsTotal gas (9) is less than total cost (10): impossible from anywhere. Circular feasibility with running balance → one pass: reset the start when the running sum goes negative; total ≥ 0 guarantees the last start works: O(n). new Hand of Straights Medium ★★★ #846 Greedy Repeatedly remove the smallest run ⏱ O(n²) ▦ O(n) Counts + smallest-first ⏱ O(n log n) ▦ O(n) O(n log n) from O(n²) · space O(n) 3 edge cases · 5 tests5 cards can't be split into groups of 4. Partition into consecutive runs → counts + process smallest first (it must start a run): O(n log n). new Merge Triplets to Form Target Medium ★★★ #1899 Greedy Try every subset ⏱ O(2ⁿ·n) ▦ O(n) Keep only 'safe' triplets ⏱ O(n) ▦ O(1) O(n) from O(2ⁿ·n) · space O(1) 3 edge cases · 5 testsEvery triplet's middle value is above 2, and maxima can't decrease. Monotone merge (max) → discard anything that overshoots, then check coverage: O(n). new Partition Labels Medium ★★★ #763 Greedy Grow each part until it is closed ⏱ O(n²) ▦ O(1) Last-occurrence map + one sweep ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 2 edge cases · 4 testse appears at both ends, so everything is one part. Partition so each label stays in one piece → last-occurrence map + greedy cut when i == reach: O(n). new Valid Parenthesis String Medium ★★★ #678 Greedy Try every meaning of each * ⏱ O(3ᵏ·n) ▦ O(n) Track the range of possible open counts ⏱ O(n) ▦ O(1) O(n) from O(3ᵏ·n) · space O(1) 2 edge cases · 6 testsTreat * as ( to balance the extra ). Wildcard brackets → track the [min, max] range of open counts greedily: O(n), O(1). new Best Time to Buy and Sell Stock II Medium ★★★ #122 quant Greedy Recursion: buy, sell or wait each day ⏱ O(2ⁿ) ▦ O(n) Sum every positive day-to-day move ⏱ O(n) ▦ O(1) O(n) from O(2ⁿ) · space O(1) 3 edge cases · 5 testsOne long trade equals the sum of daily gains. Unlimited trades, no fees → sum of positive consecutive differences: O(n). new Candy Hard ★★★ #135 Greedy Fix violations until stable ⏱ O(n²) ▦ O(n) Two passes (left rule, then right rule) ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 2 edge cases · 5 testsEqual neighbours don't need different amounts: 1, 2, 1. Two-sided neighbour constraints → two greedy passes (left then right), taking the max: O(n). new Intervals 9 · Sort by start, then merge, insert or count overlaps. Insert Interval Medium ★★★ #57 Interval sweep Append, sort, merge ⏱ O(n log n) ▦ O(n) One linear pass in three phases ⏱ O(n) ▦ O(n) O(n) from O(n log n) · space O(n) 4 edge cases · 6 testsNo existing intervals. Insert into sorted disjoint intervals → linear scan: copy before, merge overlaps, copy after: O(n). new Merge Intervals Medium ★★★ #56 quant Interval sweep Merge pairs until stable ⏱ O(n³) ▦ O(n) Sort by start, then sweep ⏱ O(n log n) ▦ O(n) O(n log n) from O(n³) · space O(n) 3 edge cases · 5 testsTouching intervals merge. Merge overlapping intervals → sort by start + one sweep extending the last: O(n log n). new Non-overlapping Intervals Medium ★★★ #435 Interval sweep Longest compatible chain (DP) ⏱ O(n²) ▦ O(n) Greedy: keep the earliest-ending interval ⏱ O(n log n) ▦ O(1) O(n log n) from O(n²) · space O(1) 2 edge cases · 4 testsIdentical intervals: keep only one. Max set of non-overlapping intervals (activity selection) → sort by end, greedy keep: O(n log n). new Meeting Rooms Easy ★★★ #252 Interval sweep Compare every pair ⏱ O(n²) ▦ O(1) Sort and check neighbours ⏱ O(n log n) ▦ O(1) O(n log n) from O(n²) · space O(1) 2 edge cases · 4 testsNo meetings: trivially yes. Any overlap among intervals → sort by start and compare neighbours: O(n log n). new Meeting Rooms II Medium ★★★ #253 quant Heap / top-k Count overlaps at every start time ⏱ O(n²) ▦ O(1) Sort by start + min-heap of end times ⏱ O(n log n) ▦ O(n) O(n log n) from O(n²) · space O(n) 3 edge cases · 5 testsThe room frees exactly when the next meeting starts. Max concurrent intervals (rooms, servers, positions) → sort by start + min-heap of ends, or a +1/−1 sweep: O(n log n). new Minimum Interval to Include Each Query Hard ★★★ #1851 Heap / top-k Scan all intervals per query ⏱ O(n·q) ▦ O(1) Sorted sweep with a min-heap by size ⏱ O(n log n + q log q) ▦ O(n + q) O(n log n + q log q) from O(n·q) · space O(n + q) 2 edge cases · 4 tests2 lies in no interval. Many point queries over intervals → offline: sort queries and intervals, sweep with a heap keyed by the answer metric: O((n + q) log). new Interval List Intersections Medium ★★★ #986 quant Two pointers Intersect every pair ⏱ O(n·m) ▦ O(n+m) Two pointers ⏱ O(n+m) ▦ O(n+m) O(n+m) from O(n·m) · space O(n+m) 2 edge cases · 4 testsOne list is empty: nothing in common. Intersect two sorted interval lists → two pointers, advance the earlier-ending one: O(n + m). new Minimum Number of Arrows to Burst Balloons Medium ★★★ #452 Interval sweep Smallest set of candidate positions ⏱ O(2ⁿ·n²) ▦ O(n) Sort by end, shoot at each end ⏱ O(n log n) ▦ O(1) O(n log n) from O(2ⁿ·n²) · space O(1) 2 edge cases · 5 testsTouching balloons can share an arrow (at 2 and at 4). Minimum points to stab all intervals → sort by end, place a point at each uncovered interval's end: O(n log n). new Car Pooling Medium ★★★ #1094 Interval sweep Count passengers at every kilometre ⏱ O(n·R) ▦ O(1) Sweep sorted pick-up / drop-off events ⏱ O(n log n) ▦ O(n) O(n log n) from O(n·R) · space O(n) 2 edge cases · 5 testsAt km 5 the first group gets off before the second gets on. Max simultaneous load over intervals → sweep line over +/− events (or a difference array when coordinates are small). new Math & Geometry 12 · Matrices, number tricks and careful arithmetic. Rotate Image Medium ★★★ #48 Matrix traversal Rotate into a copy ⏱ O(n²) ▦ O(n²) Transpose, then reverse each row ⏱ O(n²) ▦ O(1) O(n²) from O(n²) · space O(1) 1 edge cases · 4 testsA 1 × 1 matrix is unchanged. Rotate a square matrix in place → transpose + reverse rows (or 4-way cycle swaps by layer): O(n²), O(1). new Spiral Matrix Medium ★★★ #54 Matrix traversal Walk with a direction and a visited grid ⏱ O(m·n) ▦ O(m·n) Shrinking boundaries ⏱ O(m·n) ▦ O(1) O(m·n) from O(m·n) · space O(1) 2 edge cases · 5 testsA single row: don't walk back along it. Spiral traversal → four shrinking boundaries with guards: O(m·n), O(1). new Set Matrix Zeroes Medium ★★★ #73 Matrix traversal Remember zero rows and columns in sets ⏱ O(m·n) ▦ O(m+n) Use the first row and column as markers ⏱ O(m·n) ▦ O(1) O(m·n) from O(m·n) · space O(1) 2 edge cases · 5 testsZeros in the first row: the trick that uses row 0 as markers must remember this separately. Mark-then-apply in a matrix with O(1) space → reuse row 0/column 0 as flags (remember their own state first): O(m·n). new Happy Number Easy ★★★ #202 Fast & slow pointers Remember every number seen ⏱ O(log n) ▦ O(log n) Floyd's tortoise and hare ⏱ O(log n) ▦ O(1) O(log n) from O(log n) · space O(1) 2 edge cases · 5 testsAlready 1. Iterated function that must end or loop → cycle detection (hash set, or Floyd's fast/slow for O(1) space). new Plus One Easy ★★★ #66 Math & number tricks Convert to a big number and back ⏱ O(n) ▦ O(n) Carry from the right ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 2 edge cases · 5 testsThe carry creates a new leading digit. Arbitrary-precision increment → carry from the least significant digit with early exit: O(n). new Pow(x, n) Medium ★★★ #50 quant Math & number tricks Multiply |n| times ⏱ O(n) ▦ O(1) Binary exponentiation ⏱ O(log n) ▦ O(1) O(log n) from O(n) · space O(1) 4 edge cases · 6 testsNegative exponent: 1 / 2² = 0.25. Fast power → binary exponentiation (square-and-multiply): O(log n). The same trick powers modular exponentiation and matrix powers. new Multiply Strings Medium ★★★ #43 quant Math & number tricks Partial products + string addition ⏱ O(n·(m+n)) ▦ O(m+n) Position array ⏱ O(m·n) ▦ O(m+n) O(m·n) from O(n·(m+n)) · space O(m+n) 2 edge cases · 5 testsZero times anything is "0", not "00". Big-number multiplication → position array of size m + n, accumulate digit products with carry: O(m·n). new Detect Squares Medium ★★★ #2013 Hash map lookup List of points; scan for the other corners ⏱ O(n²) per count ▦ O(n) Point counts in a hash map ⏱ O(n) per count ▦ O(n) O(n) per count from O(n²) per count · space O(n) 4 edge cases · 5 testsNo points stored. Count geometric shapes with multiplicity → hash map of point counts, enumerate the defining corner: O(n) per query. new Sqrt(x) Easy ★★★ #69 quant Binary search Count up ⏱ O(sqrt(x)) ▦ O(1) Binary search on the answer ⏱ O(log x) ▦ O(1) O(log x) from O(sqrt(x)) · space O(1) 2 edge cases · 5 tests√8 ≈ 2.83 rounds down to 2. Integer square root → binary search the largest k with k² ≤ x (or Newton's method): O(log x). new Excel Sheet Column Number Easy ★★★ #171 Math & number tricks Count up through titles ⏱ O(N·L) ▦ O(L) Base-26 with digits 1–26 ⏱ O(L) ▦ O(1) O(L) from O(N·L) · space O(1) 2 edge cases · 5 testsThere is no zero digit: Z means 26, not 0 with a carry. Bijective base-26 → Horner's rule with digits 1..26: O(L). new Count Primes Medium ★★★ #204 quant Math & number tricks Trial division ⏱ O(n·sqrt(n)) ▦ O(1) Sieve of Eratosthenes ⏱ O(n log log n) ▦ O(n) O(n log log n) from O(n·sqrt(n)) · space O(n) 2 edge cases · 6 testsStrictly less than 2: no primes. Count/list primes up to n → Sieve of Eratosthenes: O(n log log n) time, O(n) memory. new Game of Life Medium ★★★ #289 Matrix traversal Compute into a copy ⏱ O(m·n) ▦ O(m·n) Two bits per cell ⏱ O(m·n) ▦ O(1) O(m·n) from O(m·n) · space O(1) 2 edge cases · 5 testsA lone live cell dies of underpopulation. Simultaneous in-place grid update → encode the next state in spare bits (or extra state values), then finalise: O(m·n), O(1). new Bit Manipulation 8 · XOR, masks and shifts. Single Number Easy ★★★ #136 quant Bit manipulation Count with a hash map ⏱ O(n) ▦ O(n) XOR everything ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 2 edge cases · 4 testsA single element is the answer. Find the unpaired element → XOR fold: O(n) time, O(1) space. new Number of 1 Bits Easy ★★★ #191 Bit manipulation Check all 32 bits ⏱ O(32) ▦ O(1) Brian Kernighan's trick ⏱ O(k) ▦ O(1) O(k) from O(32) · space O(1) 1 edge cases · 4 testsTop bit set: as a Java int this is negative (−3), so shift with >>> or use n & (n − 1). Count set bits → n & (n − 1) loop (Kernighan), O(number of 1 bits); or a built-in popcount. new Counting Bits Easy ★★★ #338 Bit manipulation Popcount each number ⏱ O(n log n) ▦ O(1) DP: bits(i) = bits(i >> 1) + (i & 1) ⏱ O(n) ▦ O(1) O(n) from O(n log n) · space O(1) 1 edge cases · 4 testsOnly the number 0. Popcounts for 0..n → DP on i >> 1 (or i & (i − 1)): O(n). new Reverse Bits Easy ★★★ #190 Bit manipulation Via a 32-character binary string ⏱ O(32) ▦ O(32) Shift bits across one at a time ⏱ O(32) ▦ O(1) O(32) from O(32) · space O(1) 2 edge cases · 4 testsInput has the top bit set (negative as a Java int); use >>> so the sign doesn't smear in. Reverse bits → 32 rounds of res = (res << 1) | (n & 1); n >>>= 1. Memoise per byte for many calls. new Missing Number Easy ★★★ #268 quant Bit manipulation Sort and scan ⏱ O(n log n) ▦ O(1) XOR indices with values ⏱ O(n) ▦ O(1) O(n) from O(n log n) · space O(1) 2 edge cases · 4 testsThe missing number can be n itself. Find the one missing value in 0..n → Gauss sum difference or XOR of indices and values: O(n), O(1). new Sum of Two Integers Medium ★★★ #371 Bit manipulation Ripple-carry adder, bit by bit ⏱ O(32) ▦ O(1) XOR for the sum, AND << 1 for the carry ⏱ O(32) ▦ O(1) O(32) from O(32) · space O(1) 2 edge cases · 5 testsTwo's complement: the carry runs off the top of the 32 bits. Add without + → XOR for partial sum, (AND << 1) for carry, loop until carry is 0 (mask in Python). new Reverse Integer Medium ★★★ #7 Math & number tricks Reverse the string, then range-check ⏱ O(d) ▦ O(d) Pop and push digits with an overflow guard ⏱ O(d) ▦ O(1) O(d) from O(d) · space O(1) 4 edge cases · 6 testsThe sign stays in front. Digit reversal with bounds → pop/push digits, check overflow before r × 10 + d: O(log x). new Power of Two Easy ★★★ #231 Bit manipulation Keep dividing by 2 ⏱ O(log n) ▦ O(1) Exactly one set bit ⏱ O(1) ▦ O(1) O(1) from O(log n) · space O(1) 2 edge cases · 6 tests0 has no set bit; 0 & (0 − 1) = 0 would wrongly pass without the n > 0 check. Power of two → n > 0 and n & (n − 1) == 0: O(1). new Data Structure Design 9 · Classes with operations that must hit target complexities. LRU Cache Medium ★★★ #146 quant Data structure design List in recency order ⏱ O(n) per op ▦ O(n) Hash map + doubly linked list ⏱ O(1) per op ▦ O(capacity) O(1) per op from O(n) per op · space O(capacity) 2 edge cases · 4 testsCapacity 1: every new key evicts the previous one. O(1) get/put with recency eviction → hash map + doubly linked list with sentinels (LinkedHashMap / OrderedDict in practice). new LFU Cache Hard ★★★ #460 Data structure design Scan for the victim ⏱ O(n) per eviction ▦ O(n) Frequency buckets of LRU lists + min-frequency pointer ⏱ O(1) per op ▦ O(capacity) O(1) per op from O(n) per eviction · space O(capacity) 3 edge cases · 4 testsEqual counts: the least recently used (key 1) goes. O(1) LFU → key map + count→ordered-set buckets + a min-frequency pointer. new Insert Delete GetRandom O(1) Medium ★★★ #380 quant Data structure design Plain list ⏱ O(n) insert/remove ▦ O(n) Array + value→index map, swap-remove ⏱ O(1) average ▦ O(n) O(1) average from O(n) insert/remove · space O(n) 2 edge cases · 3 testsDuplicates are rejected; removing twice fails the second time. O(1) insert/delete/random → array + value→index map, swap-with-last on delete. new Design Hit Counter Medium ★★★ #362 quant Data structure design Store every timestamp ⏱ O(n) getHits ▦ O(n) 300 circular buckets ⏱ O(1) hit, O(300) getHits ▦ O(300) O(1) hit, O(300) getHits from O(n) getHits · space O(300) 3 edge cases · 4 testsMany hits in one second; the window is (t − 300, t]. Sliding-window counter → ring buffer of per-second buckets (or a deque of timestamps): bounded memory. new Design Underground System Medium ★★★ #1396 Data structure design Keep every trip; average on demand ⏱ O(T) per query ▦ O(T) Running totals per route ⏱ O(1) per op ▦ O(P + R) O(1) per op from O(T) per query · space O(P + R) 2 edge cases · 3 testsDirection matters: A→B and B→A are separate routes. Streaming averages by key → store running sum and count per key: O(1) updates and queries. new Snapshot Array Medium ★★★ #1146 quant Binary search Copy the whole array on every snap ⏱ O(n) per snap ▦ O(n·S) Per-index change history + binary search ⏱ O(1) set/snap, O(log S) get ▦ O(n + sets) O(1) set/snap, O(log S) get from O(n) per snap · space O(n + sets) 2 edge cases · 3 testsNever-set indices read as 0; a value set after snap 1 shows up only from snap 2. Versioned array / time-travel reads → per-key change logs + binary search (copy-on-write idea): O(log S) reads. new Design Browser History Medium ★★★ #1472 Data structure design Two stacks, one step at a time ⏱ O(steps) per back/forward ▦ O(n) Array with current and last pointers ⏱ O(1) per op ▦ O(n) O(1) per op from O(steps) per back/forward · space O(n) 2 edge cases · 3 testsNowhere to go: stay on the homepage. Undo/redo-style navigation → array + cursor + last-valid index: O(1) moves. new Implement Queue using Stacks Easy ★★★ #232 Stack Reorder on every push ⏱ O(n) push, O(1) pop ▦ O(n) Inbox / outbox stacks (amortised) ⏱ O(1) amortised ▦ O(n) O(1) amortised from O(n) push, O(1) pop · space O(n) 1 edge cases · 3 testsPushes interleaved with pops must keep FIFO order. Queue from stacks → inbox/outbox, pour only when outbox is empty: amortised O(1). new Design Circular Queue Medium ★★★ #622 quant Data structure design Dynamic list with pop(0) ⏱ O(k) deQueue ▦ O(k) Fixed array + head + count ⏱ O(1) per op ▦ O(k) O(1) per op from O(k) deQueue · space O(k) 2 edge cases · 3 testsEmpty queue: Front/Rear return −1 and deQueue fails. Bounded FIFO → ring buffer with head + count and modular indexing: O(1) everything. new Quant & Trading 25 · Pricing, probability, simulation and market-data problems asked at trading firms. Limit Order Book Hard ★★★ quant Heap / top-k One list, scanned every time ⏱ O(n) per match step ▦ O(n) Price levels: heaps (or sorted maps) of FIFO queues + lazy cancel ⏱ O(log P) per price change, O(1) per fill ▦ O(n) O(log P) per price change, O(1) per fill from O(n) per match step · space O(n) 3 edge cases · 4 testsTime priority: order 1 (older) fills completely before order 2 is touched; a fully filled order can't be cancelled. Matching engine → per-side sorted price levels (heap/TreeMap) of FIFO queues + id map; lazy cancels: O(log P) per new level, O(1) per fill. new Moving VWAP Easy ★★★ quant Sliding window Recompute over the window ⏱ O(k) per add ▦ O(n) Queue + running sums ⏱ O(1) per add ▦ O(k) O(1) per add from O(k) per add · space O(k) 2 edge cases · 3 testsk = 1: the VWAP is the latest trade's price. Sliding aggregates (VWAP, moving average) → queue + running sums: O(1) per update. new Moving Average from Data Stream Easy ★★★ #346 quant Sliding window Sum the window each time ⏱ O(size) per call ▦ O(n) Queue + running sum ⏱ O(1) per call ▦ O(size) O(1) per call from O(size) per call · space O(size) 2 edge cases · 3 testsWindow of 1. Simple moving average → queue + running sum: O(1) per value. new Maximum Drawdown Medium ★★★ quant Greedy Every peak–trough pair ⏱ O(n²) ▦ O(1) Running peak ⏱ O(n) ▦ O(1) O(n) from O(n²) · space O(1) 3 edge cases · 5 testsOnly rising: no drawdown. Max drawdown → running high-water mark, one pass: O(n). (Mirror image of max-profit single trade.) new Best Time to Buy and Sell Stock IV Hard ★★★ #188 quant 2-D dynamic programming Recursion on (day, trades left, holding?) ⏱ O(2ⁿ) ▦ O(n) DP over transactions: buy[j], sell[j] ⏱ O(n·k) ▦ O(k) O(n·k) from O(2ⁿ) · space O(k) 3 edge cases · 5 testsTwo trades: 2→6 and 0→3. At most k trades → DP over (trade index, holding): O(n·k); collapse to the greedy when k ≥ n/2. new Best Time to Buy and Sell Stock with Transaction Fee Medium ★★★ #714 quant 1-D dynamic programming Recursion: buy, sell or wait ⏱ O(2ⁿ) ▦ O(n) Two states: cash and hold ⏱ O(n) ▦ O(1) O(n) from O(2ⁿ) · space O(1) 2 edge cases · 5 testsThe fee is bigger than the gain: don't trade. Stock with a fee → two-state DP (cash, hold): O(n), O(1). new Black–Scholes Call Price Medium ★★★ quant Math & number tricks Integrate the discounted payoff ⏱ O(m) ▦ O(1) Closed form: S·N(d₁) − K·e^(−rT)·N(d₂) ⏱ O(1) ▦ O(1) O(1) from O(m) · space O(1) 3 edge cases · 5 testsDeep in the money: ≈ S − K·e^(−rT) = 104.88. European option → Black–Scholes closed form with a stable normal CDF; numerical integration or Monte Carlo as checks. new American Put on a Binomial Tree Medium ★★★ quant 2-D dynamic programming Recurse over every path ⏱ O(2ⁿ) ▦ O(n) Backward induction on a recombining tree ⏱ O(n²) ▦ O(n) O(n²) from O(2ⁿ) · space O(n) 2 edge cases · 4 testsDeep in the money: exercising immediately (100 − 40) beats waiting. Lattice option pricing → backward induction on a recombining tree: O(n²) time, O(n) space. new Implied Volatility Medium ★★★ quant Binary search on the answer Bisection on σ ⏱ O(log(1/ε)) ▦ O(1) Newton–Raphson with vega, safeguarded by a bracket ⏱ O(iterations), typically < 10 ▦ O(1) O(iterations), typically < 10 from O(log(1/ε)) · space O(1) 2 edge cases · 5 testsBelow the lower bound S − K·e^(−rT) ≈ 4.88: no volatility gives this price. Invert a monotone pricing function → bracketed Newton (vega as derivative), bisection as fallback: a few iterations. new Bond Yield to Maturity Medium ★★★ quant Binary search on the answer Bisection on the yield ⏱ O(n·log(1/ε)) ▦ O(1) Newton's method with the price derivative ⏱ O(n·iterations), ~5 iterations ▦ O(1) O(n·iterations), ~5 iterations from O(n·log(1/ε)) · space O(1) 4 edge cases · 5 testsBelow par: the yield is above the coupon. Solve PV(y) = price → Newton with duration as the derivative (bisection fallback): a few iterations of O(n). new Probability of a Dice Sum Medium ★★★ quant 1-D dynamic programming Enumerate all 6ⁿ outcomes ⏱ O(6ⁿ·n) ▦ O(n) DP over the running sum ⏱ O(n²·6) ▦ O(n) O(n²·6) from O(6ⁿ·n) · space O(n) 3 edge cases · 5 testsSeven is the most likely two-dice total: 6 of 36 outcomes. Distribution of a sum of independent discrete variables → DP convolution: O(n·range·faces) (FFT for large n). new Gambler's Ruin Medium ★★★ quant Math & number tricks Solve the linear equations ⏱ O(N³) ▦ O(N²) Closed form ⏱ O(1) ▦ O(1) O(1) from O(N³) · space O(1) 5 edge cases · 6 testsFair game: the probability is start / target (a martingale). Absorbing random walk → first-step analysis gives a linear recurrence; closed form (1 − ρⁱ)/(1 − ρᴺ). new Expected Flips Until a Pattern Hard ★★★ quant Math & number tricks Markov chain + linear solve ⏱ O(m³) ▦ O(m²) Overlap (autocorrelation) formula ⏱ O(m²) ▦ O(1) O(m²) from O(m³) · space O(1) 2 edge cases · 7 testsHH can 'overlap' itself, which makes it slower to appear than HT. Waiting time for a pattern → Markov chain on matched-prefix length, or the overlap formula Σ 2ᵏ (Conway): O(m²). new Dice Game with Rerolls (Optimal Stopping) Medium ★★★ quant 1-D dynamic programming Explore the full decision tree ⏱ O(6ⁿ) ▦ O(n) Backward induction ⏱ O(6n) ▦ O(1) O(6n) from O(6ⁿ) · space O(1) 2 edge cases · 5 testsKeep 4, 5 or 6; reroll 1–3 (worth 3.5): (4 + 5 + 6 + 3·3.5)/6. Optimal stopping → backward induction: value = E[max(stop payoff, continuation value)]. new Kelly Bet Size Medium ★★★ quant Math & number tricks Ternary search on the concave growth rate ⏱ O(iterations·m) ▦ O(1) Newton's method on g′(f) = 0 ⏱ O(iterations·m), ~10 iterations ▦ O(1) O(iterations·m), ~10 iterations from O(iterations·m) · space O(1) 4 edge cases · 5 testsPaying 2:1 with a coin flip: f* = p − q/b = 0.5 − 0.5/2. Growth-optimal sizing → maximise E[log(1 + fR)]; concave, so Newton/ternary search (two outcomes: f* = p − q/b). new EWMA Volatility (RiskMetrics) Medium ★★★ quant 1-D dynamic programming Recompute each day from the weighted sum ⏱ O(n²) ▦ O(n) Recursive update ⏱ O(n) ▦ O(n) O(n) from O(n²) · space O(n) 2 edge cases · 3 testsOne return: the seed. Exponentially weighted statistics → recursive update s = λs + (1 − λ)x: O(1) per observation. new Running Mean and Variance (Welford) Medium ★★★ quant Data structure design Store everything; two-pass on demand ⏱ O(n) per query ▦ O(n) Welford's online algorithm ⏱ O(1) per op ▦ O(1) O(1) per op from O(n) per query · space O(1) 2 edge cases · 3 testsHuge values: the naive Σx² − n·mean² formula loses all precision here. Streaming mean/variance → Welford's update (stable, O(1)); Chan's formula merges partial results in parallel. new Pearson Correlation Easy ★★★ quant Math & number tricks Two passes ⏱ O(n) ▦ O(1) One streaming pass (Welford co-moments) ⏱ O(n) ▦ O(1) O(n) from O(n) · space O(1) 3 edge cases · 5 testsPerfectly opposite. Correlation → centred co-moments, two-pass or one-pass Welford; never Σxy − n·x̄ȳ on raw large numbers. new Currency Arbitrage Detection Hard ★★★ quant Graph BFS / DFS Try every cycle ⏱ O(n!·n) ▦ O(n) Bellman–Ford on −log(rate) ⏱ O(n³) ▦ O(n²) O(n³) from O(n!·n) · space O(n²) 3 edge cases · 4 testsA round trip worth exactly 1 is not an arbitrage. Multiplicative cycle detection → take −log weights, negative cycle via Bellman–Ford: O(V·E). new Count Inversions (Kendall Distance) Hard ★★★ quant Math & number tricks Check every pair ⏱ O(n²) ▦ O(1) Merge sort with counting ⏱ O(n log n) ▦ O(n) O(n log n) from O(n²) · space O(n) 3 edge cases · 5 testsAlready sorted. Count inversions → merge sort with a counter (or a Fenwick tree over ranks): O(n log n). new Sliding Window Median Hard ★★★ #480 quant Heap / top-k Sort each window ⏱ O(n·k log k) ▦ O(k) Two heaps with lazy deletion ⏱ O(n log k) ▦ O(n) O(n log k) from O(n·k log k) · space O(n) 3 edge cases · 5 testsEven k: average the two middle values. Sliding median → two heaps + lazy deletion (or an order-statistic tree / two sorted multisets): O(n log k). new Merge Sorted Market Data Feeds Medium ★★★ quant Heap / top-k Concatenate and sort ⏱ O(N log N) ▦ O(N) k-way merge with a min-heap ⏱ O(N log k) ▦ O(k) O(N log k) from O(N log N) · space O(k) 3 edge cases · 5 testsEmpty feeds are allowed. Merge k sorted streams → min-heap of k heads: O(N log k); works on unbounded streams. new Random Pick with Weight Medium ★★★ #528 quant Binary search Scan cumulative weights ⏱ O(n) per pick ▦ O(1) Prefix sums + binary search ⏱ O(log n) per pick ▦ O(n) O(log n) per pick from O(n) per pick · space O(n) 2 edge cases · 3 testsOne weight: always index 0. Weighted sampling → prefix sums + binary search (O(log n)); alias method for O(1) picks; Fenwick tree if weights change. new Range Sum Query - Mutable Medium ★★★ #307 quant Prefix sums Plain array ⏱ O(1) update, O(n) query ▦ O(n) Fenwick (binary indexed) tree ⏱ O(log n) per op ▦ O(n) O(log n) per op from O(1) update, O(n) query · space O(n) 2 edge cases · 3 testsNegative updates and empty sub-ranges. Point updates + range sums → Fenwick tree (or segment tree): O(log n) each. new Stock Price Fluctuation Medium ★★★ #2034 quant Heap / top-k Hash map + scan ⏱ O(n) for max/min ▦ O(n) Map + two heaps with lazy validation ⏱ O(log n) amortised ▦ O(n) O(log n) amortised from O(n) for max/min · space O(n) 2 edge cases · 3 testsOut-of-order timestamps: current is the latest time, not the latest call. Max/min under corrections → hash map of truth + heaps with lazy invalidation (or a sorted multiset): O(log n). new System Design 20 · Scalable architectures, estimates and trade-offs, with one core component coded. Design a URL Shortener Medium ★★★ System design Hash the URL (e.g. MD5) and take the first 7 characters; store it in one SQL table; every redirect reads the… breaks at scale Generate unique IDs (a counter handed out in ranges, or Snowflake IDs), encode them in base 62, store code → URL in a replicated… Estimates, trade-offs core: O(1) amortised 3 failure modes · core: Short-code codec (base 62)Cache node dies ID generation (counter ranges or Snowflake) → base 62 → KV store, with a read-through cache and CDN because reads dominate. new Design a Rate Limiter Medium ★★★ quant System design A fixed-window counter per client in one database: INCR key:minute and reject above N. breaks at scale Run the limiter in the API gateway as middleware. Use a sliding-window (log or counter approximation) or token bucket per key,… Estimates, trade-offs core: O(1) amortised 3 failure modes · core: Sliding-window rate limiterRedis shard down Gateway middleware + token bucket or sliding window per key in sharded Redis with atomic Lua updates; local caches for rules and blocked keys. new Design a Distributed Key-Value Store Hard ★★★ quant System design One big server with a hash map persisted to disk; scale up by buying a bigger machine. breaks at scale Partition keys with consistent hashing (virtual nodes), replicate each key to N nodes, use quorum reads/writes (R + W > N for… Estimates, trade-offs core: O(N log k) 3 failure modes · core: LSM compaction: merge sorted runsNode down Consistent hashing + replication with quorum R/W, LSM storage (WAL, memtable, SSTables, Bloom filters, compaction), gossip and anti-entropy for repair. new Design a News Feed Hard ★★★ System design On every feed request, query all followees' posts, sort by time and return the top 20 (pull on read). breaks at scale Hybrid fan-out: on write, push the post ID into each follower's precomputed feed (a Redis list), except for celebrities; on… Estimates, trade-offs core: O(F + k log F) 3 failure modes · core: Merge followees' timelines (top k newest)Fan-out backlog Hybrid fan-out: push post IDs into per-user feed caches, pull celebrities at read time, k-way merge then rank; cursor pagination. new Design a Chat System Hard ★★★ System design Clients poll a REST endpoint every few seconds for new messages stored in one SQL table. breaks at scale Persistent WebSocket connections to stateless chat gateways; a session registry maps user → gateway. Messages get a… Estimates, trade-offs core: O(1) amortised 3 failure modes · core: Client reorder bufferGateway crash WebSocket gateways + session registry; per-conversation sequence numbers written to a partitioned store; at-least-once delivery with client-side reorder and dedupe. new Design a Web Crawler Medium ★★★ System design A single process with a FIFO queue and a set of visited URLs, fetching one page at a time. breaks at scale A URL frontier split into per-host queues (for politeness) and priority queues (for importance), many stateless fetcher workers,… Estimates, trade-offs core: O(V+E) 3 failure modes · core: Depth-limited BFS crawl with dedupeFetcher crash Frontier with per-host politeness queues + priorities, distributed fetchers, URL normalisation and Bloom-filter dedupe, content fingerprints, re-crawl scheduling. new Design a Notification System Medium ★★★ System design The application calls the email/SMS provider synchronously inside the request. breaks at scale A notification service validates and enqueues requests; a scheduler holds future jobs in time-bucketed storage and releases due… Estimates, trade-offs core: O(log n) per job 3 failure modes · core: Scheduled job dispatcherProvider outage API → queues per channel with priority isolation; scheduler with time buckets + min-heap; idempotent workers with retries, rate limits and preferences. new Design Search Autocomplete (Typeahead) Medium ★★★ System design SELECT query FROM searches WHERE query LIKE 'prefix%' ORDER BY count DESC LIMIT 10 on every keystroke. breaks at scale Serve from an in-memory trie (or prefix → top-k table) replicated across servers and cached at the CDN/browser for short… Estimates, trade-offs core: O(p + m log k) 3 failure modes · core: Top-k completions by popularityTrie server restart In-memory trie with top-k cached per node, sharded and replicated, fed by a log-aggregation pipeline; heavy caching at browser and CDN. new Design a Distributed Cache Medium ★★★ quant System design Route keys with hash(key) mod N. breaks at scale Consistent hashing with virtual nodes: hash nodes (many times each) and keys onto a ring; a key belongs to the first node… Estimates, trade-offs core: O(log V) per lookup 3 failure modes · core: Consistent hash ring with virtual nodesNode failure Consistent hashing with virtual nodes for placement, LRU/LFU per node with TTL, cache-aside pattern, single-flight to prevent stampedes. new Design a Distributed Unique ID Generator Medium ★★★ quant System design A database auto-increment column, or random UUIDs. breaks at scale Each worker composes IDs locally: [41-bit ms timestamp since a custom epoch][10-bit worker id][12-bit per-ms sequence]. Worker… Estimates, trade-offs core: O(1) 2 failure modes · core: Snowflake ID encoder / decoderDuplicate worker id Snowflake layout: 41-bit ms timestamp, 10-bit worker, 12-bit sequence; no coordination per ID; guard against clock rollback. new Design File Sync (Dropbox / Google Drive) Hard ★★★ System design Upload the whole file to one server's disk on every save; clients poll for changes. breaks at scale Split files into content-addressed blocks (hash = block ID) stored in object storage (dedupe across users); a metadata service… Estimates, trade-offs core: O(n + m) expected 3 failure modes · core: Find a block anywhere in a file (rolling hash)Upload interrupted Content-addressed blocks in object storage + metadata DB of block lists and versions; clients upload only missing blocks (rolling-hash chunking), notified via long poll. new Design a Video Streaming Service Hard ★★★ System design Store one MP4 per video on a web server and let players download it. breaks at scale Upload to object storage, then a DAG of transcoding jobs splits the video into segments and produces a bitrate ladder… Estimates, trade-offs core: O(n log n) 3 failure modes · core: Unique watch time from playback rangesTranscoder crash Resumable upload → parallel transcoding into an HLS/DASH bitrate ladder → object storage → CDN; adaptive bitrate in the player; heartbeats for progress and watch time. new Design a Ride-Hailing Service Hard ★★★ System design Store driver locations in a SQL table and run 'ORDER BY distance LIMIT 10' over all drivers per request. breaks at scale Partition by city/region; keep live driver locations in memory in a geospatial index (geohash/H3 cells or a quadtree) updated by… Estimates, trade-offs core: O(n log k) 3 failure modes · core: k nearest driversLocation service lag Per-city in-memory geo index (H3/geohash) fed by streamed GPS; matching ranks nearby candidates by ETA and offers with timeouts; trips as a consistent state machine. new Design a Payment System Hard ★★★ quant System design On 'Pay', call the card processor and update a balance column; if the request times out, the client retries. breaks at scale Every request carries an idempotency key; a payment service records intent and outcome per key (so retries return the original… Estimates, trade-offs core: O(1) per call 3 failure modes · core: Idempotent transfers on a ledgerTimeout after charge Idempotency keys on every write, a payment state machine, an append-only double-entry ledger in ACID transactions, outbox events, and daily reconciliation. new Design a Real-Time Leaderboard Medium ★★★ quant System design UPDATE scores SET score = score + x, then SELECT … ORDER BY score DESC LIMIT 100 on every read. breaks at scale Keep scores in an in-memory sorted structure: Redis sorted sets (skip list + hash) give O(log n) updates, top-N and rank.… Estimates, trade-offs core: O(1) update, O(n log K) top 2 failure modes · core: Leaderboard (top-K sum)Redis node loss Redis sorted sets (skip list + hash) for O(log n) updates and ranks, a cached top N, and an event log for durability and audits. new Design a Metrics & Monitoring System Medium ★★★ quant System design Insert every sample as a row in a relational table and run GROUP BY time queries. breaks at scale Agents push (or servers pull) samples to an ingestion tier that writes to a time-series database: series are sharded by (metric,… Estimates, trade-offs core: O(n) 3 failure modes · core: Downsample a time series into bucketsIngestion spike Agents → buffered ingestion → sharded TSDB with compressed blocks and rollups (count/sum/min/max/sketch) → query engine and alert manager. new Design a Market Data Feed Handler Hard ★★★ quant System design One thread reads TCP data, parses into objects, updates books in a hash map of linked lists, and publishes… breaks at scale Kernel-bypass NICs receive both multicast lines; an arbiter dedupes by sequence number; a gap detector tracks the next expected… Estimates, trade-offs core: O(n log n) 3 failure modes · core: Sequence gap detectionPacket loss on both lines Kernel-bypass receive of A/B multicast → sequence arbitration → gap detection with retransmit/snapshot recovery → preallocated book arrays → lock-free shared-memory rings to strategies. new Design an Exchange Matching Engine Hard ★★★ quant System design A database-backed order table with SQL queries to find matching orders, shared by many threads with locks. breaks at scale Gateways validate and sequence orders into a single ordered input log per partition (symbol group); a single-threaded, in-memory… Estimates, trade-offs core: O(n log n) 3 failure modes · core: Auction uncrossing pricePrimary crash Gateways → sequencer/journal → single-threaded deterministic matching per partition with in-memory price levels; hot standby replays the journal; auctions maximise executable volume. new Design a Search Engine (Inverted Index) Hard ★★★ System design For each query, scan every document for the words (grep). breaks at scale Build an inverted index: for each term, a sorted posting list of document IDs (with positions and frequencies). Shard by… Estimates, trade-offs core: O(Σ|postings of query terms|) 2 failure modes · core: Inverted index with AND queriesSlow shard (tail latency) Inverted index with sorted posting lists, document-partitioned shards with replicas, broker fan-out and top-k merge, BM25 + re-ranking, segment-based updates. new Design a Real-Time P&L and Risk System Hard ★★★ quant System design A nightly batch job recomputes P&L from the database of trades. breaks at scale An event-sourced stream processor: fills (deduped by execution id) and conflated prices flow through Kafka, partitioned by… Estimates, trade-offs core: O(n) 3 failure modes · core: Realised P&L with FIFO lotsDuplicate fill delivery Event-sourced stream processing: deduped fills and conflated prices partitioned by account; in-memory FIFO lot queues for realised P&L, mark-to-market for unrealised; checkpoints + replay for exactly-once. new