Algorithms, Patterns & Types

A compact C++11 reference covering the algorithms, data structures, and patterns you’ll reach for most often. Code is minimal and direct: #include <bits/stdc++.h>, using namespace std;, short names, no error handling. Every topic includes a when to use line, complexity, code, use cases, and gotchas.

Organized into six parts:

Part A — Core Data Structures (18 topics)
Part B — Graphs (12 topics)
Part C — Search, DP & Divide-and-Conquer (14 topics)
Part D — Strings, Math & Bits (12 topics)
Part E — Patterns & Idioms (8 topics)
Part F — Problem-Solving Skills (4 topics)

Total: 68 topics.

Part A — Core Data Structures

1. Arrays & `vector`

When to use: Fixed or dynamic-size indexed storage with O(1) random access.

Complexity: O(1) access, O(1) amortized push_back, O(n) erase.

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> v = {1, 2, 3};
  v.push_back(4);           // O(1) amortized
  v.emplace_back(5);        // O(1) amortized
  cout << v.size() << endl; // 5

  // Random access
  cout << v[2] << endl;     // 3

  // Iteration
  for (int x : v) cout << x << " ";

  // Sort
  sort(v.begin(), v.end());

  // Binary search bounds
  auto it = lower_bound(v.begin(), v.end(), 3);

  // Erase
  v.erase(v.begin() + 1);   // O(n)

  return 0;
}

Use cases:

Dynamic arrays with random access
Building up results before returning
Sorting and binary search on ordered data

Gotchas: push_back is amortized O(1), not guaranteed constant; erase is O(n) because it shifts; capacity != size.

2. Strings & `string`

When to use: Text manipulation, parsing, pattern matching on character sequences.

Complexity: O(n) most string ops, O(1) access, O(n) substr.

#include <bits/stdc++.h>
using namespace std;

int main() {
  string s = "hello";

  // Concatenation
  s += "world";

  // Substring (O(n) copy)
  string sub = s.substr(0, 5); // "hello"

  // Find
  size_t pos = s.find("wo");   // 5, or string::npos

  // Access
  cout << s[0] << endl;        // 'h'

  // Convert
  string num_str = to_string(42);
  int num = stoi("123");

  // Reverse
  reverse(s.begin(), s.end());

  // Length
  cout << s.length() << endl;

  return 0;
}

Use cases:

String parsing and transformation
Palindrome/substring checks
Number-to-string conversions

Gotchas: substr() creates a new string (O(n) copy); find() returns size_t with npos sentinel; string mutations via operator+ create new strings.

3. Hash Table — `unordered_map` / `unordered_set`

When to use: Fast average O(1) lookup and insertion; order not required.

Complexity: O(1) average insert/lookup/erase, O(n) worst case (collision attacks).

#include <bits/stdc++.h>
using namespace std;

int main() {
  unordered_map<string, int> freq;

  // Insert / update
  freq["apple"]++;
  freq.insert({"banana", 2});

  // Lookup
  if (freq.count("apple")) {
    cout << freq["apple"] << endl; // 1
  }

  // Find (safer than [])
  auto it = freq.find("apple");
  if (it != freq.end()) {
    cout << it->second << endl;
  }

  // Erase
  freq.erase("banana");

  unordered_set<int> seen;
  seen.insert(5);
  if (seen.count(5)) cout << "found" << endl;

  return 0;
}

Use cases:

Frequency counting
Presence checking (membership)
Caching and memoization

Gotchas: Worst-case O(n) via collision attacks; operator[] inserts if missing; use find() to avoid accidental insertions; custom hash can mitigate attacks (e.g. hash<long long> h; h(x ^ 0x9e3779b9) as seed).

4. Ordered Map / Set — `map` / `set`

When to use: Key-value or set storage with guaranteed sorted order; need range queries.

Complexity: O(log n) insert/lookup/erase; O(n) iteration in order.

#include <bits/stdc++.h>
using namespace std;

int main() {
  map<int, string> m;
  m[1] = "one";
  m[2] = "two";
  m[3] = "three";

  // Lookup
  cout << m[2] << endl; // "two"

  // lower_bound / upper_bound
  auto it = m.lower_bound(2); // points to {2, "two"}
  auto ut = m.upper_bound(2); // points to {3, "three"}

  // Iterate in sorted order
  for (auto& p : m) {
    cout << p.first << " " << p.second << "\n";
  }

  // Previous / next
  auto prev_it = prev(it);
  auto next_it = next(it);

  // Erase
  m.erase(2);

  set<int> s = {3, 1, 2};
  // same iterator operations work on set

  return 0;
}

Use cases:

Ordered dictionary lookups
Range queries (all keys in [a, b])
Detecting sorted structure

Gotchas: O(log n) per operation; operator[] inserts if missing; lower_bound >= key, upper_bound > key; reverse iteration requires rbegin/rend.

5. Stack — `stack` & manual

When to use: LIFO (last-in-first-out) access pattern; undo, DFS, expression evaluation.

Complexity: O(1) push/pop/top.

#include <bits/stdc++.h>
using namespace std;

int main() {
  // Standard std::stack
  stack<int> st;
  st.push(1);
  st.push(2);
  st.push(3);

  while (!st.empty()) {
    cout << st.top() << endl; // 3, 2, 1
    st.pop();
  }

  // Manual vector-as-stack (more flexible)
  vector<int> manual_stack;
  manual_stack.push_back(10);
  manual_stack.push_back(20);

  int top_val = manual_stack.back();
  manual_stack.pop_back();

  cout << manual_stack.size() << endl;

  return 0;
}

Use cases:

Expression evaluation (infix to postfix)
Undo/redo operations
DFS traversal

Gotchas: empty() before accessing top(); std::stack doesn’t provide size() in some older compilers (use manual vector); no random access.

6. Queue — `queue` & circular buffer

When to use: FIFO (first-in-first-out) access; BFS, task scheduling.

Complexity: O(1) push/pop front/back.

#include <bits/stdc++.h>
using namespace std;

int main() {
  // Standard std::queue
  queue<int> q;
  q.push(1);
  q.push(2);
  q.push(3);

  while (!q.empty()) {
    cout << q.front() << endl; // 1, 2, 3
    q.pop();
  }

  // Manual circular buffer
  int buf[1000];
  int head = 0, tail = 0, sz = 0;

  // enqueue
  buf[tail] = 100;
  tail = (tail + 1) % 1000;
  sz++;

  // dequeue
  int val = buf[head];
  head = (head + 1) % 1000;
  sz--;

  return 0;
}

Use cases:

BFS level-order traversal
Producer-consumer pattern
Task scheduling

Gotchas: empty() before front(); std::queue doesn’t support random access; circular buffer needs careful modulo handling.

7. Deque — `deque`

When to use: Efficient push/pop at both ends; fast random access.

Complexity: O(1) push_front/back, pop_front/back, random access.

#include <bits/stdc++.h>
using namespace std;

int main() {
  deque<int> dq;

  dq.push_back(3);
  dq.push_front(1);
  dq.push_front(0);
  dq.push_back(4);

  // Random access
  cout << dq[2] << endl; // 3

  // Front/back
  cout << dq.front() << " " << dq.back() << endl; // 0, 4

  // Pop from both ends
  dq.pop_front();
  dq.pop_back();

  // Iteration
  for (int x : dq) cout << x << " ";

  return 0;
}

Use cases:

Sliding window with O(1) removals from both ends
Task queues with priority on both ends
Double-ended buffering

Gotchas: Internally a list of blocks; cache-unfriendly compared to vector; slower iteration than vector.

8. Linked List (singly, doubly)

When to use: Frequent insertions/deletions in middle; no random access needed.

Complexity: O(1) insert/delete at position (if pointer available), O(n) search.

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
  int val;
  ListNode* next;
  ListNode(int v) : val(v), next(nullptr) {}
};

ListNode* reverse(ListNode* head) {
  ListNode* prev = nullptr;
  while (head) {
    ListNode* nxt = head->next;
    head->next = prev;
    prev = head;
    head = nxt;
  }
  return prev;
}

ListNode* detectCycle(ListNode* head) {
  ListNode *slow = head, *fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return slow; // cycle detected
  }
  return nullptr;
}

int main() {
  ListNode* head = new ListNode(1);
  head->next = new ListNode(2);
  head->next->next = new ListNode(3);

  // Reverse
  head = reverse(head);

  // Iterate
  ListNode* curr = head;
  while (curr) {
    cout << curr->val << " ";
    curr = curr->next;
  }

  return 0;
}

Use cases:

Undo stacks with O(1) removals
LRU cache (doubly-linked)
Cycle detection

Gotchas: No random access; O(n) search; manual memory management (free nodes in real code); Floyd cycle detection uses two pointers.

9. Heap / Priority Queue — `priority_queue`

When to use: Repeated access to min or max element; partial sorting.

Complexity: O(log n) push/pop, O(1) peek.

#include <bits/stdc++.h>
using namespace std;

int main() {
  // Max-heap (default)
  priority_queue<int> maxh;
  maxh.push(3);
  maxh.push(1);
  maxh.push(4);

  while (!maxh.empty()) {
    cout << maxh.top() << " "; // 4, 3, 1
    maxh.pop();
  }
  cout << "\n";

  // Min-heap via greater<int>
  priority_queue<int, vector<int>, greater<int>> minh;
  minh.push(3);
  minh.push(1);
  minh.push(4);

  while (!minh.empty()) {
    cout << minh.top() << " "; // 1, 3, 4
    minh.pop();
  }

  return 0;
}

Use cases:

Dijkstra / Prim algorithms
Median in stream (two heaps)
Top-K elements

Gotchas: Cannot iterate; no decrease-key in std::priority_queue (rebuild or mark deleted); greater() not greater.

10. Binary Tree basics & traversals

When to use: Hierarchical data; searching, indexing, expression trees.

Complexity: O(n) traversal, O(log n) search (if balanced).

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

void inorderRec(TreeNode* root, vector<int>& res) {
  if (!root) return;
  inorderRec(root->left, res);
  res.push_back(root->val);
  inorderRec(root->right, res);
}

vector<int> inorderIter(TreeNode* root) {
  vector<int> res;
  stack<TreeNode*> st;
  TreeNode* curr = root;
  while (curr || !st.empty()) {
    while (curr) {
      st.push(curr);
      curr = curr->left;
    }
    curr = st.top();
    st.pop();
    res.push_back(curr->val);
    curr = curr->right;
  }
  return res;
}

vector<vector<int>> levelOrder(TreeNode* root) {
  vector<vector<int>> res;
  if (!root) return res;
  queue<TreeNode*> q;
  q.push(root);
  while (!q.empty()) {
    int sz = q.size();
    vector<int> level;
    for (int i = 0; i < sz; i++) {
      TreeNode* node = q.front();
      q.pop();
      level.push_back(node->val);
      if (node->left) q.push(node->left);
      if (node->right) q.push(node->right);
    }
    res.push_back(level);
  }
  return res;
}

int main() {
  TreeNode* root = new TreeNode(1);
  root->left = new TreeNode(2);
  root->right = new TreeNode(3);

  vector<int> inorder = inorderIter(root);
  vector<vector<int>> levels = levelOrder(root);

  return 0;
}

Use cases:

Expression evaluation
File system hierarchies
DOM trees

Gotchas: Unbalanced trees degrade to O(n) search; recursive traversal limited by stack depth; level-order needs explicit queue.

11. Binary Search Tree (conceptual)

When to use: Ordered insertion/search; in-order traversal gives sorted sequence.

Complexity: O(log n) average, O(n) worst (unbalanced).

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

TreeNode* insert(TreeNode* root, int val) {
  if (!root) return new TreeNode(val);
  if (val < root->val)
    root->left = insert(root->left, val);
  else
    root->right = insert(root->right, val);
  return root;
}

bool search(TreeNode* root, int val) {
  if (!root) return false;
  if (val == root->val) return true;
  if (val < root->val) return search(root->left, val);
  return search(root->right, val);
}

TreeNode* deleteNode(TreeNode* root, int val) {
  if (!root) return nullptr;
  if (val < root->val) {
    root->left = deleteNode(root->left, val);
  } else if (val > root->val) {
    root->right = deleteNode(root->right, val);
  } else {
    if (!root->left) return root->right;
    if (!root->right) return root->left;
    TreeNode* minRight = root->right;
    while (minRight->left) minRight = minRight->left;
    root->val = minRight->val;
    root->right = deleteNode(root->right, minRight->val);
  }
  return root;
}

int main() {
  TreeNode* root = nullptr;
  root = insert(root, 5);
  root = insert(root, 3);
  root = insert(root, 7);

  cout << search(root, 3) << endl; // 1
  root = deleteNode(root, 3);

  return 0;
}

Use cases:

Ordered dynamic dictionary
Range queries on sorted data
Autocomplete with prefix tree variant

Gotchas: Naive insertion can create unbalanced tree (O(n) worst case); use AVL or Red-Black for guaranteed O(log n); std::set is a self-balancing BST.

12. Trie (prefix tree)

When to use: Prefix-based search, autocomplete, word filtering, spell check.

Complexity: O(m) insert/search where m is key length.

#include <bits/stdc++.h>
using namespace std;

struct TrieNode {
  TrieNode* children[26];
  bool isWord;
  TrieNode() : isWord(false) {
    for (int i = 0; i < 26; i++) children[i] = nullptr;
  }
};

void insert(TrieNode* root, string word) {
  TrieNode* node = root;
  for (char c : word) {
    int idx = c - 'a';
    if (!node->children[idx])
      node->children[idx] = new TrieNode();
    node = node->children[idx];
  }
  node->isWord = true;
}

bool search(TrieNode* root, string word) {
  TrieNode* node = root;
  for (char c : word) {
    int idx = c - 'a';
    if (!node->children[idx]) return false;
    node = node->children[idx];
  }
  return node->isWord;
}

bool startsWith(TrieNode* root, string prefix) {
  TrieNode* node = root;
  for (char c : prefix) {
    int idx = c - 'a';
    if (!node->children[idx]) return false;
    node = node->children[idx];
  }
  return true;
}

int main() {
  TrieNode* root = new TrieNode();
  insert(root, "apple");
  insert(root, "app");

  cout << search(root, "app") << endl;       // 1
  cout << startsWith(root, "ap") << endl;   // 1
  cout << search(root, "appl") << endl;     // 0

  return 0;
}

Use cases:

Autocomplete / search suggestions
Spell checker
IP routing tables

Gotchas: Space O(alphabet_size * num_words * avg_length); search is O(key_length) not O(log n); no natural ordering.

13. Union-Find (DSU with path compression + union by rank)

When to use: Connected components, cycle detection, Kruskal’s MST algorithm.

Complexity: O(α(n)) per operation (nearly O(1)) with both optimizations.

#include <bits/stdc++.h>
using namespace std;

class DSU {
public:
  vector<int> parent, rank;

  DSU(int n) : parent(n), rank(n, 0) {
    for (int i = 0; i < n; i++) parent[i] = i;
  }

  int find(int x) {
    if (parent[x] != x)
      parent[x] = find(parent[x]); // path compression
    return parent[x];
  }

  bool unite(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return false;

    // union by rank
    if (rank[px] < rank[py]) swap(px, py);
    parent[py] = px;
    if (rank[px] == rank[py]) rank[px]++;

    return true;
  }
};

int main() {
  DSU dsu(5);
  dsu.unite(0, 1);
  dsu.unite(1, 2);

  cout << (dsu.find(0) == dsu.find(2)) << endl; // 1
  cout << (dsu.find(0) == dsu.find(3)) << endl; // 0

  return 0;
}

Use cases:

Connected components in undirected graph
Cycle detection
Kruskal’s MST algorithm

Gotchas: path compression must happen on find(); rank is not actual height (heuristic); O(α(n)) is nearly O(1) for practical n.

14. Segment Tree (point update, range query)

When to use: Fast range sum/min/max queries with point updates on dynamic data.

Complexity: O(log n) update and range query, O(n) build.

#include <bits/stdc++.h>
using namespace std;

class SegmentTree {
private:
  vector<long long> tree;
  int n;

  void build(vector<int>& arr, int node, int start, int end) {
    if (start == end) {
      tree[node] = arr[start];
    } else {
      int mid = (start + end) / 2;
      build(arr, 2*node, start, mid);
      build(arr, 2*node+1, mid+1, end);
      tree[node] = tree[2*node] + tree[2*node+1];
    }
  }

  void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
      tree[node] = val;
    } else {
      int mid = (start + end) / 2;
      if (idx <= mid)
        update(2*node, start, mid, idx, val);
      else
        update(2*node+1, mid+1, end, idx, val);
      tree[node] = tree[2*node] + tree[2*node+1];
    }
  }

  long long query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return tree[node];
    int mid = (start + end) / 2;
    return query(2*node, start, mid, l, r) +
           query(2*node+1, mid+1, end, l, r);
  }

public:
  SegmentTree(vector<int>& arr) : n(arr.size()) {
    tree.resize(4 * n);
    build(arr, 1, 0, n - 1);
  }

  void update(int idx, int val) {
    update(1, 0, n - 1, idx, val);
  }

  long long query(int l, int r) {
    return query(1, 0, n - 1, l, r);
  }
};

int main() {
  vector<int> arr = {1, 2, 3, 4, 5};
  SegmentTree st(arr);

  cout << st.query(0, 2) << endl; // 6
  st.update(1, 10);
  cout << st.query(0, 2) << endl; // 14

  return 0;
}

Use cases:

Range sum queries with point updates
RMQ (range minimum query)
Inversion count in dynamic arrays

Gotchas: 1-indexed in some templates; tree size must be >= 4*n; recursive easier to understand than iterative.

15. Segment Tree with Lazy Propagation (range update + range query)

When to use: Range add/set operations with range sum/min/max queries.

Complexity: O(log n) per operation.

#include <bits/stdc++.h>
using namespace std;

class LazySegmentTree {
private:
  vector<long long> tree, lazy;
  int n;

  void push(int node, int start, int end) {
    if (lazy[node] != 0) {
      tree[node] += (long long)(end - start + 1) * lazy[node];
      if (start != end) {
        lazy[2*node] += lazy[node];
        lazy[2*node+1] += lazy[node];
      }
      lazy[node] = 0;
    }
  }

  void update(int node, int start, int end, int l, int r, long long val) {
    push(node, start, end);
    if (start > end || start > r || end < l) return;

    if (l <= start && end <= r) {
      lazy[node] += val;
      push(node, start, end);
      return;
    }

    int mid = (start + end) / 2;
    update(2*node, start, mid, l, r, val);
    update(2*node+1, mid+1, end, l, r, val);
    push(2*node, start, mid);
    push(2*node+1, mid+1, end);
    tree[node] = tree[2*node] + tree[2*node+1];
  }

  long long query(int node, int start, int end, int l, int r) {
    if (start > end || start > r || end < l) return 0;
    push(node, start, end);
    if (l <= start && end <= r) return tree[node];

    int mid = (start + end) / 2;
    return query(2*node, start, mid, l, r) +
           query(2*node+1, mid+1, end, l, r);
  }

public:
  LazySegmentTree(int sz) : n(sz) {
    tree.resize(4 * n, 0);
    lazy.resize(4 * n, 0);
  }

  void update(int l, int r, long long val) {
    update(1, 0, n - 1, l, r, val);
  }

  long long query(int l, int r) {
    return query(1, 0, n - 1, l, r);
  }
};

int main() {
  LazySegmentTree st(5);
  st.update(0, 2, 5);
  cout << st.query(0, 4) << endl; // 15
  st.update(1, 3, 2);
  cout << st.query(0, 4) << endl; // 21

  return 0;
}

Use cases:

Range add, range sum queries
Range assignment operations
Competitive programming range updates

Gotchas: push_down must happen before every access; lazy tracking on internal nodes is critical; off-by-one errors are common.

16. Fenwick Tree (Binary Indexed Tree)

When to use: Prefix sum queries with point updates; simpler than segment tree, cache-friendly.

Complexity: O(log n) update and prefix query, O(n log n) build.

#include <bits/stdc++.h>
using namespace std;

class FenwickTree {
private:
  vector<long long> tree;
  int n;

public:
  FenwickTree(int sz) : n(sz), tree(sz + 1, 0) {}

  void update(int idx, long long val) {
    idx++; // 1-indexed
    while (idx <= n) {
      tree[idx] += val;
      idx += idx & (-idx);
    }
  }

  long long query(int idx) {
    idx++; // 1-indexed
    long long sum = 0;
    while (idx > 0) {
      sum += tree[idx];
      idx -= idx & (-idx);
    }
    return sum;
  }

  long long rangeQuery(int l, int r) {
    if (l > 0)
      return query(r) - query(l - 1);
    return query(r);
  }
};

int main() {
  FenwickTree ft(5);
  ft.update(0, 1);
  ft.update(1, 2);
  ft.update(2, 3);
  ft.update(3, 4);
  ft.update(4, 5);

  cout << ft.query(2) << endl;        // 1+2+3 = 6
  cout << ft.rangeQuery(1, 3) << endl; // 2+3+4 = 9

  return 0;
}

Use cases:

Dynamic prefix sum
Inversion count (with coordinate compression)
Simpler alternative to segment tree

Gotchas: 1-indexed internally; only supports prefix queries (or via difference trick for range); idx & (-idx) isolates lowest set bit.

17. Custom Comparators (struct with `operator()`)

When to use: whenever you need non-default ordering for sort, set, multiset, map, priority_queue, lower_bound, or upper_bound.

Complexity: same as default — the comparator is just a callback.

#include <bits/stdc++.h>
using namespace std;

// Canonical form: a struct with operator() returning "is x < y?".
// IMPORTANT: it must define a STRICT WEAK ordering (a<b and b<a never
// both true; equivalent elements yield !cmp(a,b) && !cmp(b,a)).
struct Cmp {
    bool operator()(const pair<int,int>& x, const pair<int,int>& y) const {
        if (x.first != y.first) return x.first < y.first;   // smaller first wins
        return x.second > y.second;                          // tie: larger second wins
    }
};

int main() {
    // 1) vector + sort
    vector<pair<int,int>> v = {{1,2},{1,5},{2,1}};
    sort(v.begin(), v.end(), Cmp());

    // 2) set / multiset / map  — pass type as 2nd/3rd template arg
    set<pair<int,int>, Cmp> s;
    multiset<pair<int,int>, Cmp> ms;
    map<pair<int,int>, int, Cmp> mp;
    s.insert({1,5});
    ms.insert({1,2});
    mp[{2,1}] = 42;

    // 3) priority_queue — note the ordering is INVERTED:
    //    priority_queue pops the "largest" per comparator, so
    //    returning "x < y" gives a MAX-heap on x.
    //    Return "x > y" if you want a MIN-heap.
    priority_queue<pair<int,int>, vector<pair<int,int>>, Cmp> pq;
    pq.push({1,5});
    pq.push({1,2});
    pq.push({2,1});

    // 4) lower_bound / upper_bound on a sorted vector with Cmp
    sort(v.begin(), v.end(), Cmp());
    pair<int,int> key = {1, 3};
    auto it1 = lower_bound(v.begin(), v.end(), key, Cmp()); // first not < key
    auto it2 = upper_bound(v.begin(), v.end(), key, Cmp()); // first > key
    (void)it1; (void)it2;
    return 0;
}

Use cases:

sort by custom field / multi-key tiebreak
min-heap of pairs / structs via priority_queue
ordered set of intervals, events, or indices by weight
lower_bound / upper_bound on a sorted vector of structs

Gotchas:

priority_queue inverts the sense: x < y in the comparator yields a max-heap, x > y yields a min-heap. This trips people up every time.
The comparator must be a strict weak ordering — never return true for equal elements, or set/sort breaks.
For a set/map you pass the type (Cmp), not an instance. For sort / lower_bound / priority_queue you pass an instance (Cmp()).
For small ad-hoc cases a non-capturing lambda also works with sort, but it cannot be used as the comparator type of a set in C++11 — prefer the struct form shown above.
Common shortcut for min-heap of ints: priority_queue<int, vector<int>, greater<int>> pq; (use greater<int>(), not greater<>{}, in C++11).

18. Custom Hash for `unordered_map` / `unordered_set`

When to use: whenever the key is a pair, tuple, or custom struct — the STL has no default hash for those.

Complexity: same as default unordered containers — O(1) average, O(n) worst case.

#include <bits/stdc++.h>
using namespace std;

// Simple custom hash for pair<int,int> — combines two int hashes.
struct PairHash {
    size_t operator()(const pair<int,int>& p) const {
        size_t h1 = hash<int>()(p.first);
        size_t h2 = hash<int>()(p.second);
        return h1 ^ (h2 << 1);   // shift avoids h1==h2 collapsing to 0
    }
};

// Custom hash for a struct key — same pattern.
struct Point { int x, y; };
struct PointEq {
    bool operator()(const Point& a, const Point& b) const {
        return a.x == b.x && a.y == b.y;
    }
};
struct PointHash {
    size_t operator()(const Point& p) const {
        size_t h1 = hash<int>()(p.x);
        size_t h2 = hash<int>()(p.y);
        return h1 ^ (h2 << 1);
    }
};

int main() {
    // Pass the hash as a template TYPE (not an instance).
    unordered_map<pair<int,int>, int, PairHash> mp;
    unordered_set<pair<int,int>, PairHash>      st;
    mp[{1, 2}] = 10;
    st.insert({3, 4});

    // For a struct key you also need an equality functor
    // (or define operator== on the struct itself).
    unordered_map<Point, int, PointHash, PointEq> pm;
    pm[{5, 6}] = 99;
    return 0;
}

Use cases:

unordered_map<pair<int,int>, int> for grid coordinates
unordered_set of visited states in BFS/DFS over composite states
memoization tables keyed by (i, j) or small structs

Gotchas:

unordered_map takes Key, Value, Hash, Equal (4 template args); unordered_set takes Key, Hash, Equal (3). Pass hash as a type, not an instance.
std::hash<std::pair<...>> doesn’t exist — you must provide one for any pair or custom struct key.
For a plain struct key you also need an equality functor (or define operator== on the struct).
h1 ^ h2 alone is bad because hash(a, a) collapses to 0 for many inputs; shift one side (h2 << 1) to avoid it.

Part B — Graphs

19. Graph Representations (adj list / adj matrix)

When to use: Choose adjacency list for sparse graphs, adjacency matrix for dense graphs.

Complexity: O(V + E) space for adjacency list, O(V²) for adjacency matrix.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 5, m = 4;

    // Adjacency list (unweighted)
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); // undirected
    }

    // Adjacency list (weighted)
    vector<vector<pair<int, int>>> wadj(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        wadj[u].push_back(make_pair(v, w));
        wadj[v].push_back(make_pair(u, w));
    }

    // Adjacency matrix (dense graphs)
    vector<vector<int>> matrix(n, vector<int>(n, 0));
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        matrix[u][v] = 1;
        matrix[v][u] = 1;
    }

    return 0;
}

Use cases:

Adjacency list for sparse graphs and most problems
Adjacency matrix for dense graphs or when checking edge existence quickly
Weighted adjacency list for Dijkstra, Bellman-Ford, Kruskal’s

Gotchas: Adjacency matrix uses O(V²) memory even if E << V². Adj list with pairs can be harder to iterate; use .first and .second explicitly.

20. BFS on graph

When to use: Find shortest path in unweighted graph, level-order traversal, or reachability.

Complexity: O(V + E) time, O(V) space.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 5;
    vector<vector<int>> adj(n);

    // Build graph...

    vector<int> dist(n, -1);
    queue<int> q;
    q.push(0);
    dist[0] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    // dist[i] = shortest distance from node 0 to node i (-1 if unreachable)
    return 0;
}

Use cases:

Shortest path in unweighted graphs
Finding all nodes at distance k
Checking if graph is bipartite
Topological sort via BFS (Kahn’s algorithm)

Gotchas: Only works for unweighted or unit-weight edges. Visited array critical; don’t revisit. Queue size can be O(V).

21. DFS on graph

When to use: Explore all reachable nodes, detect cycles, find components, or compute post-order traversal.

Complexity: O(V + E) time, O(V) space (recursion/stack).

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj;
vector<bool> visited;

void dfs_recursive(int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs_recursive(v);
        }
    }
}

int main() {
    int n = 5;
    adj.resize(n);
    visited.resize(n, false);

    // Build graph...

    // Recursive DFS
    dfs_recursive(0);

    // Iterative DFS with stack
    vector<bool> vis(n, false);
    stack<int> st;
    st.push(0);
    vis[0] = true;

    while (!st.empty()) {
        int u = st.top();
        st.pop();

        for (int v : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                st.push(v);
            }
        }
    }

    return 0;
}

Use cases:

Finding connected components
Topological sorting (post-order)
Cycle detection in directed graphs
Finding bridges and articulation points

Gotchas: Recursion depth O(V) can overflow stack on large graphs. Iterative version avoids this. Mark visited before/after processing affects logic.

22. Connected Components

When to use: Count number of connected components or identify which component each node belongs to.

Complexity: O(V + E) time, O(V) space.

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj;
vector<int> comp;

void dfs(int u, int c) {
    comp[u] = c;
    for (int v : adj[u]) {
        if (comp[v] == -1) {
            dfs(v, c);
        }
    }
}

int main() {
    int n = 6;
    adj.resize(n);
    comp.resize(n, -1);

    // Build graph...

    int num_components = 0;
    for (int i = 0; i < n; i++) {
        if (comp[i] == -1) {
            dfs(i, num_components);
            num_components++;
        }
    }

    // comp[i] = component ID of node i
    // num_components = total number of components
    return 0;
}

Use cases:

Count connected components in undirected graph
Assign each node a component label
Detect disconnected subgraphs
Union-Find alternative

Gotchas: Works only on undirected graphs (for directed, use strongly connected components). Union-Find is faster for dynamic connectivity queries.

23. Topological Sort — Kahn’s (BFS) and DFS-based

When to use: Linearize directed acyclic graph (DAG) for dependency resolution or task scheduling.

Complexity: O(V + E) time, O(V) space.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 5;
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0);

    // Build graph and compute indegrees...

    // Kahn's BFS approach
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indeg[i] == 0) {
            q.push(i);
        }
    }

    vector<int> topo;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo.push_back(u);

        for (int v : adj[u]) {
            indeg[v]--;
            if (indeg[v] == 0) {
                q.push(v);
            }
        }
    }

    // Cycle detection: if topo.size() < n, cycle exists
    if ((int)topo.size() < n) {
        // Cycle detected
    }

    // DFS-based approach (post-order reverse)
    vector<bool> visited(n, false);
    vector<int> topo_dfs;

    function<void(int)> dfs = [&](int u) {
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) {
                dfs(v);
            }
        }
        topo_dfs.push_back(u);
    };

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }
    reverse(topo_dfs.begin(), topo_dfs.end());

    return 0;
}

Use cases:

Task scheduling with dependencies
Instruction order in compilers
Course prerequisite ordering
DAG shortest/longest paths

Gotchas: Only works on DAGs. Kahn’s detects cycles (output < n nodes). DFS-based requires post-order reverse. Both assume acyclic input for meaningful output.

24. Cycle Detection (directed & undirected)

When to use: Detect if graph contains a cycle.

Complexity: O(V + E) time, O(V) space.

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj;

// For directed graph: white/gray/black DFS
// white = 0 (unvisited), gray = 1 (visiting), black = 2 (done)
bool has_cycle_directed(int u, vector<int>& color) {
    color[u] = 1; // gray

    for (int v : adj[u]) {
        if (color[v] == 1) {
            return true; // back edge: cycle found
        }
        if (color[v] == 0 && has_cycle_directed(v, color)) {
            return true;
        }
    }

    color[u] = 2; // black
    return false;
}

// For undirected graph: DFS with parent
bool has_cycle_undirected(int u, int p, vector<bool>& visited) {
    visited[u] = true;

    for (int v : adj[u]) {
        if (!visited[v]) {
            if (has_cycle_undirected(v, u, visited)) {
                return true;
            }
        } else if (v != p) {
            return true; // found back edge
        }
    }

    return false;
}

int main() {
    int n = 4;
    adj.resize(n);

    // Build directed graph...

    vector<int> color(n, 0);
    bool cycle = false;
    for (int i = 0; i < n; i++) {
        if (color[i] == 0 && has_cycle_directed(i, color)) {
            cycle = true;
            break;
        }
    }

    return 0;
}

Use cases:

Dependency graph validation
Deadlock detection in systems
Topological sort validation
Graph acyclicity check

Gotchas: Directed and undirected differ fundamentally. Directed needs color states; undirected needs parent tracking. Self-loops are always cycles.

25. Dijkstra’s Shortest Path

When to use: Find shortest path from source to all nodes with non-negative edge weights.

Complexity: O((V + E) log V) time, O(V) space.

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

int main() {
    int n = 5;
    vector<vector<pii>> adj(n);

    // Build graph with weighted edges...

    vector<long long> dist(n, LLONG_MAX);
    priority_queue<pii, vector<pii>, greater<pii>() > pq;

    dist[0] = 0;
    pq.push(make_pair(0, 0)); // (distance, node)

    while (!pq.empty()) {
        pii top = pq.top();
        pq.pop();
        long long d = top.first;
        int u = top.second;

        if (d > dist[u]) continue;

        for (int i = 0; i < (int)adj[u].size(); i++) {
            int v = adj[u][i].first;
            int w = adj[u][i].second;

            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    // dist[i] = shortest distance from node 0 to node i
    return 0;
}

Use cases:

GPS navigation shortest path
Network routing
Robot path planning
Game AI pathfinding

Gotchas: Fails on negative weights. Priority queue comparator must use greater<pii>() with explicit type. Always check if (d > dist[u]) continue; to handle stale queue entries.

26. Bellman-Ford

When to use: Find shortest path with negative edge weights; detect negative cycles.

Complexity: O(V * E) time, O(V) space.

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, w;
};

int main() {
    int n = 4, m = 5;
    vector<Edge> edges;

    // Read edges...

    vector<long long> dist(n, LLONG_MAX);
    dist[0] = 0;

    // Relax edges V-1 times
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m; j++) {
            Edge e = edges[j];
            if (dist[e.u] != LLONG_MAX && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
            }
        }
    }

    // Check for negative cycle
    bool has_neg_cycle = false;
    for (int j = 0; j < m; j++) {
        Edge e = edges[j];
        if (dist[e.u] != LLONG_MAX && dist[e.u] + e.w < dist[e.v]) {
            has_neg_cycle = true;
            break;
        }
    }

    return 0;
}

Use cases:

Currency arbitrage detection
Network routing with arbitrary weights
Constraint satisfaction (difference constraints)
Negative cycle detection

Gotchas: O(VE) is slow for large graphs. Requires edge list representation. Negative cycle detection happens in the V-th iteration. LLONG_MAX overflow risk when adding weights.

27. Floyd-Warshall

When to use: Compute shortest paths between all pairs of nodes on small graphs.

Complexity: O(V³) time, O(V²) space.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 4;
    const long long INF = 1e18;
    vector<vector<long long>> dist(n, vector<long long>(n, INF));

    // Initialize distances
    for (int i = 0; i < n; i++) {
        dist[i][i] = 0;
    }

    // Read edges and populate dist...

    // Floyd-Warshall
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // dist[i][j] = shortest distance from node i to node j
    return 0;
}

Use cases:

All-pairs shortest path on small dense graphs
Transitive closure computation
Network diameter calculation
Small constraint-based distance problems

Gotchas: O(V³) is slow for V > 500. Handles negative weights but not negative cycles directly. INF overflow risk; use large constant like 1e18.

28. Minimum Spanning Tree — Kruskal’s

When to use: Find minimum weight spanning tree using greedy edge sorting.

Complexity: O(E log E) time, O(V) space.

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

class DSU {
public:
    vector<int> parent, rnk;

    DSU(int n) : parent(n), rnk(n, 0) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;

        if (rnk[px] < rnk[py]) swap(px, py);
        parent[py] = px;
        if (rnk[px] == rnk[py]) rnk[px]++;
        return true;
    }
};

int main() {
    int n = 4, m = 5;
    vector<Edge> edges;

    // Read edges...

    sort(edges.begin(), edges.end());

    DSU dsu(n);
    long long mst_weight = 0;
    int mst_edges = 0;

    for (const Edge& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            mst_weight += e.w;
            mst_edges++;
            if (mst_edges == n - 1) break;
        }
    }

    // mst_weight = total weight of MST
    // mst_edges = number of edges in MST (should be n-1)
    return 0;
}

Use cases:

Network design with minimum cost
Clustering and image segmentation
Maximum bottleneck path (MST property)
Electric grid design

Gotchas: Must sort edges; DSU prevents cycles. Time bottleneck is sorting. Works on undirected graphs only. If mst_edges < n-1, graph is disconnected.

29. Minimum Spanning Tree — Prim’s

When to use: Build MST starting from a source node, good for dense graphs.

Complexity: O((V + E) log V) time, O(V) space.

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

int main() {
    int n = 4;
    vector<vector<pii>> adj(n);

    // Build graph with weighted edges...

    vector<bool> in_mst(n, false);
    priority_queue<pii, vector<pii>, greater<pii>() > pq;

    long long mst_weight = 0;

    // Start from node 0
    in_mst[0] = true;
    for (int i = 0; i < (int)adj[0].size(); i++) {
        int v = adj[0][i].first;
        int w = adj[0][i].second;
        pq.push(make_pair(w, v)); // (weight, node)
    }

    while (!pq.empty()) {
        pii top = pq.top();
        pq.pop();
        int w = top.first;
        int v = top.second;

        if (in_mst[v]) continue;

        in_mst[v] = true;
        mst_weight += w;

        for (int i = 0; i < (int)adj[v].size(); i++) {
            int u = adj[v][i].first;
            int wt = adj[v][i].second;

            if (!in_mst[u]) {
                pq.push(make_pair(wt, u));
            }
        }
    }

    // mst_weight = total weight of MST
    return 0;
}

Use cases:

MST on dense graphs
Incremental network expansion
Bottleneck-aware minimum spanning forest
Real-time MST updates

Gotchas: Can start from any node; result is same. Priority queue may have stale entries; check in_mst[v] to skip. Slower than Kruskal’s on sparse graphs.

30. LCA (binary lifting) & Tree DP

When to use: Preprocess tree for O(log n) LCA queries and compute tree DP values.

Complexity: O(n log n) preprocessing, O(log n) per LCA query; Tree DP O(n).

#include <bits/stdc++.h>
using namespace std;

const int LOG = 20;

vector<vector<int>> adj;
vector<vector<int>> up;
vector<int> depth;
vector<int> subtree_size;

void dfs(int u, int p) {
    up[u][0] = p;
    subtree_size[u] = 1;

    for (int i = 1; i < LOG; i++) {
        up[u][i] = up[up[u][i-1]][i-1];
    }

    for (int v : adj[u]) {
        if (v != p) {
            depth[v] = depth[u] + 1;
            dfs(v, u);
            subtree_size[u] += subtree_size[v];
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);

    int diff = depth[u] - depth[v];
    for (int i = 0; i < LOG; i++) {
        if ((diff >> i) & 1) {
            u = up[u][i];
        }
    }

    if (u == v) return u;

    for (int i = LOG - 1; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }

    return up[u][0];
}

int main() {
    int n = 7;
    adj.resize(n);
    up.assign(n, vector<int>(LOG, 0));
    depth.assign(n, 0);
    subtree_size.assign(n, 0);

    // Build tree...

    dfs(0, 0);

    // Query LCA
    int result = lca(2, 5);

    // subtree_size[u] = number of nodes in subtree rooted at u
    return 0;
}

Use cases:

LCA queries on trees
Distance computation on trees (dist(u,v) = depth[u] + depth[v] - 2*depth[lca(u,v)])
Subtree DP aggregation
Path properties (max edge weight on path, etc.)

Gotchas: Requires rooted tree with parent pointers. Binary lifting table is O(n log n) space. LCA assumes preprocessing done first. Subtree_size computes tree DP in single DFS pass.

Part C — Search, DP & Divide-and-Conquer

31. Binary Search on sorted array

When to use: Find exact element or boundary in sorted data.

Complexity: O(log n) time, O(1) space.

int binarySearch(vector<int>& arr, int target) {
    int lo = 0, hi = arr.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return (lo < arr.size() && arr[lo] == target) ? lo : -1;
}

// Using lower_bound
auto it = lower_bound(arr.begin(), arr.end(), target);
if (it != arr.end() && *it == target) cout << (it - arr.begin());

Use cases:

Find first/last occurrence of element
Find insertion position
Range queries in sorted data

Gotchas: Off-by-one errors in loop bounds; ensure array is actually sorted; lower_bound returns iterator to first >= target.

32. Binary Search on Answer

When to use: Minimize/maximize something by binary search on result space.

Complexity: O(log(max_ans) * T(predicate)) time, O(1) space.

bool canShip(vector<int>& weights, int days, int cap) {
    int curDays = 1, curLoad = 0;
    for (int w : weights) {
        if (curLoad + w > cap) {
            curDays++;
            curLoad = w;
        } else {
            curLoad += w;
        }
    }
    return curDays <= days;
}

int shipWithinDays(vector<int>& weights, int days) {
    int lo = *max_element(weights.begin(), weights.end());
    int hi = accumulate(weights.begin(), weights.end(), 0);
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canShip(weights, days, mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

Use cases:

Minimum capacity / maximum throughput
Minimum time to complete task
Maximize resource allocation

Gotchas: Search space must be monotonic (condition true for all >= ans); boundary check carefully; often need to iterate lo/hi to include all candidates.

33. Two Pointers

When to use: Process sorted/filtered data with two endpoints moving toward center or outward.

Complexity: O(n) time, O(1) space.

vector<int> twoSum(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return {left, right};
        if (sum < target) left++;
        else right--;
    }
    return {};
}

int removeDuplicates(vector<int>& nums) {
    int i = 0;
    for (int j = 1; j < nums.size(); j++) {
        if (nums[j] != nums[i]) {
            nums[++i] = nums[j];
        }
    }
    return i + 1;
}

Use cases:

Pair sum / 3-sum in sorted array
Remove duplicates in place
Reverse array
Partition array

Gotchas: Requires sorted or pre-processed data; be careful with duplicate handling; in-place modifications require careful index tracking.

34. Sliding Window (fixed & variable)

When to use: Find subarray/substring meeting condition; avoid nested loops.

Complexity: O(n) time, O(1) or O(26) space for fixed/variable.

// Fixed window: max sum of subarray size k
int maxSumSubarray(vector<int>& arr, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += arr[i];
    int maxSum = sum;
    for (int i = k; i < arr.size(); i++) {
        sum += arr[i] - arr[i - k];
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}

// Variable window: longest substring without repeating
int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> count;
    int left = 0, maxLen = 0;
    for (int right = 0; right < s.size(); right++) {
        count[s[right]]++;
        while (count[s[right]] > 1) {
            count[s[left]]--;
            if (count[s[left]] == 0) count.erase(s[left]);
            left++;
        }
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

Use cases:

Maximum/minimum subarray sum of fixed size
Longest substring without repeating chars
Anagram/permutation match
Fruit basket (max fruits in window)

Gotchas: Fixed window contracting; variable window needs two pointers; distinguish when to shrink vs expand; off-by-one in window size.

35. Prefix Sums & Difference Arrays

When to use: Range sum queries or range increment/decrement updates efficiently.

Complexity: O(n) preprocess, O(1) query for prefix; O(n) for difference array.

// 1D Prefix sum
vector<int> prefixSum(vector<int>& arr) {
    vector<int> prefix(arr.size() + 1, 0);
    for (int i = 0; i < arr.size(); i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}
int rangeSum(vector<int>& prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

// 2D Prefix sum
vector<vector<int>> prefix2D(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> p(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            p[i][j] = grid[i-1][j-1] + p[i-1][j] + p[i][j-1] - p[i-1][j-1];
    return p;
}

// Difference array for range updates
vector<int> rangeUpdate(int n, vector<vector<int>>& updates) {
    vector<int> diff(n + 1, 0);
    for (auto& u : updates) {
        diff[u[0]]++;
        diff[u[1] + 1]--;
    }
    vector<int> result(n);
    int curr = 0;
    for (int i = 0; i < n; i++) {
        curr += diff[i];
        result[i] = curr;
    }
    return result;
}

Use cases:

Range sum / range average queries
2D grid sum queries
Multiple range increments with final point query
Painting houses / painting intervals

Gotchas: 1-indexed prefix arrays easier to avoid boundary bugs; difference array requires pass to compute final values; order of updates doesn’t matter with difference arrays.

36. Recursion & Backtracking

When to use: Explore all combinations, permutations, or path solutions with pruning.

Complexity: O(2^n) time worst-case, O(n) space (recursion stack).

// Generate all subsets
void backtrack(vector<int>& nums, int idx, vector<int>& curr, vector<vector<int>>& result) {
    if (idx == nums.size()) {
        result.push_back(curr);
        return;
    }
    // Include nums[idx]
    curr.push_back(nums[idx]);
    backtrack(nums, idx + 1, curr, result);
    curr.pop_back();
    // Exclude nums[idx]
    backtrack(nums, idx + 1, curr, result);
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> curr;
    backtrack(nums, 0, curr, result);
    return result;
}

// N-Queens with pruning
void solve(int row, vector<string>& board, set<int>& cols, set<int>& diag1, set<int>& diag2, vector<vector<string>>& result) {
    if (row == board.size()) {
        result.push_back(board);
        return;
    }
    for (int col = 0; col < board.size(); col++) {
        if (cols.count(col) || diag1.count(row - col) || diag2.count(row + col)) continue;
        board[row][col] = 'Q';
        cols.insert(col);
        diag1.insert(row - col);
        diag2.insert(row + col);
        solve(row + 1, board, cols, diag1, diag2, result);
        board[row][col] = '.';
        cols.erase(col);
        diag1.erase(row - col);
        diag2.erase(row + col);
    }
}

Use cases:

Generate all subsets / combinations / permutations
N-Queens, Sudoku solver
Word search in grid
Partition string into palindromes

Gotchas: Forgetting to backtrack (restore state); missing pruning conditions; exponential time/space; duplicate results with sorted input.

37. Divide & Conquer (merge sort, quickselect)

When to use: Break problem into independent subproblems, solve, and combine results.

Complexity: Merge sort O(n log n) time, O(n) space; Quickselect avg O(n), worst O(n^2).

void merge(vector<int>& arr, int lo, int mid, int hi) {
    vector<int> left(arr.begin() + lo, arr.begin() + mid + 1);
    vector<int> right(arr.begin() + mid + 1, arr.begin() + hi + 1);
    int i = 0, j = 0, k = lo;
    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) arr[k++] = left[i++];
        else arr[k++] = right[j++];
    }
    while (i < left.size()) arr[k++] = left[i++];
    while (j < right.size()) arr[k++] = right[j++];
}

void mergeSort(vector<int>& arr, int lo, int hi) {
    if (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        mergeSort(arr, lo, mid);
        mergeSort(arr, mid + 1, hi);
        merge(arr, lo, mid, hi);
    }
}

// Quickselect: find k-th smallest
int quickSelect(vector<int>& arr, int lo, int hi, int k) {
    if (lo == hi) return arr[lo];
    int pi = partition(arr, lo, hi);
    if (k == pi) return arr[k];
    if (k < pi) return quickSelect(arr, lo, pi - 1, k);
    return quickSelect(arr, pi + 1, hi, k);
}

Use cases:

Sorting (merge sort)
Finding k-th smallest/largest element
Counting inversions
Closest pair of points

Gotchas: Merge step is critical; partition function must be correct; quickselect expected O(n) but worst-case O(n^2); careful with boundary indices.

38. DP — 1D Linear

When to use: Optimal substructure with linear dependency on prior states.

Complexity: O(n) time, O(n) space (can optimize to O(1)).

// House robber: max sum non-adjacent elements
int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    vector<int> dp(n);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp[n - 1];
}

// Space optimized
int robOptimized(vector<int>& nums) {
    int prev2 = 0, prev1 = 0;
    for (int num : nums) {
        int curr = max(prev1, prev2 + num);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Use cases:

Climbing stairs (coin change, min steps)
House robber variants
Decode ways
Longest increasing subsequence

Gotchas: Identify base cases clearly; transition formula must be correct; space optimization requires careful variable updates.

39. DP — 2D Grid

When to use: Optimal path through 2D grid with state dependencies.

Complexity: O(m*n) time, O(m*n) space (can optimize to O(n)).

// Unique paths with obstacles
int uniquePathsWithObstacles(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                dp[i][j] = 0;
            } else if (i == 0 && j == 0) {
                dp[i][j] = 1;
            } else {
                int fromUp = (i > 0) ? dp[i - 1][j] : 0;
                int fromLeft = (j > 0) ? dp[i][j - 1] : 0;
                dp[i][j] = fromUp + fromLeft;
            }
        }
    }
    return dp[m - 1][n - 1];
}

// Minimum path sum
int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n));
    dp[0][0] = grid[0][0];
    for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
    for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
    return dp[m-1][n-1];
}

Use cases:

Unique/minimum paths in grid
Maximal square
Distinct subsequences
Delete columns for sorted order

Gotchas: Initialize first row/column carefully; handle obstacles; distinguish minimum vs maximum transitions; transition order matters.

40. DP — Knapsack (0/1, unbounded)

When to use: Select items under capacity constraint to maximize value.

Complexity: O(n*W) time, O(W) space (optimized 1D).

// 0/1 Knapsack: take or leave each item
int knapsack01(vector<int>& weights, vector<int>& values, int W) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][W];
}

// Space-optimized 1D (iterate backward)
int knapsack01Optimized(vector<int>& weights, vector<int>& values, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < weights.size(); i++) {
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

// Unbounded Knapsack: can take multiple copies (forward iteration)
int knapsackUnbounded(vector<int>& weights, vector<int>& values, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < weights.size(); i++) {
        for (int w = weights[i]; w <= W; w++) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

Use cases:

0/1 knapsack, unbounded knapsack
Coin change (minimum coins)
Partition equal subset sum
Target sum

Gotchas: Backward iteration for 0/1 to avoid reusing item; forward iteration for unbounded; distinguish between coin change and knapsack transitions.

41. DP — Longest Common Subsequence / Edit Distance

When to use: Compare two sequences for similarity or transformation cost.

Complexity: O(m*n) time, O(m*n) space.

// Longest Common Subsequence
int lcs(string a, string b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

// Edit Distance (Levenshtein)
int editDistance(string a, string b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
            }
        }
    }
    return dp[m][n];
}

Use cases:

Longest common subsequence
Edit distance (insert/delete/replace)
Wildcard matching
Regular expression matching

Gotchas: LCS: match extends diagonal; edit distance: replace/insert/delete costs; both require 1-indexed dp to handle base case; careful with string indexing.

42. DP — Interval DP

When to use: Optimize over all subranges; dependencies span entire interval.

Complexity: O(n^3) time, O(n^2) space.

// Burst Balloons: pop balloons in specific order
int burstBalloons(vector<int>& nums) {
    vector<int> balloons = {1};
    balloons.insert(balloons.end(), nums.begin(), nums.end());
    balloons.push_back(1);
    int n = balloons.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int len = 3; len <= n; len++) {
        for (int left = 0; left + len - 1 < n; left++) {
            int right = left + len - 1;
            for (int k = left + 1; k < right; k++) {
                int coins = balloons[left] * balloons[k] * balloons[right] + dp[left][k] + dp[k][right];
                dp[left][right] = max(dp[left][right], coins);
            }
        }
    }
    return dp[0][n - 1];
}

// Matrix Chain Multiplication
int matrixChainOrder(vector<int>& dims) {
    int n = dims.size() - 1;
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n - 1];
}

Use cases:

Burst balloons
Matrix chain multiplication
Stone game variants
Palindrome partitioning cost

Gotchas: Triple nested loop: len then i then k; boundaries (left, right, k) must be distinct and avoid off-by-one; transitions combine non-overlapping subproblems.

43. DP — Bitmask DP

When to use: Encode state as bitmask; optimize over all subset choices.

Complexity: O(2^n * n) time, O(2^n * n) space.

// Traveling Salesman Problem
int tsp(vector<vector<int>>& dist) {
    int n = dist.size();
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
    dp[1][0] = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;
            if (dp[mask][u] == INT_MAX) continue;
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;
                int newMask = mask | (1 << v);
                dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }
    int ans = INT_MAX;
    for (int i = 1; i < n; i++) {
        ans = min(ans, dp[(1 << n) - 1][i] + dist[i][0]);
    }
    return ans;
}

// Partition to K Equal Sum Subsets
bool canPartition(vector<int>& nums, int k, int target, vector<int>& buckets, int idx) {
    if (idx == nums.size()) return true;
    for (int i = 0; i < k; i++) {
        if (buckets[i] + nums[idx] <= target) {
            buckets[i] += nums[idx];
            if (canPartition(nums, k, target, buckets, idx + 1)) return true;
            buckets[i] -= nums[idx];
        }
        if (buckets[i] == 0) break;
    }
    return false;
}

Use cases:

Traveling Salesman Problem (TSP)
Steiner tree
Subset enumeration with constraints
Partition into equal sum subsets

Gotchas: Exponential memory for large n; bit operations: check (mask & (1 << i)), set (mask | (1 << i)); careful with INT_MAX overflow; state transitions must verify bit presence.

44. DP — Digit DP

When to use: Count/maximize numbers in range [L, R] with digit constraints.

Complexity: O(log N * S) time (S = state space), O(log N * S) space.

// Count numbers in [1, N] without consecutive same digits
string num;
map<tuple<int, int, bool>, long long> memo;

long long solve(int pos, int lastDigit, bool tight) {
    if (pos == num.size()) return 1;
    auto key = make_tuple(pos, lastDigit, tight);
    if (memo.find(key) != memo.end()) return memo[key];

    int maxDigit = tight ? (num[pos] - '0') : 9;
    long long ans = 0;
    for (int digit = 0; digit <= maxDigit; digit++) {
        if (pos > 0 && digit == lastDigit) continue;
        ans += solve(pos + 1, digit, tight && (digit == maxDigit));
    }
    return memo[key] = ans;
}

long long countNumbers(int n) {
    num = to_string(n);
    memo.clear();
    return solve(0, -1, true);
}

// Count numbers in range [L, R]
long long countInRange(int L, int R) {
    return countNumbers(R) - (L > 1 ? countNumbers(L - 1) : 0);
}

Use cases:

Count numbers without repeating/consecutive digits
Count numbers divisible by k in range
Sum of digits in range
Digit DP with modular constraints

Gotchas: Tight constraint: only relax after choosing digit < limit; lastDigit state initial value (use -1); memoization key must include all states; convert to string and process left-to-right; handle [L,R] by subtracting count(L-1) from count(R). # Part D — Strings, Math & Bits

45. KMP (prefix function)

When to use: Find all occurrences of a pattern in a text efficiently.

Complexity: O(n+m) time, O(m) space.

#include <bits/stdc++.h>
using namespace std;

vector<int> computePI(string s) {
    int n = s.length();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

vector<int> findOccurrences(string text, string pattern) {
    vector<int> pi = computePI(pattern);
    vector<int> result;
    int j = 0;
    for (int i = 0; i < (int)text.length(); i++) {
        while (j > 0 && text[i] != pattern[j]) j = pi[j - 1];
        if (text[i] == pattern[j]) j++;
        if (j == (int)pattern.length()) {
            result.push_back(i - j + 1);
            j = pi[j - 1];
        }
    }
    return result;
}

Use cases:

String matching without preprocessing the text
Finding all pattern occurrences in a single pass
Pattern matching in streaming data

Gotchas: The pi[] array is 0-indexed and stores the length of the longest proper prefix that is also a suffix. When a match fails, reset j = pi[j-1] instead of backtracking in the text.

46. Z-function

When to use: Compute all lengths of prefixes matching at each position; find pattern occurrences.

Complexity: O(n) time, O(n) space.

#include <bits/stdc++.h>
using namespace std;

vector<int> computeZ(string s) {
    int n = s.length();
    vector<int> z(n, 0);
    z[0] = n;
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i > r) {
            l = r = i;
            while (r < n && s[r - l] == s[r]) r++;
            z[i] = r - l;
            r--;
        } else {
            int k = i - l;
            if (z[k] < r - i + 1) {
                z[i] = z[k];
            } else {
                l = i;
                while (r < n && s[r - l] == s[r]) r++;
                z[i] = r - l;
                r--;
            }
        }
    }
    return z;
}

vector<int> findPattern(string text, string pattern) {
    string s = pattern + "$" + text;
    vector<int> z = computeZ(s);
    vector<int> result;
    int m = pattern.length();
    for (int i = m + 1; i < (int)s.length(); i++) {
        if (z[i] == m) result.push_back(i - m - 1);
    }
    return result;
}

Use cases:

Pattern matching in a single concatenated string
Computing prefix array for periodic string analysis
Finding all repeating patterns efficiently

Gotchas: The separator character must not appear in either pattern or text. The Z-array is 0-indexed; z[i] is the length of the prefix starting at position i. The window [l, r] tracks the rightmost segment that matches the prefix.

47. Rabin-Karp (rolling hash)

When to use: Find pattern occurrences using polynomial rolling hash for quick substring comparison.

Complexity: O(n+m) average, O((n-m+1)*m) worst case; O(1) space.

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;
const long long BASE = 31;

long long computeHash(string s) {
    long long h = 0;
    long long pow_base = 1;
    for (int i = 0; i < (int)s.length(); i++) {
        h = (h + (s[i] - 'a' + 1) * pow_base) % MOD;
        if (i < (int)s.length() - 1) pow_base = (pow_base * BASE) % MOD;
    }
    return h;
}

vector<int> rabinKarp(string text, string pattern) {
    vector<int> result;
    int n = text.length(), m = pattern.length();
    if (m > n) return result;

    long long patHash = computeHash(pattern);
    long long pow_base = 1;
    for (int i = 0; i < m - 1; i++) pow_base = (pow_base * BASE) % MOD;

    long long textHash = computeHash(text.substr(0, m));
    if (textHash == patHash && text.substr(0, m) == pattern) result.push_back(0);

    for (int i = m; i < n; i++) {
        textHash = (textHash - (text[i - m] - 'a' + 1) + MOD) % MOD;
        textHash = (textHash * BASE) % MOD;
        textHash = (textHash + (text[i] - 'a' + 1) * pow_base) % MOD;
        if (textHash == patHash && text.substr(i - m + 1, m) == pattern) {
            result.push_back(i - m + 1);
        }
    }
    return result;
}

Use cases:

Quick heuristic filtering before confirming matches
Approximate string matching with modifications
Substring search with multiple patterns simultaneously

Gotchas: Hash collisions are possible; always verify matches with direct string comparison. For robustness, use double hashing with two independent hash functions and moduli to reduce collision probability.

48. Manacher’s Algorithm

When to use: Find the longest palindromic substring in linear time.

Complexity: O(n) time, O(n) space.

#include <bits/stdc++.h>
using namespace std;

string manacher(string s) {
    string t = "#";
    for (char c : s) {
        t += c;
        t += '#';
    }

    int n = t.length();
    vector<int> p(n, 0);
    int center = 0, right = 0;
    int maxLen = 0, maxCenter = 0;

    for (int i = 0; i < n; i++) {
        int mirror = 2 * center - i;
        if (i < right) {
            p[i] = min(right - i, p[mirror]);
        }

        while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 &&
               t[i + p[i] + 1] == t[i - p[i] - 1]) {
            p[i]++;
        }

        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }

        if (p[i] > maxLen) {
            maxLen = p[i];
            maxCenter = i;
        }
    }

    string result = "";
    for (int i = maxCenter - maxLen; i <= maxCenter + maxLen; i++) {
        if (t[i] != '#') result += t[i];
    }
    return result;
}

Use cases:

Finding the longest palindromic substring
Counting all palindromic substrings
Palindrome radius queries

Gotchas: The transformation with # separators creates odd-length palindromes only, so all radii correspond to characters. The array p[i] stores the radius of the palindrome centered at i. The center and right boundary track the rightmost palindrome found so far.

49. Suffix Array (basic)

When to use: Build a sorted array of all suffix starting positions for substring queries.

Complexity: O(n log^2 n) construction, O((n - m + 1) log n) query; O(n) space.

#include <bits/stdc++.h>
using namespace std;

struct Suffix {
    int idx;
    pair<int, int> rank;
};

bool cmp(Suffix a, Suffix b) {
    return a.rank < b.rank;
}

vector<int> buildSuffixArray(string s) {
    int n = s.length();
    vector<Suffix> suffixes(n);

    for (int i = 0; i < n; i++) {
        suffixes[i].idx = i;
        suffixes[i].rank.first = s[i] - 'a';
        suffixes[i].rank.second = (i + 1 < n) ? s[i + 1] - 'a' : -1;
    }

    sort(suffixes.begin(), suffixes.end(), cmp);

    vector<int> ind(n);
    for (int k = 4; k < 2 * n; k *= 2) {
        int rank = 0;
        int prev_rank = suffixes[0].rank.first;
        suffixes[0].rank.first = rank;
        ind[suffixes[0].idx] = 0;

        for (int i = 1; i < n; i++) {
            if (suffixes[i].rank.first == prev_rank &&
                suffixes[i].rank.second == suffixes[i - 1].rank.second) {
                prev_rank = suffixes[i].rank.first;
                suffixes[i].rank.first = rank;
            } else {
                prev_rank = suffixes[i].rank.first;
                suffixes[i].rank.first = ++rank;
            }
            ind[suffixes[i].idx] = i;
        }

        for (int i = 0; i < n; i++) {
            int nextindex = suffixes[i].idx + k / 2;
            suffixes[i].rank.second = (nextindex < n) ?
                suffixes[ind[nextindex]].rank.first : -1;
        }

        sort(suffixes.begin(), suffixes.end(), cmp);
    }

    vector<int> sa(n);
    for (int i = 0; i < n; i++) sa[i] = suffixes[i].idx;
    return sa;
}

Use cases:

Counting distinct substrings
Finding longest repeated substring
Pattern matching in multiple texts

Gotchas: The suffix array is 0-indexed; sa[i] is the starting position of the i-th smallest suffix. Building requires careful rank management across iterations. Naïve binary search on suffix array finds pattern ranges; use LCP array for advanced queries.

50. Number Theory — GCD, Modular Exponentiation, Modular Inverse

When to use: Solve modular arithmetic problems, find GCD, compute powers under modulus.

Complexity: O(log min(a,b)) for GCD, O(log b) for modular exponentiation; O(1) space.

#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

long long power(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

long long modInverse(long long a, long long mod) {
    // mod must be prime; inverse = a^(mod-2) mod mod
    return power(a, mod - 2, mod);
}

// Extended GCD: finds x, y such that a*x + b*y = gcd(a,b)
pair<long long, long long> extgcd(long long a, long long b) {
    if (b == 0) return make_pair(1, 0);
    pair<long long, long long> p = extgcd(b, a % b);
    return make_pair(p.second, p.first - (a / b) * p.second);
}

int main() {
    long long a = 12, b = 18;
    cout << "GCD: " << gcd(a, b) << endl;
    cout << "5^7 mod 13: " << power(5, 7, 13) << endl;
    cout << "Inverse of 3 mod 11: " << modInverse(3, 11) << endl;
    return 0;
}

Use cases:

Computing modular inverses for division under modulus
Fast exponentiation in cryptography
Finding GCD for fraction reduction and Bezout coefficients

Gotchas: Modular inverse exists only when gcd(a, mod) == 1. For prime moduli, use Fermat’s little theorem: a^(-1) ≡ a^(p-2) (mod p). The extended GCD uses structured bindings; if using older C++ standard, unpack manually.

51. Sieve of Eratosthenes & prime factorization

When to use: Precompute all primes up to N or find prime factors of numbers efficiently.

Complexity: O(n log log n) sieve, O(log n) factorization per number; O(n) space.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;
int spf[MAXN]; // smallest prime factor

void sieve(int n) {
    for (int i = 1; i <= n; i++) spf[i] = i;
    for (int i = 2; i * i <= n; i++) {
        if (spf[i] == i) { // i is prime
            for (int j = i * i; j <= n; j += i) {
                if (spf[j] == j) spf[j] = i;
            }
        }
    }
}

vector<pair<long long, int>> factorize(long long n) {
    vector<pair<long long, int>> factors;
    while (n > 1) {
        long long p = spf[n];
        int cnt = 0;
        while (n % p == 0) {
            n /= p;
            cnt++;
        }
        factors.push_back({p, cnt});
    }
    return factors;
}

int main() {
    sieve(1000000);
    vector<pair<long long, int>> factors = factorize(120);
    for (int i = 0; i < (int)factors.size(); i++) {
        cout << factors[i].first << "^" << factors[i].second << " ";
    }
    return 0;
}

Use cases:

Generating all primes up to a limit
Factorizing numbers quickly for divisor problems
Checking primality for numbers up to MAXN

Gotchas: The SPF array initialization must be spf[i] = i for all i; only primes have spf[i] == i after sieving. Sieve only needs to iterate up to sqrt(n) because all composites have a factor <= sqrt(n). For numbers outside the sieve range, use trial division or Pollard’s rho.

52. Combinatorics — nCr mod p

When to use: Compute binomial coefficients modulo a prime efficiently for many queries.

Complexity: O(n) precomputation, O(1) per query; O(n) space.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
const long long MOD = 1e9 + 7;
long long fact[MAXN], inv_fact[MAXN];

long long power(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

void precompute(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    inv_fact[n] = power(fact[n], MOD - 2, MOD);
    for (int i = n - 1; i >= 0; i--) {
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
    }
}

long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return (fact[n] * inv_fact[r] % MOD) * inv_fact[n - r] % MOD;
}

int main() {
    precompute(200000);
    cout << "C(10,3) mod 10^9+7: " << nCr(10, 3) << endl;
    cout << "C(100,50) mod 10^9+7: " << nCr(100, 50) << endl;
    return 0;
}

Use cases:

Counting paths in grids
Distributing identical items into distinct bins
Computing probabilities and expected values modulo p

Gotchas: Precomputation must happen before any queries. Compute inverse factorials by first finding the inverse of n! via Fermat, then working backward. nCr is zero if r < 0 or r > n.

53. Matrix Exponentiation

When to use: Solve linear recurrences (Fibonacci, etc.) in O(log n) time.

Complexity: O(k^3 log n) for k×k matrices; O(k^2) space.

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

typedef vector<vector<long long>> Matrix;

Matrix multiply(const Matrix& A, const Matrix& B, int k) {
    Matrix C(k, vector<long long>(k, 0));
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            for (int l = 0; l < k; l++) {
                C[i][j] = (C[i][j] + A[i][l] * B[l][j]) % MOD;
            }
        }
    }
    return C;
}

Matrix matPower(Matrix A, long long n, int k) {
    Matrix res(k, vector<long long>(k, 0));
    for (int i = 0; i < k; i++) res[i][i] = 1; // identity

    while (n > 0) {
        if (n & 1) res = multiply(res, A, k);
        A = multiply(A, A, k);
        n >>= 1;
    }
    return res;
}

long long fibonacci(long long n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    Matrix base = {{1, 1}, {1, 0}};
    Matrix res = matPower(base, n, 2);
    return res[0][1];
}

int main() {
    cout << "Fib(10): " << fibonacci(10) << endl;
    cout << "Fib(50) mod 10^9+7: " << fibonacci(50) << endl;
    return 0;
}

Use cases:

Fibonacci and linear recurrence computation
Counting paths in graphs with transition matrices
Matrix power queries and transformations

Gotchas: Modular arithmetic is applied in the multiply function to avoid overflow. The identity matrix initialization is critical: res[i][i] = 1 for all i. For Fibonacci, F(n) = res[0][1] after computing base^n.

54. Bit Manipulation Tricks

When to use: Solve bit-level problems efficiently using bitwise operations.

Complexity: O(1) per operation; O(1) space.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int x = 12; // 1100 in binary

    // Get the lowest set bit
    int lowbit = x & (-x); // 0100 = 4

    // Clear the lowest set bit
    int cleared = x & (x - 1); // 1000 = 8

    // Count the number of set bits
    int popcount = __builtin_popcount(x); // 2

    // Count trailing zeros (position of lowest set bit)
    int ctz = __builtin_ctz(x); // 2

    // Count leading zeros in a 32-bit number
    int clz = __builtin_clz(x); // 28

    // Check if bit at position i is set
    int i = 2;
    bool is_set = (x >> i) & 1; // true

    // Set bit at position i
    int set_bit = x | (1 << i); // unchanged, already set

    // Clear bit at position i
    int clear_bit = x & ~(1 << i); // 1000 = 8

    // Toggle bit at position i
    int toggle_bit = x ^ (1 << i); // 1000 = 8

    // Check if x is a power of 2
    bool is_pow2 = x > 0 && (x & (x - 1)) == 0; // false

    cout << "lowbit: " << lowbit << ", popcount: " << popcount << endl;
    cout << "ctz: " << ctz << ", clz: " << clz << endl;
    return 0;
}

Use cases:

Finding the only set bit in a number
Iterating through all set bits
Checking if a number is a power of 2
Counting bit differences between two numbers

Gotchas: __builtin_ctz is undefined when x=0. __builtin_clz assumes 32-bit integers; use __builtin_clzll for 64-bit. x & -x works because -x in two’s complement is ~x + 1, making the lowest set bit isolated.

55. XOR Tricks & Subset Sums

When to use: Solve problems involving XOR properties and subset enumeration.

Complexity: O(n) for finding single element/missing number, O(3^k) to enumerate all subsets of a k-bit mask; O(1) space.

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Find single element in array where all others appear twice
    vector<int> arr = {1, 2, 3, 2, 3};
    int single = 0;
    for (int x : arr) single ^= x; // single = 1
    cout << "Single element: " << single << endl;

    // Find missing number in range [1, n]
    vector<int> nums = {1, 2, 4, 5}; // 3 is missing
    int xor_all = 0;
    for (int x : nums) xor_all ^= x;
    int expected_xor = 0;
    for (int i = 1; i <= 5; i++) expected_xor ^= i;
    int missing = xor_all ^ expected_xor; // missing = 3
    cout << "Missing number: " << missing << endl;

    // Iterate all subsets of a mask
    int mask = 5; // 101 in binary
    cout << "All subsets of " << mask << ": ";
    for (int s = mask; ; s = (s - 1) & mask) {
        cout << s << " ";
        if (s == 0) break;
    }
    cout << endl;

    // Parity (XOR all elements to check if count of odd-bits is odd)
    int parity = 0;
    for (int x : arr) parity ^= x;
    cout << "Parity: " << parity << endl;

    return 0;
}

Use cases:

Finding single elements in arrays where others appear even times
Detecting missing or duplicate numbers
Enumerating all subsets of a given bitmask
Solving XOR-based linear system problems

Gotchas: The subset enumeration loop for (int s = mask; s; s = (s-1)&mask) does not iterate the zero subset explicitly; add a special case if needed. XOR is associative and commutative: a XOR b XOR b = a. Subsets are enumerated in decreasing order.

56. Geometry Basics (cross product, orientation, convex hull)

When to use: Solve computational geometry problems: point orientation, segment intersection, convex hull.

Complexity: O(1) for cross product and orientation, O(n log n) for convex hull; O(n) space.

#include <bits/stdc++.h>
using namespace std;

struct Point {
    long long x, y;
    Point() {}
    Point(long long x, long long y) : x(x), y(y) {}
    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    bool operator<(const Point& p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
};

long long cross(const Point& O, const Point& A, const Point& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

// Returns: 1 (CCW), -1 (CW), 0 (collinear)
int orientation(const Point& O, const Point& A, const Point& B) {
    long long cp = cross(O, A, B);
    if (cp > 0) return 1;
    if (cp < 0) return -1;
    return 0;
}

vector<Point> convexHull(vector<Point> points) {
    int n = points.size();
    if (n <= 2) return points;
    sort(points.begin(), points.end());

    vector<Point> hull;
    // Build lower hull
    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2 && cross(hull[hull.size()-2], hull[hull.size()-1], points[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }

    // Build upper hull
    int lower_size = hull.size();
    for (int i = n - 2; i >= 0; i--) {
        while (hull.size() > lower_size && cross(hull[hull.size()-2], hull[hull.size()-1], points[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }

    hull.pop_back(); // Remove duplicate endpoint
    return hull;
}

int main() {
    Point O(0, 0), A(1, 1), B(2, 0);
    cout << "Orientation O-A-B: " << orientation(O, A, B) << endl;

    vector<Point> pts = {{0, 0}, {1, 1}, {2, 2}, {2, 0}, {1, 0}};
    auto hull = convexHull(pts);
    cout << "Convex hull size: " << hull.size() << endl;
    return 0;
}

Use cases:

Determining point position relative to a line
Computing area of triangles and polygons
Finding convex hull of a point set
Checking line segment intersections

Gotchas: Cross product can overflow for large coordinates; use long long for intermediate calculations. Andrew’s monotone chain builds lower hull first, then upper hull in reverse. The final result includes the endpoint twice; remove it with pop_back(). Collinear points are excluded from strict convex hull; adjust <= 0 to < 0 to include them. # Part E — Patterns & Idioms

57. Monotonic Stack

When to use: Find next/previous greater or smaller element in O(n).

Complexity: O(n) time, O(n) space.

#include <bits/stdc++.h>
using namespace std;

vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    vector<int> stack;

    for (int i = n - 1; i >= 0; --i) {
        while (!stack.empty() && stack.back() <= nums[i]) {
            stack.pop_back();
        }
        if (!stack.empty()) {
            result[i] = stack.back();
        }
        stack.push_back(nums[i]);
    }

    return result;
}

Use cases:

Next greater element problem
Temperature increase problem (stock span)
Trapping rain water (variant with monotonic decreasing stack)

Gotchas: Traverse right-to-left for next-greater; left-to-right for previous-greater. Pop while condition matches your target (e.g., <= for strictly greater).

58. Monotonic Deque

When to use: Sliding window maximum/minimum in O(n) without repeated comparisons.

Complexity: O(n) time, O(k) space (k = window size).

#include <bits/stdc++.h>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    deque<int> dq; // stores indices

    for (int i = 0; i < nums.size(); ++i) {
        // Remove out-of-window indices
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }

        // Remove smaller elements from back
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();
        }

        dq.push_back(i);

        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

Use cases:

Sliding window maximum problem
Sliding window minimum problem
Constraint satisfaction with streaming data

Gotchas: Store indices, not values, to handle duplicates and out-of-window removal. Pop from front for expired window, from back for smaller elements.

59. Merge Intervals

When to use: Combine overlapping intervals into a single list in O(n log n).

Complexity: O(n log n) time, O(n) space.

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};

    sort(intervals.begin(), intervals.end());
    vector<vector<int>> result;
    result.push_back(intervals[0]);

    for (int i = 1; i < intervals.size(); ++i) {
        if (intervals[i][0] <= result.back()[1]) {
            // Overlapping: merge
            result.back()[1] = max(result.back()[1], intervals[i][1]);
        } else {
            // Non-overlapping: add new interval
            result.push_back(intervals[i]);
        }
    }

    return result;
}

Use cases:

Calendar event scheduling
Insert interval into a set of intervals
Meeting room problem (count rooms needed)

Gotchas: Sort by start time first. After sorting, check only against the last merged interval. Update end time with max() to handle nested intervals.

60. Kadane’s Algorithm

When to use: Find maximum sum of contiguous subarray in O(n).

Complexity: O(n) time, O(1) space.

#include <bits/stdc++.h>
using namespace std;

int maxSubArray(vector<int>& nums) {
    int maxCurrent = nums[0];
    int maxGlobal = nums[0];

    for (int i = 1; i < nums.size(); ++i) {
        maxCurrent = max(nums[i], maxCurrent + nums[i]);
        maxGlobal = max(maxGlobal, maxCurrent);
    }

    return maxGlobal;
}

Use cases:

Maximum subarray sum
Stock buy-sell (modified version)
Best time to buy and sell stock with cooldown

Gotchas: Handles all-negative arrays correctly (returns the least negative). Reset maxCurrent when sum becomes negative only if next element is larger; simpler to use max(nums[i], maxCurrent + nums[i]).

61. Cyclic Sort / Index Placement

When to use: Place elements in their “natural” positions for arrays with [1..n] or [0..n-1] values in O(n) space.

Complexity: O(n) time, O(1) space.

#include <bits/stdc++.h>
using namespace std;

int findDisappeared(vector<int>& nums) {
    int n = nums.size();

    // Place each number at its correct index
    for (int i = 0; i < n; ++i) {
        while (nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
            swap(nums[i], nums[nums[i] - 1]);
        }
    }

    // Find the number that is out of place
    for (int i = 0; i < n; ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }

    return -1;
}

Use cases:

Find missing number in [1..n]
Find duplicate in [1..n]
Find all duplicates in [1..n]

Gotchas: Only works when values are in range [1..n] (or [0..n-1]). Inner while condition prevents infinite swaps on duplicates. Check nums[nums[i]-1] carefully to avoid index out of bounds.

62. Reservoir Sampling

When to use: Select k random items uniformly from a stream of unknown length.

Complexity: O(n) time, O(k) space.

#include <bits/stdc++.h>
using namespace std;

// For k=1 (pick one random item)
int reservoirSamplingK1(vector<int>& stream) {
    int result = stream[0];
    int count = 1;

    for (int i = 1; i < stream.size(); ++i) {
        int j = rand() % (++count);
        if (j == 0) {
            result = stream[i];
        }
    }

    return result;
}

// General k-reservoir sampling
vector<int> reservoirSamplingGeneral(vector<int>& stream, int k) {
    vector<int> reservoir(stream.begin(), stream.begin() + min(k, (int)stream.size()));
    int count = reservoir.size();

    for (int i = k; i < stream.size(); ++i) {
        int j = rand() % (++count);
        if (j < k) {
            reservoir[j] = stream[i];
        }
    }

    return reservoir;
}

Use cases:

Random sampling from unknown stream length
LinkedIn profile suggestions (random user selection)
Spotify shuffle from a playlist

Gotchas: rand() may have poor quality; for production use better PRNG. Probability of selecting each item must be exactly 1/n. Counter increments before random call.

63. Top-K with Heap / Quickselect

When to use: Find k largest or k smallest elements efficiently.

Complexity: Heap: O(n log k) time, O(k) space. Quickselect: O(n) avg time, O(1) space.

#include <bits/stdc++.h>
using namespace std;

// Approach 1: Min-heap of size k (for top-k largest)
vector<int> topKWithHeap(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>()> minHeap;

    for (int num : nums) {
        minHeap.push(num);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }

    vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top());
        minHeap.pop();
    }
    return result;
}

// Approach 2: Quickselect (find kth largest)
int quickSelect(vector<int>& nums, int left, int right, int k) {
    if (left == right) return nums[left];

    int pivot = nums[left];
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] < pivot) --j;
        nums[i] = nums[j];
        while (i < j && nums[i] >= pivot) ++i;
        nums[j] = nums[i];
    }
    nums[i] = pivot;

    if (k == i) return pivot;
    return k < i ? quickSelect(nums, left, i - 1, k) : quickSelect(nums, i + 1, right, k);
}

Use cases:

Top-k frequent elements
Kth largest/smallest element
Heavy hitter problems

Gotchas: Min-heap for top-k largest (not max-heap). Quickselect is O(n) on average but O(n²) worst-case. Partition logic must handle duplicates and pivot placement correctly.

64. Fast I/O & `ios_base::sync_with_stdio(false)`

When to use: Competitive programming or when processing millions of lines of input/output.

Complexity: Negligible overhead with fast I/O enabled vs. standard C++ streams.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        cout << x << "\n";
    }

    return 0;
}

Use cases:

Heavy I/O in competitive programming
Reading/writing millions of integers
Online judges with strict time limits

Gotchas: ios_base::sync_with_stdio(false) decouples C++ streams from C stdio (faster). cin.tie(NULL) removes the implicit flush before cin. Use "\n" instead of endl (endl flushes buffer). For even faster I/O, use scanf/printf if mixing C-style I/O.

Part F — Problem-Solving Skills

65. Problem Decomposition & Clarifying Questions

Before you code, slow down and ask questions. Clarifying ambiguities up front prevents false starts.

Clarify before coding

Input size range (n ≤ 100? 1e6? 1e9?)
Value ranges (1–100? negative numbers? floats?)
Duplicates allowed?
Is input already sorted?
Can input be empty? Single element?
What’s the expected output format (array, count, boolean, coordinates)?
Hard constraints on time and space?

Explore examples

Work through one or two small examples by hand. If the problem is vague (“find the best…”), your example clarifies what “best” means. Write it down—it makes your reasoning visible.

State brute force first

Even if you won’t code it, name the naive approach: “The brute force would be O(n²) checking all pairs.” This shows you understand the landscape before optimizing.

Identify the bottleneck

Ask yourself: which step is slow? Is it iteration, lookup, sorting, or graph traversal? Then ask: “Can I do this step faster?”

Talk while you code

Narrate your intent as you write. Don’t silently code for five minutes. Say things like: “I’m using a hash map here because I need O(1) lookups,” or “This deque will track the max in each window.”

66. Complexity Analysis — recognizing targets

Use constraints to work backward to your target complexity. This eliminates whole classes of approaches.

Input size	Acceptable complexity
n ≤ 12	O(n!)
n ≤ 20	O(2^n) / O(2^n · n)
n ≤ 500	O(n^3)
n ≤ 5000	O(n^2)
n ≤ 1e5	O(n log n)
n ≤ 1e6	O(n) or O(n log n) with small constants
n ≤ 1e9	O(log n) or O(√n)

Given a constraint, aim for the target in the table. If n ≤ 1e5, O(n²) will likely TLE; aim for O(n log n). If n ≤ 20, backtracking O(2^n) is viable.

Space matters too

Don’t ignore space complexity. Consider rolling arrays (use two rows instead of a full DP table), in-place modifications, vector<bool> (memory-efficient bitmask), or bitset for fixed ranges. On large inputs, O(n) space can fail if constants are high.

67. Choosing the Right Data Structure

Need	Use	Why
Fast lookup by key	`unordered_map<K,V>`	O(1) average; O(n) worst-case but rarely hit
Ordered iteration by key	`map<K,V>`	O(log n) per operation; keys always sorted
LIFO (call stack, undo)	`stack` or `vector`	O(1) push/pop at back
FIFO (task queue)	`queue` or `deque`	O(1) push back, pop front
Fast access to both ends	`deque`	O(1) front and back operations
Top-k elements / min/max stream	`priority_queue`	O(log n) push/pop; O(1) peek
Range queries on array	Segment tree / Fenwick	O(log n) query after O(n log n) build
Range updates + range queries	Segment tree with lazy propagation	O(log n) both; handles bulk updates
Union / connectivity (DSU)	Disjoint Set Union	Near O(1) amortized with path compression + union by rank
Prefix matching on strings	Trie	O(m) per word of length m; space is O(alphabet_size · total_chars)
Substring search	KMP / Z-algorithm / rolling hash	O(n+m) vs brute O(nm)
Sliding window min/max	Monotonic deque	O(n) single pass; tracks candidates only

68. Common Pitfalls & Gotchas

Integer overflow: Use long long for intermediate results. In binary search, use mid = l + (r - l) / 2 instead of (l + r) / 2.
Off-by-one errors: Carefully distinguish closed [l, r] vs half-open [l, r) intervals in binary search; test boundary conditions.
Iterator invalidation: Erasing from a vector or map mid-loop invalidates iterators. Either erase carefully, use a second pass, or copy data first.
Recursion depth: A linear chain of n ~ 1e5 recursive calls may overflow the stack. Prefer iterative solutions or increase stack size.
Negative modulo: In C++, a % m can be negative if a is negative. Use ((a % m) + m) % m for safety.
unordered_map worst-case: Theoretically O(n) per operation if hash collisions are adversarial. For competitive contests, use a custom hash or map.
Pass vectors by const reference: Avoid void func(vector<int> v); use void func(const vector<int>& v) to prevent expensive copies.
Missing base cases: DP and recursion crash without them. Always define base cases before the recurrence.
Signed vs unsigned: Comparing int and size_t can cause surprises. Be explicit about types.
C++ heap is max-heap by default: priority_queue<int> is a max-heap. For min-heap use priority_queue<int, vector<int>, greater<int>>.
Uninitialized values: vector<int> dp(n) initializes to zero, but local arrays like int dp[n] do not. Initialize explicitly if unsure.
Slow I/O: cin without sync_with_stdio(false) is slow for 1e6+ inputs. Add ios::sync_with_stdio(false); cin.tie(nullptr); at the start.
Reading a line after cin >> x: There’s a trailing newline in the input stream. Call cin.ignore() before getline().
Counting distinct elements: Use unordered_set for O(n) single pass rather than sorting.
Tree node indexing: Keep 0-indexed and 1-indexed node labels consistent throughout; mixing them is a common bug.

Algorithms, Patterns & Types

Part A — Core Data Structures

1. Arrays & vector

2. Strings & string

3. Hash Table — unordered_map / unordered_set

4. Ordered Map / Set — map / set

5. Stack — stack & manual

6. Queue — queue & circular buffer

7. Deque — deque

8. Linked List (singly, doubly)

9. Heap / Priority Queue — priority_queue

10. Binary Tree basics & traversals

11. Binary Search Tree (conceptual)

12. Trie (prefix tree)

13. Union-Find (DSU with path compression + union by rank)

14. Segment Tree (point update, range query)

15. Segment Tree with Lazy Propagation (range update + range query)

16. Fenwick Tree (Binary Indexed Tree)

17. Custom Comparators (struct with operator())

18. Custom Hash for unordered_map / unordered_set

Part B — Graphs

19. Graph Representations (adj list / adj matrix)

20. BFS on graph

21. DFS on graph

22. Connected Components

23. Topological Sort — Kahn’s (BFS) and DFS-based

24. Cycle Detection (directed & undirected)

25. Dijkstra’s Shortest Path

26. Bellman-Ford

27. Floyd-Warshall

28. Minimum Spanning Tree — Kruskal’s

29. Minimum Spanning Tree — Prim’s

30. LCA (binary lifting) & Tree DP

Part C — Search, DP & Divide-and-Conquer

31. Binary Search on sorted array

32. Binary Search on Answer

33. Two Pointers

34. Sliding Window (fixed & variable)

35. Prefix Sums & Difference Arrays

36. Recursion & Backtracking

37. Divide & Conquer (merge sort, quickselect)

38. DP — 1D Linear

39. DP — 2D Grid

40. DP — Knapsack (0/1, unbounded)

41. DP — Longest Common Subsequence / Edit Distance

42. DP — Interval DP

43. DP — Bitmask DP

44. DP — Digit DP

45. KMP (prefix function)

46. Z-function

47. Rabin-Karp (rolling hash)

48. Manacher’s Algorithm

49. Suffix Array (basic)

50. Number Theory — GCD, Modular Exponentiation, Modular Inverse

51. Sieve of Eratosthenes & prime factorization

52. Combinatorics — nCr mod p

53. Matrix Exponentiation

54. Bit Manipulation Tricks

55. XOR Tricks & Subset Sums

56. Geometry Basics (cross product, orientation, convex hull)

57. Monotonic Stack

58. Monotonic Deque

59. Merge Intervals

60. Kadane’s Algorithm

61. Cyclic Sort / Index Placement

62. Reservoir Sampling

63. Top-K with Heap / Quickselect

64. Fast I/O & ios_base::sync_with_stdio(false)

Part F — Problem-Solving Skills

65. Problem Decomposition & Clarifying Questions

Clarify before coding

Explore examples

State brute force first

Identify the bottleneck

Talk while you code

66. Complexity Analysis — recognizing targets

Space matters too

67. Choosing the Right Data Structure

68. Common Pitfalls & Gotchas

1. Arrays & `vector`

2. Strings & `string`

3. Hash Table — `unordered_map` / `unordered_set`

4. Ordered Map / Set — `map` / `set`

5. Stack — `stack` & manual

6. Queue — `queue` & circular buffer

7. Deque — `deque`

9. Heap / Priority Queue — `priority_queue`

17. Custom Comparators (struct with `operator()`)

18. Custom Hash for `unordered_map` / `unordered_set`

64. Fast I/O & `ios_base::sync_with_stdio(false)`