Cheatsheets

Revise at a glance

Complexity tables, pattern recognition guides and battle-tested code templates — everything you skim the night before the interview.

Sorting & Searching complexities Data structure operations Graph algorithms Classic DP problems Pattern recognition guide

Sorting & Searching complexities

n = input size, k = value range, d = digits.

AlgorithmBestAverageWorstSpaceStable
Bubble SortO(n)O(n²)O(n²)O(1)Yes
Selection SortO(n²)O(n²)O(n²)O(1)No
Insertion SortO(n)O(n²)O(n²)O(1)Yes
Merge SortO(n log n)O(n log n)O(n log n)O(n)Yes
Quick SortO(n log n)O(n log n)O(n²)O(log n)No
Heap SortO(n log n)O(n log n)O(n log n)O(1)No
Counting SortO(n+k)O(n+k)O(n+k)O(n+k)Yes
Radix SortO(nd)O(nd)O(nd)O(n+k)Yes
Binary SearchO(1)O(log n)O(log n)O(1)—
Linear SearchO(1)O(n)O(n)O(1)—

Data structure operations

Average-case costs. MC = min/max query.

StructureAccessSearchInsertDeleteNotes
ArrayO(1)O(n)O(n)O(n)Contiguous memory
Dynamic ArrayO(1)O(n)O(1)*O(n)*amortized push
Linked ListO(n)O(n)O(1)O(1)O(1) at known node
Hash Table—O(1)O(1)O(1)Worst O(n) collisions
BST (balanced)O(log n)O(log n)O(log n)O(log n)O(n) if unbalanced
HeapO(1) peekO(n)O(log n)O(log n)Min/max only
Trie—O(L)O(L)O(L)L = key length
Segment Tree—O(log n)O(log n)O(log n)Range queries
Fenwick (BIT)—O(log n)O(log n)—Prefix sums
Union-Find—O(α(n))O(α(n))—α ≈ constant

Graph algorithms

V = vertices, E = edges.

AlgorithmTimeSpaceUse when
BFSO(V+E)O(V)Shortest unweighted path, level order
DFSO(V+E)O(V)Components, cycles, topological order
Topological SortO(V+E)O(V)Ordering DAG tasks / prerequisites
Union-FindO(α(n))O(V)Dynamic connectivity, cycle detection
DijkstraO(E log V)O(V)Shortest path, non-negative weights
Bellman-FordO(V·E)O(V)Negative weights, negative cycles
Floyd-WarshallO(V³)O(V²)All-pairs shortest paths
Kruskal MSTO(E log E)O(V)MST via edge sorting + union-find
Prim MSTO(E log V)O(V)MST via priority queue
Kahn's ToposortO(V+E)O(V)Topological order via in-degrees

Classic DP problems

Recognize the state, the transition and the base case.

ProblemStateTransitionTime
Climbing Stairsways[i]ways[i-1] + ways[i-2]O(n)
House Robberrob[i]max(rob[i-1], rob[i-2] + v[i])O(n)
Coin Changemin[v]min(min[v-c] + 1) over coinsO(n·k)
0/1 Knapsackdp[i][w]max(skip, take + dp[i-1][w-wt])O(n·W)
LCSdp[i][j]match ? 1+dp[i-1][j-1] : max(left, up)O(n·m)
Edit Distancedp[i][j]min(insert, delete, replace)O(n·m)
LISlen[i]max over j<i where a[j]<a[i]O(n²) / O(n log n)
Unique Pathsdp[i][j]dp[i-1][j] + dp[i][j-1]O(n·m)
Partition Subsetsreach[s]reach[s] || reach[s - v[i]]O(n·S)

Pattern recognition guide

What the problem statement is telling you.

If the problem says…Think…
Sorted arrayBinary search or two pointers
Top / smallest K elementsHeap of size k
All combinations / permutationsBacktracking
Contiguous subarray or substringSliding window or prefix sums
Count ways to do XDynamic programming
Min/max cost to reach a goalDP or Dijkstra (on states)
Connected groups / componentsBFS/DFS or Union-Find
Dependencies / orderingTopological sort
Pairs that satisfy a conditionHash map or sort + two pointers
Overlapping rangesSort by start, sweep with heap
Fast lookup of seen itemsHash set / hash map
Linked list middle / cycleFast & slow pointers
Prefix of stringsTrie
Range sum / range min queriesPrefix sums / segment tree
Does path exist with constraintBFS/DFS over (state) graph

Code templates

The implementations you should be able to write from memory. Click to expand.

The loop invariant: everything < lo is excluded, everything > hi is excluded. Never `mid = (lo+hi)/2` in overflow-prone languages — use lo + (hi-lo)/2.

javascript · python · c++
javascript
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
python
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
c++
int binarySearch(vector<int>& arr, int target) {
    int lo = 0, hi = arr.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}
Try it with your own input in the workspace.Open visualizer

Only works on sorted input. Move the pointer whose side can't possibly form a better answer.

javascript · python · c++
javascript
function pairWithSum(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {
    const sum = arr[lo] + arr[hi];
    if (sum === target) return [lo, hi];
    if (sum < target) lo++;
    else hi--;
  }
  return null;
}
python
def pair_with_sum(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)
        if s < target:
            lo += 1
        else:
            hi -= 1
    return None
c++
pair<int,int> pairWithSum(vector<int>& arr, int target) {
    int lo = 0, hi = arr.size() - 1;
    while (lo < hi) {
        int s = arr[lo] + arr[hi];
        if (s == target) return {lo, hi};
        if (s < target) lo++;
        else hi--;
    }
    return {-1, -1};
}
Try it with your own input in the workspace.Open visualizer

Expand right every step; shrink left only while the window is invalid. Each index enters and leaves once → O(n).

javascript · python · c++
javascript
function longestDistinct(s) {
  const seen = new Map(); // char -> last index
  let best = 0, left = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    if (seen.has(c) && seen.get(c) >= left) left = seen.get(c) + 1;
    seen.set(c, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}
python
def longest_distinct(s):
    seen = {}          # char -> last index
    best = left = 0
    for right, c in enumerate(s):
        if c in seen and seen[c] >= left:
            left = seen[c] + 1
        seen[c] = right
        best = max(best, right - left + 1)
    return best
c++
int longestDistinct(string s) {
    unordered_map<char,int> last;
    int best = 0, left = 0;
    for (int right = 0; right < s.size(); right++) {
        char c = s[right];
        if (last.count(c) && last[c] >= left) left = last[c] + 1;
        last[c] = right;
        best = max(best, right - left + 1);
    }
    return best;
}
Try it with your own input in the workspace.Open visualizer

The shortest-path workhorse for unweighted graphs. Mark visited when you enqueue, not when you dequeue.

javascript · python · c++
javascript
function bfs(start, getNeighbors) {
  const visited = new Set([start]);
  const queue = [start];
  let level = 0;
  while (queue.length) {
    for (let size = queue.length; size > 0; size--) {
      const node = queue.shift();
      for (const nb of getNeighbors(node)) {
        if (!visited.has(nb)) {
          visited.add(nb);
          queue.push(nb);
        }
      }
    }
    level++;
  }
  return level; // or visited, or distances
}
python
from collections import deque

def bfs(start, get_neighbors):
    visited = {start}
    queue = deque([start])
    level = 0
    while queue:
        for _ in range(len(queue)):
            node = queue.popleft()
            for nb in get_neighbors(node):
                if nb not in visited:
                    visited.add(nb)
                    queue.append(nb)
        level += 1
    return level
c++
int bfs(int start, vector<vector<int>>& adj) {
    vector<bool> visited(adj.size(), false);
    queue<int> q;
    q.push(start); visited[start] = true;
    int level = 0;
    while (!q.empty()) {
        int size = q.size();
        while (size--) {
            int node = q.front(); q.pop();
            for (int nb : adj[node]) {
                if (!visited[nb]) { visited[nb] = true; q.push(nb); }
            }
        }
        level++;
    }
    return level;
}
Try it with your own input in the workspace.Open visualizer

The natural fit for cycle detection, component counting and exhaustive path exploration.

javascript · python · c++
javascript
function dfs(node, visited, getNeighbors) {
  if (visited.has(node)) return;
  visited.add(node);
  for (const nb of getNeighbors(node)) {
    dfs(nb, visited, getNeighbors);
  }
}
python
def dfs(node, visited, get_neighbors):
    if node in visited:
        return
    visited.add(node)
    for nb in get_neighbors(node):
        dfs(nb, visited, get_neighbors)
c++
void dfs(int node, vector<bool>& visited, vector<vector<int>>& adj) {
    if (visited[node]) return;
    visited[node] = true;
    for (int nb : adj[node]) dfs(nb, visited, adj);
}
Try it with your own input in the workspace.Open visualizer

Choose → explore → un-choose. The template for permutations, combinations and constraint problems.

javascript · python · c++
javascript
function subsets(nums) {
  const res = [], path = [];
  function backtrack(start) {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);      // choose
      backtrack(i + 1);        // explore
      path.pop();              // un-choose
    }
  }
  backtrack(0);
  return res;
}
python
def subsets(nums):
    res, path = [], []
    def backtrack(start):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])   # choose
            backtrack(i + 1)       # explore
            path.pop()             # un-choose
    backtrack(0)
    return res
c++
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> path;
    function<void(int)> backtrack = [&](int start) {
        res.push_back(path);
        for (int i = start; i < nums.size(); i++) {
            path.push_back(nums[i]);   // choose
            backtrack(i + 1);          // explore
            path.pop_back();           // un-choose
        }
    };
    backtrack(0);
    return res;
}
Try it with your own input in the workspace.Open visualizer

Sort by start, then extend the last interval while the current one overlaps.

javascript · python · c++
javascript
function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const out = [];
  for (const [start, end] of intervals) {
    const last = out[out.length - 1];
    if (last && start <= last[1]) last[1] = Math.max(last[1], end);
    else out.push([start, end]);
  }
  return out;
}
python
def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    out = []
    for start, end in intervals:
        if out and start <= out[-1][1]:
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return out
c++
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> out;
    for (auto& iv : intervals) {
        if (!out.empty() && iv[0] <= out.back()[1])
            out.back()[1] = max(out.back()[1], iv[1]);
        else
            out.push_back(iv);
    }
    return out;
}
Try it with your own input in the workspace.Open visualizer

Most tree problems are a one-liner recursion if you ask: what does the answer look like for my children?

javascript · python · c++
javascript
function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
python
def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))
c++
int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
Try it with your own input in the workspace.Open visualizer

The choice DP: for each item, either skip it or take it (if capacity allows). Roll the row to get O(W) space.

javascript · python · c++
javascript
function knapsack(values, weights, cap) {
  const n = values.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(cap + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= cap; w++) {
      dp[i][w] = dp[i - 1][w];                         // skip
      if (weights[i - 1] <= w)                          // take
        dp[i][w] = Math.max(dp[i][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
    }
  }
  return dp[n][cap];
}
python
def knapsack(values, weights, cap):
    n = len(values)
    dp = [[0] * (cap + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(cap + 1):
            dp[i][w] = dp[i - 1][w]                       # skip
            if weights[i - 1] <= w:                       # take
                dp[i][w] = max(dp[i][w], values[i-1] + dp[i-1][w - weights[i-1]])
    return dp[n][cap]
c++
int knapsack(vector<int>& values, vector<int>& weights, int cap) {
    int n = values.size();
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int w = 0; w <= cap; w++) {
            dp[i][w] = dp[i-1][w];                        // skip
            if (weights[i-1] <= w)                        // take
                dp[i][w] = max(dp[i][w], values[i-1] + dp[i-1][w - weights[i-1]]);
        }
    return dp[n][cap];
}
Try it with your own input in the workspace.Open visualizer

Keep a min-heap of size k; the heap floor is the k-th largest. Push-and-pop anything bigger.

javascript · python · c++
javascript
function topK(nums, k) {
  const heap = []; // min-heap via sorted insert (demo) — use a real heap in prod
  for (const n of nums) {
    heap.push(n);
    heap.sort((a, b) => a - b);
    if (heap.length > k) heap.shift();
  }
  return heap;
}
python
import heapq

def top_k(nums, k):
    heap = []
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap  # k largest, smallest first
c++
vector<int> topK(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> heap; // min-heap
    for (int n : nums) {
        heap.push(n);
        if (heap.size() > k) heap.pop();
    }
    vector<int> out;
    while (!heap.empty()) { out.push_back(heap.top()); heap.pop(); }
    return out;
}
Try it with your own input in the workspace.Open visualizer

Floyd's tortoise and hare. If they meet, there's a cycle; reset one to head and step both by 1 to find the cycle start.

javascript · python · c++
javascript
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast?.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}
python
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
c++
bool hasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}
Try it with your own input in the workspace.Open visualizer

Precompute cumulative sums once; any range sum becomes a subtraction. The base for 2D versions and beyond.

javascript · python · c++
javascript
const prefix = [0];
for (let i = 0; i < nums.length; i++) prefix.push(prefix[i] + nums[i]);
// sum of nums[l..r] inclusive:
const rangeSum = (l, r) => prefix[r + 1] - prefix[l];
python
prefix = [0]
for i, x in enumerate(nums):
    prefix.append(prefix[i] + x)

def range_sum(l, r):          # inclusive
    return prefix[r + 1] - prefix[l]
c++
vector<long long> prefix(nums.size() + 1, 0);
for (int i = 0; i < nums.size(); i++) prefix[i+1] = prefix[i] + nums[i];
// inclusive range sum:
long long rangeSum(int l, int r) { return prefix[r + 1] - prefix[l]; }
Try it with your own input in the workspace.Open visualizer