Data structures and algorithms, as patterns.
The 154 patterns behind the questions Google asks, each with a short video that runs the real algorithm on one example, step by step.
How to read these notes
Google's DSA interview questions repeat a small number of ideas. These notes list every one of those ideas as a pattern: a one-line idea, the invariant the code keeps true, when to reach for it, and the Google-tagged LeetCode problems it solves. The source is the public LeetCode company-tag export: 2,324 Google-tagged problems, of which 784 are mapped here across 27 topics.
Every pattern has a 42 s video on average (108 minutes in all): a title card, the algorithm run on one small input with a caption per step and the state on screen, then a recap of the invariant, the complexity and the problems. The steps are also written out under each video. Read a topic top to bottom, or search the sidebar for a problem name you have been asked. The sidebar ticks the patterns you have finished, in this browser only.
Difficulty colours and frequencies come from LeetCode; "last 6 months" marks problems reported in the most recent window of the export.
Arrays and strings
Arrays & Hashing
Answering questions about an array in one pass by remembering what you have already seen.
- 001 · Hash the complement One pass: look up what you still need, then store what you have.
- 002 · Frequency counting Count first; the answer is a question about the counts.
- 003 · Canonical key hashing Map each item to a canonical form; equal forms share a bucket.
- 004 · In-place index hashing Values 1..n: mark presence by negating or swapping into slot value-1.
- 005 · Set-start expansion Only start a run from numbers whose predecessor is absent.
- 006 · Seen-set cycle detection Repeating a deterministic step: a repeated state means a cycle.
Prefix Sums
Precompute running totals so any range becomes a subtraction.
- 007 · Prefix sum + hashmap Subarray sum = prefix[j] − prefix[i]; count earlier prefixes worth prefix[j] − k.
- 008 · Prefix and suffix products Answer at i = everything to the left × everything to the right.
- 009 · Difference array (range add) Add at l, subtract at r+1; a prefix sum replays every range update.
- 010 · 2D prefix sums Rectangle sum from four corner lookups by inclusion–exclusion.
Two Pointers
Two indices that move with purpose so the whole array is covered in one pass.
- 011 · Opposite ends converge Sorted: too small → move left up, too big → move right down.
- 012 · Fix one, two-pointer the rest Sort, pin index i, solve a 2-sum on the suffix; skip duplicates.
- 013 · Reader / writer pointers The writer trails the reader and keeps only what qualifies.
- 014 · Dutch national flag partition Three regions: lows, unknown, highs; one pass with low/mid/high pointers.
- 015 · Merge two sorted sequences Compare heads, take the smaller, advance that side.
- 016 · Two-sided max walls Water at i is bounded by the smaller side's running max; advance the smaller side.
Sliding Window
A contiguous range that grows and shrinks while a running aggregate stays exact.
- 017 · Fixed-size window Slide a width-k window: add the new right, drop the old left.
- 018 · Longest valid window Grow right; while invalid, shrink left; record the longest valid span.
- 019 · Shortest satisfying window Grow right until the window satisfies; shrink left while it still does.
- 020 · Count windows via at-most(k) trick exactly(k) = atMost(k) − atMost(k−1); each window end adds r−l+1 subarrays.
- 021 · Window with a need-counter Track how many required characters are still missing; zero means satisfied.
String Algorithms
Matching, hashing, parsing and rebuilding strings without quadratic rescans.
- 124 · KMP failure function The prefix table lets a mismatch jump without re-scanning the text.
- 125 · Rolling hash (Rabin–Karp) Hash a window; slide by removing the left char and adding the right.
- 126 · Reverse-and-build string transforms Reverse in chunks, or build the answer backwards with a buffer.
- 127 · Parse with a state machine Walk characters once with explicit states: sign, digits, overflow guard.
- 128 · Merge / compare two strings in lockstep Advance pointers through both strings together; handle leftovers.
- 152 · Multi-pattern scan with a set of lengths For each position try every dictionary length; a hash set makes each check O(L).
Stacks and queues
Stack
Last in, first out: matching, nesting, expression evaluation and collision simulation.
- 022 · Matching with a stack Push openers; a closer must match the top, then pop.
- 023 · Nested structure via stack On '[' push the current context; on ']' pop and fold the inner result into it.
- 024 · Expression evaluation Numbers to an operand stack; operators apply by precedence (or use RPN).
- 025 · Auxiliary-min stack Store (value, min-so-far) per push so the minimum pops away with its value.
- 026 · Collision simulation Push moving things; when a newcomer collides with the top, resolve and maybe keep popping.
Monotonic Stack
A stack kept sorted so each element learns its nearest greater or smaller neighbour in amortised O(1).
- 027 · Next greater element Keep a decreasing stack; a bigger newcomer resolves everything smaller on top.
- 028 · Largest rectangle (bounds by pops) An increasing stack; popping a bar fixes its left and right smaller neighbours.
- 029 · Greedy removal with a stack Pop a bigger previous digit while you still have removals left.
- 030 · Previous and next smaller (both sides) One pass finds both neighbours: the popped element's right bound is the popper.
Queue & Deque
First in, first out, and the deque that keeps only useful candidates.
- 031 · Monotonic deque window max A deque of candidates, decreasing; front is the window max; drop fronts that left the window.
- 032 · Queue over a time window Push timestamps; pop from the front while they fall outside the window.
- 033 · Queue from two stacks Push to inbox; when outbox is empty, pour inbox over so the order flips.
Searching and sorting
Binary Search
Halving a sorted range, a monotone predicate, or the answer space itself.
- 034 · Classic binary search Halve the sorted range by comparing with the middle.
- 035 · First true (predicate boundary) A monotone false…true predicate: find the first index where it flips.
- 036 · Binary search on the answer Guess an answer, check feasibility greedily, tighten the range.
- 037 · Rotated / mountain search One half is always sorted: decide which, then whether the target lives there.
- 038 · Partition two sorted arrays Binary search the cut in the shorter array so left halves hold exactly half the items.
Sorting
Sorting as a preprocessing step, and the partition and merge ideas behind it.
- 042 · Custom comparator / key sort Define 'better' pairwise or as a key, then sort once.
- 043 · Cyclic sort (1..n placement) Swap each value into its home index until every slot holds its own number.
- 044 · Quickselect (kth element) Partition around a pivot; recurse only into the side holding k.
- 045 · Merge sort with counting While merging, count cross pairs that violate the order.
- 046 · Bucket / counting sort Bounded keys: count into buckets instead of comparing.
Intervals
Sort by start or end, then sweep.
- 039 · Sort and merge intervals Sort by start; extend the current interval when the next one overlaps.
- 040 · Sweep line (events ±1) Turn intervals into +1/−1 events, sort, and sweep to track concurrency.
- 041 · Earliest finish first Sort by end; take an interval whenever it starts after the last chosen end.
Linked lists and design
Linked List
Pointer surgery with fast and slow runners, dummy heads and in-place reversal.
- 047 · Fast and slow pointers Two speeds: a cycle makes them meet; otherwise slow lands on the middle.
- 048 · In-place reversal Walk with prev/cur/next, flipping each pointer.
- 049 · Dummy head and splice A sentinel before head removes every 'is it the first node?' special case.
- 050 · Digit-by-digit with carry Walk both lists, add digits plus carry, emit one node per position.
- 051 · Clone with a map or interleaving Map old→new (or weave copies in between) so random pointers can be rewired.
Design
Composing a hash map with a list, a heap or a sorted structure to hit the required big-O per operation.
- 052 · Hash map + doubly linked list (LRU) A map for O(1) lookup, a list for O(1) recency moves; evict from the tail.
- 139 · Hash map + array for O(1) random Array for random access, map from value to its index; delete by swapping with the last.
- 140 · Time-versioned map Store (timestamp, value) lists per key; binary search the latest ≤ t.
- 141 · Lazy iterators Keep a stack/pointer so next() does O(1) work on average.
- 142 · Ordered intervals (range module) Keep disjoint sorted intervals; add merges neighbours, remove splits them.
- 151 · Streaming data structures Process one item at a time with O(1) or O(log n) state; never store the whole stream.
Trees, heaps and tries
Trees
Recursion that returns something upward, level-order traversal, and trees treated as graphs.
- 053 · Recursive DFS (post-order fold) Solve the children, then combine at the parent.
- 054 · Best path through each node Each node returns its best single-branch; the answer considers both branches joined at the node.
- 055 · Level-order BFS Process one level at a time: the queue length at loop start is the level size.
- 056 · Root-to-leaf path carry Pass accumulated state down; a leaf decides.
- 057 · Lowest common ancestor Return the found node upward; the first node that hears from both sides is the LCA.
- 058 · Build from traversals Preorder gives the root; inorder splits left from right.
- 059 · Iterative traversal with a stack Push the left spine; pop, visit, then push the right child's left spine.
- 060 · Column / coordinate traversal Tag each node with (column, row) while traversing, then group by column.
- 061 · Rerooting DP (sum over all roots) Compute the answer for one root, then shift to each child in O(1) using subtree sizes.
- 062 · Post-order deletion / pruning Decide at the parent after the children report; a deleted node promotes its children.
- 063 · Tree as a graph (parent pointers) Record parents, then BFS/DFS in every direction including upward.
- 064 · Tree DP: take or skip this node Each node returns two values: best if taken, best if skipped.
- 153 · Serialize / deserialize by BFS Write nodes level by level with null markers; rebuild with a queue of parents.
Binary Search Tree
Ordering gives you bounds, inorder gives you sorted order.
- 065 · BST range bounds Pass (low, high) downward; a node must sit strictly inside.
- 066 · Inorder = sorted order An inorder walk visits keys ascending; remember the previous key.
- 067 · BST insert / delete / search Walk left or right by comparison; delete replaces with the inorder successor.
- 068 · Build a balanced BST from sorted input The middle element becomes the root; recurse on each half.
Heap
A priority queue for the k best, two halves, k-way merges and scheduling.
- 069 · Top-k with a size-k heap Keep a min-heap of the k best; a newcomer replaces the root only if it beats it.
- 070 · Two heaps (running median) A max-heap for the lower half, a min-heap for the upper; keep sizes balanced.
- 071 · K-way merge Heap the head of each list; pop the smallest and push its successor.
- 072 · Greedy scheduling with a heap Sort by start; a heap of end times tells you the earliest room that frees up.
- 073 · Lazy deletion heap Keep stale entries in the heap; discard them when they surface.
- 074 · Pop-k-then-rebuild (frequency greedy) Always schedule the most frequent remaining item that is not on cooldown.
Trie
A tree of characters (or bits) for prefix and XOR queries.
- 121 · Trie for prefix queries A tree of characters; a path spells a word, a flag marks word ends.
- 122 · Trie-guided grid DFS Build a trie of all words; walk the grid and the trie together, pruning dead branches.
- 123 · Binary trie for maximum XOR Insert numbers bit by bit; for a query walk the opposite bit whenever possible.
Graphs
Graphs
Traversal, ordering, connectivity and shortest paths on explicit and implicit graphs.
- 075 · Grid flood fill (components) Treat cells as nodes; DFS/BFS from each unvisited land cell and mark the whole island.
- 076 · Multi-source BFS Seed the queue with every source; the first visit is the nearest source.
- 077 · BFS shortest path (unweighted) Layer by layer from the source; distance = number of layers.
- 078 · BFS over an augmented state The node is (position, extra state): keys held, obstacles left, parity.
- 079 · 0-1 BFS (deque) Edge weights 0 or 1: push cost-0 moves to the front, cost-1 to the back.
- 080 · DFS three-colour cycle detection White unvisited, grey on the current path, black done; a grey neighbour means a cycle.
- 081 · Topological sort (Kahn's) Queue every zero in-degree node; removing it may free its successors.
- 082 · Union–Find (disjoint sets) find with path compression, union by size; components merge in near O(1).
- 083 · Dijkstra (weighted shortest path) Pop the closest unsettled node; relax its edges; stale entries are skipped.
- 084 · Bellman–Ford with k rounds Relax every edge k+1 times from a copy of the previous round.
- 085 · Minimum spanning tree Kruskal: sort edges, union-find to skip cycles. Prim: grow from one node with a heap.
- 086 · Bipartite colouring BFS/DFS painting neighbours the opposite colour; a clash means odd cycle.
- 087 · Eulerian path (Hierholzer) Walk greedily, back out when stuck, and record nodes post-order; reverse at the end.
- 088 · Bridges / articulation (low-link) DFS timestamps; an edge is a bridge if the child cannot reach back above it.
- 089 · Clone / traverse with a visited map Map original→copy; create a node the first time you see it, reuse afterwards.
- 090 · Implicit graph (states as nodes) Define neighbours by a rule instead of an adjacency list; search as usual.
Recursion, DP and greedy
Backtracking
Build a candidate one choice at a time and undo on return.
- 091 · Subsets (include / exclude) At each index choose to take it or not; the leaf is one subset.
- 092 · Permutations with a used set Pick any unused element next; undo the pick when you return.
- 093 · Combination sum with a start index Only choose from index start onward so each combination is made once.
- 094 · Grid DFS with undo Mark the cell, explore four ways, unmark on return.
- 095 · Constraint placement with pruning Place one item per row/cell; check constraints before recursing; prune early.
- 096 · Generate valid sequences Add '(' while opens remain; add ')' only while closes < opens.
Dynamic Programming
Define the state, write the transition, pick the order to fill it.
- 097 · 1-D linear DP dp[i] from dp[i−1] and dp[i−2]; roll two variables.
- 098 · Kadane (best ending here) best ending at i = max(nums[i], best ending at i−1 + nums[i]).
- 099 · Longest increasing subsequence Patience piles: binary search where each number lands; pile count is the LIS length.
- 100 · Grid path DP dp[r][c] from the cell above and the cell to the left.
- 101 · 0/1 knapsack (subset sum) For each item, sweep capacities downward so each item is used once.
- 102 · Unbounded knapsack (coin change) Sweep capacities upward so an item can be reused.
- 103 · Two-sequence DP (LCS / edit distance) dp[i][j] compares prefixes; match takes the diagonal, else the best neighbour.
- 104 · Wildcard / regex matching DP A star either matches nothing (drop it) or eats one more character.
- 105 · Palindromes: expand or table Expand around each centre, or dp[i][j] = s[i]==s[j] and dp[i+1][j−1].
- 106 · Prefix segmentation DP dp[i] is true if some j < i has dp[j] true and s[j:i] in the dictionary.
- 107 · Interval DP (last operation) Choose the last element burst/removed in [i, j]; the sides become independent.
- 108 · State-machine DP (stocks) States: holding / not holding (plus cooldown); transitions carry the best cash.
- 109 · Bitmask DP over subsets The mask records which items are used; add one item per transition.
- 110 · Memoised DFS (top-down) Recurse on the natural subproblem and cache by its parameters.
- 111 · Digit DP Build the number digit by digit with a 'tight' flag and the needed state.
- 112 · Game DP (minimax on a range) Score difference view: best = max over moves of (gain − opponent's best).
- 113 · Counting ways with modulo Sum the ways from every predecessor state, mod 1e9+7.
- 114 · DP over sorted keys (chains) Sort by size; dp[item] extends from the best smaller item it can follow.
Greedy
Commit to the locally best choice when an exchange argument proves it safe.
- 115 · Furthest reach (jump game) Track the furthest index reachable; a new level starts when you pass the current edge.
- 116 · Sort, then take greedily Order by the key that an exchange argument proves safe, then commit one by one.
- 117 · Reset-on-negative sweep Walk once; whenever the running tank goes negative, restart from the next index.
- 118 · Last-occurrence partition Extend the current chunk to the last occurrence of every char inside it.
- 119 · Two-pass neighbour constraints Left-to-right fixes one side's rule, right-to-left fixes the other; take the max.
- 120 · Counting-based greedy (small alphabet) Count letters/values, then construct the best answer from the counts.
- 154 · Two-pointer assignment after sorting Sort both sides; match the smallest demand with the smallest supply that fits.
Math, bits and matrices
Bit Manipulation
XOR, masks and the lowest set bit.
- 129 · XOR cancels pairs a ⊕ a = 0, so pairs vanish and the lone element survives.
- 130 · Bit tricks (n & (n−1), masks) n & (n−1) clears the lowest set bit; shifts and masks build numbers without arithmetic.
- 131 · Enumerate subsets by mask Masks 0..2^n−1 encode every subset; bit i means item i is in.
Math
Number theory, digits, fast exponentiation, randomness and coordinate geometry.
- 132 · Fast exponentiation Square the base and halve the exponent; multiply in when the bit is set.
- 133 · GCD and number theory Euclid: gcd(a, b) = gcd(b, a mod b); primes by sieve.
- 134 · Digit-by-digit arithmetic Peel digits with % 10 and / 10; rebuild with ×10, guard overflow.
- 135 · Random pick and reservoir sampling Prefix sums + binary search for weighted pick; reservoir keeps each item with prob 1/i.
- 136 · Coordinate geometry with hashing Hash points or slopes; count rectangles/lines by pairs.
Matrix
Traversal orders and searches that use a matrix's structure.
- 137 · Matrix traversal and rotation Rotate = transpose then reverse rows; spiral = four shrinking bounds.
- 138 · Staircase search in a sorted matrix Start at the top-right: go left if too big, down if too small.
Advanced structures and simulation
Advanced Structures
Segment trees, Fenwick trees, ordered sets, bucketing and meet in the middle.
- 143 · Segment tree (range query + point update) A binary tree of ranges; a query visits O(log n) nodes, an update climbs one path.
- 144 · Fenwick tree (binary indexed tree) Prefix sums in O(log n) by walking the lowest set bit up and down.
- 145 · Ordered set / sorted container Keep a sorted multiset; bisect for neighbours, insert/delete in O(log n).
- 146 · Bucketing by value range Bucket id = value // (t+1); near values land in the same or neighbouring bucket.
- 147 · Matrix exponentiation for recurrences A linear recurrence is a matrix; raise it to the nth power by squaring.
- 150 · Meet in the middle Split into two halves, enumerate each, match complements with a sorted list or set.
Interactive
Problems where you query an oracle and must minimise the number of questions.
- 148 · Candidate elimination (Guess the Word) Guess the word that would split candidates most evenly; keep only consistent ones.
Simulation
Model the rules exactly with the smallest state that decides the next step.
- 149 · Careful state simulation Model the rules exactly; keep the state minimal and update it in order.