Data Structures & Algorithms Core Patterns
Master essential coding patterns from Big O analysis, sliding windows, and linked lists to binary search trees, heaps, graphs, and dynamic programming.
Master essential coding patterns from Big O analysis, sliding windows, and linked lists to binary search trees, heaps, graphs, and dynamic programming.
Big O Notation: Time & Space Complexity
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
Dynamic Arrays & Amortized Resizing
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
Two Pointers Pattern (Converging & Symmetrical)
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.
Fast & Slow Pointers (Floyd's Cycle Detection)
Two pointers moving at different speeds must eventually meet inside a loop, the way a faster runner laps a slower one. That detects a cycle in `O(N)` time and `O(1)` space, with no visited set.
Sliding Window Pattern (Fixed & Dynamic)
Recomputing each subarray from scratch is `O(N^2)`. A sliding window adds the entering element and subtracts the leaving one, so each step is `O(1)` and the whole scan finishes in `O(N)`.
Linked Lists & In-Place Reversal
Reversing a list in place is three pointers and one loop: remember `next`, flip the link backwards, step forward. Nothing is copied, so it costs `O(1)` extra space.
Stacks & The Monotonic Stack Pattern
A monotonic stack discards anything the incoming element beats, so its contents stay ordered. Each item is pushed and popped at most once, which is why "next greater element" is `O(N)` and not `O(N^2)`.
Queues, Deques & Circular Ring Buffers
Shifting an array on every dequeue costs `O(N)`. A ring buffer moves two indices with modulo arithmetic instead, so both ends stay `O(1)` and the elements never move.
Hash Maps & Collision Resolution Strategies
A hash map is `O(1)` only while collisions stay rare. As the load factor climbs, buckets turn into lists and lookup degrades toward `O(N)`, which is why the table resizes before it fills.
Prefix Sum & Difference Arrays
Precomputing running totals turns any range sum into one subtraction: `prefix[R+1] - prefix[L]`. Queries drop from `O(N)` each to `O(1)`, paid for once by an `O(N)` build.
Recursion & Call Stack Frames
Every recursive call pauses the current frame and stacks a new one holding its own variables. Without a base case the stack keeps growing until the engine refuses, at roughly 10,000 frames.
Backtracking: State Space Trees & Subsets
Backtracking walks a decision tree and undoes each choice on the way back out. That `unchoose` step is what lets one array serve every branch instead of copying the partial result at each of the N levels.
Binary Search: Standard & Bisect Boundaries
A linear scan checks every element. Halving the search space each step turns 1,000,000 candidates into roughly 20 comparisons, but only because the data is already sorted.
Sorting: Merge Sort & Quick Sort Mechanics
Both average `O(N log N)`, but merge sort guarantees it and stays stable at the cost of `O(N)` scratch space. Quick sort sorts in place and degrades to `O(N^2)` on a bad pivot.
Binary Trees & Binary Search Trees (BST)
A BST keeps every left descendant below the node and every right above it. That invariant is what buys `O(log N)` lookup, and why an unbalanced tree collapses back to `O(N)`.
Tree Traversals (Pre-order, In-order, Post-order)
Pre-, in- and post-order differ only in when a node is read relative to its children, and all three visit every node once in `O(N)`. In-order on a BST emits the values already sorted; the other two cannot.
Level-Order Traversal (BFS) using Queues
A queue is what makes BFS level-ordered: children join behind everything already waiting. Recording the queue's length at the start of each round is what separates one level from the next, in `O(N)`.
Lowest Common Ancestor (LCA) in Binary Trees
If the two targets sit in different subtrees, the current node is their meeting point. That single observation solves LCA in one post-order `O(N)` pass with no parent pointers.
Heaps & Priority Queues (Min-Heap / Max-Heap)
A heap only guarantees each parent beats its children, never a full ordering. That weaker promise is exactly what makes the top element `O(1)` to read and `O(log N)` to replace.
Tries (Prefix Trees) for String Search
A trie spends one node per character, so lookup costs `O(L)` in the length of the word and never depends on how many words are stored. That is what makes prefix search cheap where a hash set cannot help.
Graph Representations: Adjacency List vs. Matrix
An adjacency matrix answers "is there an edge?" in `O(1)` but costs `O(V^2)` memory. A list flips the trade: `O(V + E)` space, but checking one edge means scanning a neighbour list.
Graph Traversals: BFS & DFS for Connected Components
BFS and DFS visit the same vertices and differ only in order. On an unweighted graph BFS reaches each node by fewest edges (why it finds shortest paths and DFS cannot), both in `O(V + E)`.
Topological Sort (Kahn's Algorithm & DAGs)
Kahn's algorithm repeatedly takes any node with zero remaining dependencies. If the queue empties before every node is emitted, whatever is left forms a cycle: cycle detection for free in `O(V + E)`.
Dijkstra's Algorithm: Weighted Shortest Path
Dijkstra always expands the closest unvisited node, so the first time it reaches a vertex that distance is already final. The guarantee holds in `O(E log V)` and breaks the moment an edge weight goes negative.
Disjoint Set Union (Union-Find) with Path Compression
Union-Find flattens each chain as it walks it, so repeated lookups get cheaper rather than slower. With path compression and union by rank, `find` settles at a near-constant `O(alpha(N))`.
Dynamic Programming: Memoization vs. Tabulation
Plain recursion recomputes `F(3)` on both branches of `F(5)`. Storing each result once collapses an exponential call tree into a linear pass: memoisation top-down, tabulation bottom-up.
The 0/1 Knapsack & Unbounded Knapsack Pattern
At every item you face one binary choice: take it or leave it. Dynamic programming caches the best value for each remaining capacity, so `dp[i][c]` is computed once instead of re-derived down every branch.
Longest Common Subsequence (LCS) & 2D DP
LCS compares two strings as a grid: matching characters add 1 to the diagonal, mismatches inherit the better neighbour. The answer ends up in `dp[m][n]`, filled in `O(m * n)`.
Intervals Pattern: Merging & Overlap Logic
Sorting by start time means an interval can only overlap the one immediately before it. That turns a pairwise comparison into a single pass, `O(N log N)` overall and dominated by the sort.
Bit Manipulation Tricks & Bitmasks
XOR cancels a value against itself, so `1 ^ 1 = 0`. That one property isolates the single unpaired number in an array using `O(1)` space and no hash map at all.