Data Structures & Algorithms — Quick Summary

Quick revision: every topic, key terms, and mnemonics for Data Structures & Algorithms.

This is a quick revision doc covering all 40 topics in the DSA collection. Open the linked notes if you want depth — this is for fast pre-interview cementing of patterns.

Complexity & Fundamentals

Big O Notation

What it is. A way to describe how runtime / memory grows with input size. We care about growth rate, not constants.

Key terms.

• Common classes — O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2^n) → O(n!).
• Drop constants and lower terms — O(2n + 3) = O(n); O(n² + n) = O(n²).
• Time vs space — always state both.
• Time-space trade-off — extra memory (e.g. hash map) often beats nested loops.

Remember. “Constants Don’t Matter; Big Terms Win.” For n=1B, O(log n) ≈ 30 steps; O(n²) ≈ heat death of the universe.

Recursion

What it is. A function that calls itself with a smaller input until a base case.

Key terms.

• Base case — stops the recursion. Forget it → stack overflow.
• Recursive case — must shrink the problem.
• Call stack — each call is a frame; frames pop in reverse (LIFO).
• Recursion vs iteration — recursion shines for trees / divide-and-conquer; iteration is better for linear traversal (no stack overhead).

Remember. “Base + smaller subproblem.” Russian-doll mental model — open until smallest, then assemble back up.

Bit Manipulation

What it is. Direct work with binary digits — fast and O(1).

Key tricks.

• n & 1 — odd?
• n << 1, n >> 1 — multiply / divide by 2.
• n & (n - 1) — clears the lowest set bit. Repeat to count set bits (Hamming weight).
• n & (-n) — isolates the lowest set bit.
• (n >> k) & 1 — read bit k. n | (1 << k) — set. n & ~(1 << k) — clear. n ^ (1 << k) — toggle.
• XOR properties — a ^ a = 0, a ^ 0 = a, commutative. → “single number in array” in O(1) space.
• Power of 2 — n > 0 && (n & (n - 1)) === 0.

Remember. “XOR = different bits. Pairs cancel.”

Two Pointers

What it is. Two indices traversing data together. Three flavors:

Remember. Sorted array + “find a pair” → two pointers from both ends. O(n) with O(1) space.

Sliding Window

What it is. Maintain a contiguous window over an array/string and slide it.

Two flavors.

• Fixed-size — size given (k). Add new element, remove leaving element. Constant updates.
• Variable-size — expand right pointer; shrink left while window is invalid; track best.

Template.

left = 0
for right in range(len(arr)):
    # add arr[right] to state
    while invalid:
        # remove arr[left] from state
        left += 1
    result = best(result, right - left + 1)

Remember. “Contiguous + max/min/longest/shortest” → sliding window. Each element enters and leaves once → amortized O(n).

Arrays, Strings & Hashing

Arrays & Operations

What it is. Contiguous memory; O(1) random access via address arithmetic.

Key terms.

• Static vs dynamic — fixed size vs auto-resize (amortized O(1) append).
• Costs — access O(1); search O(n) unsorted / O(log n) sorted; insert/delete at end O(1); insert/delete in middle O(n) (shift).
• Reverse — two pointers swapping inward, O(n)/O(1).
• Rotate by k — three reverses: [0..k-1], [k..n-1], [0..n-1]. O(n)/O(1).

Strings & Pattern Matching

What it is. Strings are arrays of characters. Immutable in JS/Python/Java String → concatenation in a loop is O(n²).

Key idioms.

• Use StringBuilder/list+join for repeated concatenation.
• Palindrome — two pointers from both ends.
• Anagram — frequency count (length-26 array for lowercase).
• First non-repeating — two-pass frequency.
• Java gotcha — == compares references for strings; always use .equals().

Hash Maps & Hash Sets

What it is. Hash function maps keys to buckets. Average O(1) insert/lookup/delete.

Key terms.

• Collision — two keys hash to same bucket. Resolved by chaining (linked list per bucket) or open addressing (probing).
• Worst case O(n) when everything collides.
• Map vs Set — map = key→value; set = keys only (existence check).
• Two Sum — store value→index, look for target - num already seen.
• Frequency map / set for duplicates — turns O(n²) brute force into O(n).

Remember. “Stuck on a brute-force O(n²) pair check? Try a hash map.”

Prefix Sum & Difference Arrays

What it is.

• Prefix sum — precompute cumulative sums; range sum in O(1) after O(n) build. range(l, r) = prefix[r] - prefix[l-1].
• Subarray Sum Equals K — prefix sum + hash map of seen sums → O(n).
• Difference array — for range UPDATES: diff[l] += v; diff[r+1] -= v. Reconstruct with prefix sum.

Remember. “Prefix = fast queries. Difference = fast updates.”

Matrix Problems

What it is. 2D arrays — matrix[row][col]. Stored row-major.

Key patterns.

• Spiral traversal — four boundaries (top/bottom/left/right), shrink inward after each side.
• Rotate 90° clockwise — transpose (swap across main diagonal) + reverse each row. (CCW = transpose + reverse columns. 180° = reverse rows + reverse columns.)
• Search in row+col sorted matrix — start from top-right corner; go left if too big, down if too small. O(m + n).
• Grid BFS/DFS — treat each cell as a graph node.

Sorting Algorithms

What it is. Arranging elements in order.

Key terms.

• Stable — preserves relative order of equal elements. Matters when sorting by multiple keys.
• Built-in sorts — Python Timsort (stable), Java Arrays.sort for objects (stable, mergesort), JS engines (typically Timsort/quicksort hybrid). JS gotcha: default .sort() is lexicographic — pass (a,b)=>a-b for numbers.
• Custom comparator — sort objects by any key.

Remember. “Sorting is O(n log n), so it’s ‘free’ if your overall algorithm is already O(n log n) or worse.”

Linked Lists, Stacks & Queues

Linked Lists

What it is. Nodes with a value + pointer(s) to other nodes. Singly = next; Doubly = prev + next.

Key terms.

• Trade-off — O(1) insert/delete given a pointer; O(n) random access.
• Dummy node — sentinel head simplifies edge cases (deleting the head, merging).
• Reverse — three pointers prev / curr / next; iterate flipping links.
• Floyd’s cycle detection — slow=1, fast=2; meet → cycle.
• Find middle — slow=1, fast=2; when fast hits null, slow is middle.
• Merge two sorted — dummy + walk both, attach smaller, advance.

def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev, curr = curr, nxt
    return prev

Remember. “prev / curr / next.” Three pointers — every linked-list problem.

Stacks

What it is. LIFO. Push/pop/peek/isEmpty all O(1).

Implementations. JS array, Python list, Java ArrayDeque (avoid legacy java.util.Stack).

Patterns.

• Valid parentheses — push openers, pop and match on closers.
• Next greater element (right→left) — pop smaller-or-equal entries, top is next greater.
• Min Stack — store (value, current_min) pairs (or auxiliary min stack).
• Iterative DFS — explicit stack instead of recursion.

Remember. Call stack = function calls; same data structure powers recursion itself.

Monotonic Stack

What it is. Stack kept in sorted order. Each element pushed and popped at most once → amortized O(n).

Cheat sheet.

Classic problems. Next greater element, daily temperatures, largest rectangle in histogram (use 0-sentinel at end).

Queues and Deques

What it is. FIFO queue (enqueue back, dequeue front). Deque allows both ends in O(1).

Implementations. JS array (note: shift is O(n)), Python collections.deque, Java LinkedList/ArrayDeque.

Use cases.

• BFS is built on a queue.
• Sliding window maximum — monotonic decreasing deque storing indices; front holds current max.

Remember. “BFS = queue. DFS = stack. Sliding window max = monotonic deque.”

Priority Queues and Heaps

What it is. Heap = complete binary tree as an array. Min-heap: parent ≤ children. Max-heap: parent ≥ children.

Key terms.

• Indices — parent (i-1)/2, left 2i+1, right 2i+2.
• Operations — push O(log n), pop O(log n), peek O(1), heapify (build) O(n).
• Python heapq — min-heap only; for max-heap, push -val.
• Java PriorityQueue — min by default; Collections.reverseOrder() for max.
• JS — no built-in; implement a quick MinHeap class.

Patterns.

• Top K frequent / largest — min-heap of size K; pop when oversized → O(n log k).
• Merge K sorted lists — heap of K head nodes → O(N log k).
• Median of stream — two heaps: max-heap for lower half, min-heap for upper half.

Remember. “Find Top K → min-heap of size K.” “Sort O(n log n) > Top-K O(n log k) when k is small.”

Data Structure Design Problems

What it is. Build a custom DS with required ops at required complexities.

Key designs.

• Min Stack — pairs of (value, min_so_far) in one stack. All ops O(1).
• LRU Cache — hash map (key → node) + doubly linked list (head=most recent, tail=least). Both get and put O(1). On access: move node to head; on insert when full: evict tail.
• LFU, Implement Queue using Stacks (two stacks: in/out), Tic-Tac-Toe, Random Pick with Weight — interview classics.

Remember. “Hash map + doubly linked list = O(1) cache.”

Trees & Tries

Binary Trees

What it is. Each node has up to two children (left, right).

Terminology. Root, leaf, internal, depth (distance from root), height (longest path down to a leaf), subtree.

Traversals.

• Inorder (L-N-R) — for BST → sorted output.
• Preorder (N-L-R) — copy / serialize.
• Postorder (L-R-N) — delete / compute heights from leaves up.
• Level-order (BFS) — queue, prints level by level.

Common problems. Max depth (1 + max(left, right)), invert tree (swap children recursively), is symmetric (compare mirror), path sum, lowest common ancestor.

Binary Search Trees

What it is. BST property: every left descendant < node < every right descendant. Inorder traversal yields sorted order.

Operations. Search/insert/delete all O(log n) average, O(n) worst (degenerate to linked list — needs balancing for guaranteed log n).

Delete cases.

1. Leaf — just remove.
2. One child — replace with child.
3. Two children — replace with inorder successor (smallest in right subtree), then delete that.

Validate BST. Pass (min, max) bounds down recursively, NOT just node.left.val < node.val.

Binary Search

What it is. Halve search space each step on sorted data. O(log n).

Template.

lo, hi = 0, len(arr) - 1
while lo <= hi:
    mid = lo + (hi - lo) // 2  # avoid overflow
    if arr[mid] == target: return mid
    if arr[mid] < target: lo = mid + 1
    else: hi = mid - 1
return -1

Variants. First/last occurrence; rotated sorted array (find pivot first or compare halves); search for “boundary” where condition flips.

Remember. “lo + (hi - lo) / 2” — overflow-safe. Off-by-one is the #1 bug; pick <= vs < consistently.

Tree Construction and Serialization

What it is. Build trees from traversals or convert to/from strings.

Key facts.

• Single traversal is ambiguous. Need TWO traversals to uniquely reconstruct.
• Preorder + Inorder — preorder[0] is root; find it in inorder; left of it = left subtree, right = right subtree. Recurse.
• Postorder + Inorder — postorder[-1] is root; same idea.
• Serialize/deserialize — preorder with null markers for missing children.

Lowest Common Ancestor

What it is. Deepest node that is ancestor of both p and q.

BST version. If both < root → recurse left; both > root → recurse right; otherwise root is the LCA. O(log n).

General binary tree. Recursive: if root is p or q, return root. Recurse left/right. If both return non-null → root is LCA; else return whichever is non-null. O(n).

Remember. Distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA).

Tries (Prefix Trees)

What it is. Tree where each node = a character. Word = path from root to a node marked isEnd. Children stored as map/array.

Operations. Insert / search word / search prefix — all O(L) where L = word length.

When to use. Autocomplete, spell-check, prefix queries on a dictionary, word games. Replace hash map when prefix queries matter.

Memory. More than a hash set, but shared prefixes save memory and enable prefix iteration.

Graphs

Graph Representations

What it is. Nodes (vertices) + edges. Directed vs undirected, weighted vs unweighted, cyclic vs acyclic.

Two representations.

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # undirected

BFS and DFS

What it is. Two ways to explore a graph.

BFS. Queue. Level-by-level. Shortest path in unweighted graphs. O(V + E). DFS. Stack or recursion. Goes deep first. Path existence, connected components, cycle detection. O(V + E).

def bfs(graph, start):
    visited = {start}
    q = deque([start])
    while q:
        node = q.popleft()
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                q.append(nb)

Remember. “BFS = ripples (queue). DFS = caves (stack/recursion).”

Topological Sort

What it is. Linear ordering of DAG nodes such that for every edge u→v, u comes before v. Used for dependency resolution (course schedule, build systems).

Two algorithms.

• Kahn’s (BFS) — start with all in-degree-0 nodes; pop, decrement neighbor in-degrees, push new zeros. If output count < V → cycle exists, no valid order.
• DFS-based — postorder DFS, push to stack; reverse stack at end.

Remember. “DAG only. Cycle → no topo order.”

Shortest Path Algorithms

Decision tree.

• Unweighted? → BFS. O(V + E).
• Weighted, no negatives? → Dijkstra’s (greedy + min-heap). O((V + E) log V).
• Negative weights? → Bellman-Ford (relax all edges V-1 times). O(V × E). Detects negative cycles.
• All-pairs? → Floyd-Warshall (3 nested loops). O(V³).

Dijkstra in 3 lines. Min-heap of (dist, node). Pop closest, relax neighbors. Skip if popped dist > known dist.

Remember. “BFS for hops. Dijkstra for happy weights. Bellman-Ford for negatives.”

Union-Find (Disjoint Set)

What it is. Track connected components. find(x) returns root of x’s group; union(x, y) merges two groups.

Optimizations.

• Path compression — on find, point each visited node directly to root.
• Union by rank/size — attach smaller tree under larger root.
• Combined → near-O(1) amortized (technically O(α(n)), inverse Ackermann).

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # path compression
    return parent[x]

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry: return False
    if rank[rx] < rank[ry]: rx, ry = ry, rx
    parent[ry] = rx
    if rank[rx] == rank[ry]: rank[rx] += 1
    return True

When to use. Streaming connectivity (“is X still connected to Y after these edges?”), Kruskal’s MST, number of connected components, redundant edge detection.

Advanced Graph Problems

Cycle detection (directed). 3-color DFS — white (unseen), gray (in current path), black (done). Gray edge encountered → cycle.

Cycle detection (undirected). DFS with parent — if neighbor visited and not parent → cycle. Or Union-Find: union returns false on existing edge → cycle.

Bipartite check. 2-color BFS — color start, alternate colors per level; conflict → not bipartite.

MST (Minimum Spanning Tree).

• Kruskal’s — sort edges by weight, add edges that don’t form a cycle (Union-Find). O(E log E).
• Prim’s — grow tree from a node using min-heap. O(E log V).

Tarjan’s / Kosaraju’s — strongly connected components.

Dynamic Programming

DP Fundamentals

What it is. Solve problem by combining solutions to overlapping subproblems. Two requirements: overlapping subproblems + optimal substructure.

Two approaches.

• Memoization (top-down) — recursion + cache.
• Tabulation (bottom-up) — fill table iteratively from base cases.

Naive fib O(2^n) → memoized O(n) → bottom-up O(n) → space-optimized O(1) (rolling variables).

Steps. 1) Define state dp[i] (or dp[i][j]). 2) Recurrence — express dp[i] from prior states. 3) Base cases. 4) Iterate in dependency order.

Remember. “DP = remember answers.” If you’re recomputing the same thing, cache it.

1D DP Patterns

Climbing stairs. dp[i] = dp[i-1] + dp[i-2]. Pure Fibonacci.

House Robber. dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — skip or take.

Coin Change (min coins for target). dp[a] = min(dp[a - coin] + 1 for coin in coins). O(amount × coins).

LIS (Longest Increasing Subsequence). dp[i] = 1 + max(dp[j] for j<i where nums[j]<nums[i]). O(n²). Or O(n log n) with patience sort + binary search.

Word Break. dp[i] = any(dp[j] and s[j:i] in wordSet for j in 0..i).

Decode Ways. Like climbing stairs but with validity checks on 1- and 2-digit substrings.

2D DP Patterns

Unique Paths. dp[i][j] = dp[i-1][j] + dp[i][j-1]. First row/col = 1.

Min Path Sum. dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).

Longest Common Subsequence.

• If s1[i] == s2[j] → dp[i][j] = dp[i-1][j-1] + 1.
• Else → max(dp[i-1][j], dp[i][j-1]).

Edit Distance (Levenshtein). Min operations (insert, delete, replace). If chars match → dp[i-1][j-1]. Else → 1 + min(insert, delete, replace).

Remember. Many 2D DP problems can be space-optimized to 1D (or two rows).

Knapsack Patterns

0/1 Knapsack. Each item used at most once. dp[i][w] = max(skip, take if fits) = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i]). O(n × W).

Unbounded Knapsack. Can reuse items. Coin Change is unbounded knapsack. dp[w] = max(dp[w-wt[i]] + val[i]) for all items i.

Subset Sum / Partition Equal Subset Sum. Boolean DP: can we reach sum s? dp[s] = dp[s] or dp[s - num].

Target Sum / Counting Subsets. Count ways instead of yes/no.

Remember. “0/1 = take or skip. Unbounded = take or skip-and-stay (don’t advance i).”

Interval and String DP

Pattern. dp[i][j] = answer for substring/range [i..j]. Build from smallest length to largest.

Longest Palindromic Subsequence. If s[i]==s[j]: dp[i+1][j-1] + 2. Else: max(dp[i+1][j], dp[i][j-1]).

Longest Palindromic Substring. Either expand from each center (O(n²)/O(1)) or DP with dp[i][j] = (s[i]==s[j]) and dp[i+1][j-1].

Palindrome Partitioning II (min cuts), Matrix Chain Multiplication — classic interval DP.

Remember. “Length 1 → length 2 → … → length n. Outer loop = length, inner = start index.”

DP on Trees and Graphs

What it is. State per node, computed bottom-up via post-order DFS.

House Robber III. Each node returns (rob_this, skip_this). Rob = val + skip both kids; Skip = max of both for each kid.

Diameter of a Tree. Track longest path through each node = left_height + right_height. Return max(left, right) + 1 upward.

Path Sum III, Longest Univalue Path — same shape: post-order, return one value, accumulate global answer.

For DAGs, use memoization with topological order. Tree DP doesn’t need memo because each subtree is visited once.

Greedy, Backtracking & Interview Patterns

Greedy Algorithms

What it is. Make the locally optimal choice; never reconsider.

When greedy works. Greedy choice property + optimal substructure. Always test with a small counterexample.

Classics.

• Activity Selection / Interval Scheduling — sort by end time; pick earliest-ending non-overlapping.
• Jump Game — track farthest reachable; if i > farthest → fail.
• Gas Station — total > 0 → solution exists; restart from i+1 whenever tank goes negative.
• Fractional Knapsack — sort by value/weight ratio. (0/1 needs DP, NOT greedy.)
• Huffman coding, Dijkstra, Kruskal/Prim — all greedy.

Remember. “Sort, scan, decide.” If greedy fails, you probably need DP.

Backtracking

What it is. DFS with undo. Try a choice → recurse → undo → try next.

Universal template.

def backtrack(path, choices):
    if goal(path):
        result.append(path[:])  # copy!
        return
    for c in choices:
        if not valid(c, path): continue
        path.append(c)          # choose
        backtrack(path, ...)    # explore
        path.pop()              # un-choose

Classics. Subsets (2^n), Permutations (n!), Combinations C(n,k), N-Queens, Sudoku, Word Search, Combination Sum.

Pruning. Sort + skip duplicates; bound checks; constraint propagation. Pruning is the difference between “elegant” and “TLE”.

Remember. “Choose, explore, un-choose.” Always copy the path on goal hit (not the reference).

Interval Problems

What it is. Problems on [start, end] ranges. Almost always sort by start (sometimes by end) first.

Key trick — overlap. Two intervals [a,b] and [c,d] overlap iff a < d AND c < b.

Classics.

• Merge Intervals — sort by start; if intervals[i].start <= last.end, extend last; else push new.
• Insert Interval — three phases: append non-overlapping before, merge overlapping middle, append rest.
• Meeting Rooms II (min rooms) — min-heap of end times; if next start ≥ heap min, reuse (pop); push new end. Heap size = answer.
• Non-overlapping Intervals — sort by end; greedily keep earliest-ending; count removals.

Sweep line technique. Convert each interval to two events (+1 at start, -1 at end), sort, sweep with running counter.

Remember. “Sort by start, then iterate. Two intervals: extend or push.”

Binary Search on Answer

What it is. Binary search the SOLUTION SPACE, not the array. Works when feasibility is monotonic in the answer.

Recognition.

• “Minimize the maximum…”
• “Maximize the minimum…”
• “What’s the smallest X that satisfies a constraint?”

Template. lo, hi = min_possible, max_possible. While lo < hi: mid = (lo+hi)//2. If feasible(mid) → hi = mid (try smaller). Else → lo = mid + 1. Return lo.

Classics. Koko Eating Bananas (smallest speed to finish in H hours), Capacity to Ship Within D Days, Split Array Largest Sum, Minimum Pages (book allocation).

Remember. “Define feasible(x). If yes for x, also yes for x+1 → binary searchable.”

Common Interview Patterns Cheatsheet

Pattern → trigger keywords.

Big-O Cheatsheet (operations across data structures)

Remember. “Hash for lookup. Heap for top-K. Trie for prefix. Union-Find for components. Stack for LIFO/parens. Queue for BFS/scheduling.”