DSA Patterns Documentation
The 15 coding-interview patterns — how to spot each one, a C++ template and the classic problems to practise.
Most coding interview problems are variations of about 15 patterns. Learn to spot the pattern from the problem statement and you already know the shape of the solution. Each pattern below has when to use it, a C++ template and classic problems to practise in Practice.
1. How to Recognise the Pattern
| The problem says… | Try |
|---|---|
| sorted array, find a pair / triplet | Two pointers |
| contiguous subarray / substring, "longest/shortest with condition" | Sliding window |
| subarray sum equals k, range sums | Prefix sum + hash map |
| sorted / monotonic, "minimum possible maximum", "first true" | Binary search (on index or on answer) |
| linked list cycle, middle node | Fast & slow pointers |
| intervals, meetings, merge overlapping | Sort + merge intervals |
| next greater / smaller element, histogram | Monotonic stack |
| top K, K-th largest, merge K sorted | Heap |
| tree paths, depth, subtree answers | DFS (recursion) |
| level by level, shortest steps in unweighted graph/grid | BFS |
| dependencies, ordering of tasks | Topological sort |
| connected groups, "are they connected?", cycle in undirected graph | Union–Find |
| all combinations / permutations / subsets | Backtracking |
| count ways, min/max cost, overlapping subproblems | Dynamic programming |
| locally best choice works (prove it!) | Greedy |
| prefix / word search / autocomplete | Trie |
| XOR, single number, subsets as masks | Bit manipulation |
2. Two Pointers
When: sorted arrays, pairs/triplets, reversing, removing duplicates in place, palindromes.
// pair with target sum in a sorted array
int l = 0, r = n - 1;
while (l < r) {
int s = a[l] + a[r];
if (s == target) return {l, r};
if (s < target) l++; else r--;
}
Complexity: O(n) time, O(1) space. Practise: Two Sum II, 3Sum, Container With Most Water, Remove Duplicates from Sorted Array, Valid Palindrome, Trapping Rain Water.
3. Sliding Window
When: longest/shortest contiguous subarray or substring meeting a condition.
// longest substring without repeating characters (variable window)
unordered_map<char, int> cnt;
int best = 0;
for (int l = 0, r = 0; r < s.size(); r++) {
cnt[s[r]]++;
while (cnt[s[r]] > 1) cnt[s[l++]]--; // shrink until valid
best = max(best, r - l + 1);
}
Fixed window of size k: add a[r], remove a[r - k] once r >= k.
Complexity: O(n). Practise: Max Sum Subarray of Size K, Longest Substring Without Repeating Characters, Minimum Window Substring, Longest Repeating Character Replacement, Permutation in String.
Notes: Sliding Window.
4. Prefix Sum & Hashing
When: range sums, "subarray sum equals k", counting pairs, frequency questions.
// number of subarrays with sum k (works with negatives)
unordered_map<long long, int> seen{{0, 1}};
long long sum = 0; int count = 0;
for (int x : a) {
sum += x;
if (seen.count(sum - k)) count += seen[sum - k];
seen[sum]++;
}
Complexity: O(n) time, O(n) space. Practise: Two Sum, Subarray Sum Equals K, Contiguous Array, Longest Consecutive Sequence, Group Anagrams, Range Sum Query.
5. Binary Search (and on the Answer)
When: sorted data, or a monotonic yes/no question ("can we do it with capacity X?").
// first index where a[i] >= x (lower_bound)
int lo = 0, hi = n; // answer in [lo, hi]
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] >= x) hi = mid; else lo = mid + 1;
}
// binary search on the answer: smallest capacity that works
long long lo = 1, hi = 1e18;
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (canDo(mid)) hi = mid; else lo = mid + 1;
}
Complexity: O(log n) × cost of the check. Practise: Search in Rotated Sorted Array, Find Peak Element, Koko Eating Bananas, Capacity to Ship Packages, Aggressive Cows, Median of Two Sorted Arrays.
6. Fast & Slow Pointers
When: linked list cycle, middle node, cycle start, "happy number".
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true; // cycle
}
return false; // slow is the middle when the loop ends
Practise: Linked List Cycle I & II, Middle of the Linked List, Palindrome Linked List, Find the Duplicate Number, Happy Number.
7. Merge Intervals
When: overlapping ranges, meeting rooms, insert interval.
sort(iv.begin(), iv.end());
vector<vector<int>> out;
for (auto &cur : iv) {
if (out.empty() || out.back()[1] < cur[0]) out.push_back(cur);
else out.back()[1] = max(out.back()[1], cur[1]);
}
Complexity: O(n log n). Practise: Merge Intervals, Insert Interval, Non-overlapping Intervals, Meeting Rooms II (sort + min-heap of end times).
8. Monotonic Stack
When: next/previous greater or smaller element, spans, largest rectangle.
// next greater element to the right
vector<int> ans(n, -1);
stack<int> st; // indices, values decreasing
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] < a[i]) {
ans[st.top()] = a[i];
st.pop();
}
st.push(i);
}
Complexity: O(n) — each index is pushed and popped once. Practise: Next Greater Element, Daily Temperatures, Stock Span, Largest Rectangle in Histogram, Sliding Window Maximum (monotonic deque).
9. Heap / Top K
When: K largest/smallest, K-th element, merge K sorted lists, running median.
// k largest elements: keep a min-heap of size k
priority_queue<int, vector<int>, greater<int>> pq;
for (int x : a) {
pq.push(x);
if (pq.size() > k) pq.pop();
}
// pq.top() is the k-th largest
Complexity: O(n log k). Practise: Kth Largest Element, Top K Frequent Elements, K Closest Points, Merge K Sorted Lists, Find Median from Data Stream (two heaps), Task Scheduler.
10. Tree DFS & BFS
DFS — return information up from subtrees:
int height(TreeNode* root) {
if (!root) return 0;
return 1 + max(height(root->left), height(root->right));
}
BFS — level order:
queue<TreeNode*> q; q.push(root);
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode* node = q.front(); q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
Practise: Max Depth, Diameter, Balanced Tree, Lowest Common Ancestor, Path Sum, Level Order / Zigzag, Right Side View, Validate BST, Serialize/Deserialize.
11. Graph BFS / DFS, Topological Sort & Union–Find
// BFS shortest path in an unweighted graph / grid
vector<int> dist(n, -1); queue<int> q;
dist[src] = 0; q.push(src);
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); }
}
// topological sort (Kahn) — also detects cycles
vector<int> indeg(n), order; queue<int> q;
for (int u = 0; u < n; u++) for (int v : adj[u]) indeg[v]++;
for (int u = 0; u < n; u++) if (!indeg[u]) q.push(u);
while (!q.empty()) {
int u = q.front(); q.pop(); order.push_back(u);
for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
}
// order.size() < n → there is a cycle
// union–find with path compression and union by size
vector<int> parent(n), sz(n, 1);
iota(parent.begin(), parent.end(), 0);
function<int(int)> find = [&](int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); };
auto unite = [&](int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
parent[b] = a; sz[a] += sz[b];
return true;
};
Practise: Number of Islands, Rotting Oranges, Word Ladder, Course Schedule I & II, Clone Graph, Number of Provinces, Redundant Connection, Network Delay Time (Dijkstra). Notes: Graphs — BFS and DFS.
12. Backtracking
When: generate all combinations, permutations, subsets, or search with constraints (N-Queens, Sudoku).
void solve(int start, vector<int>& path) {
result.push_back(path); // record a subset
for (int i = start; i < n; i++) {
if (i > start && a[i] == a[i - 1]) continue; // skip duplicates (array sorted)
path.push_back(a[i]); // choose
solve(i + 1, path); // explore
path.pop_back(); // un-choose
}
}
Practise: Subsets I & II, Permutations, Combination Sum, Palindrome Partitioning, Word Search, N-Queens, Sudoku Solver.
13. Dynamic Programming
When: count the ways / min or max cost, and the same subproblem repeats. Steps: define state → write the recurrence → set base cases → choose order (memoisation top-down or table bottom-up) → optimise space.
// 1-D: climbing stairs / house robber shape
vector<int> dp(n + 1);
dp[0] = 1; dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
// 2-D: longest common subsequence
vector<vector<int>> L(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
L[i][j] = (s[i-1] == t[j-1]) ? L[i-1][j-1] + 1 : max(L[i-1][j], L[i][j-1]);
| Family | Examples |
|---|---|
| 1-D | Climbing Stairs, House Robber, Decode Ways, Jump Game |
| Grid | Unique Paths, Minimum Path Sum, Dungeon Game |
| Knapsack | 0/1 Knapsack, Partition Equal Subset Sum, Coin Change, Target Sum |
| Strings | LCS, Edit Distance, Longest Palindromic Subsequence, Word Break |
| LIS | Longest Increasing Subsequence, Russian Doll Envelopes |
| Intervals | Matrix Chain Multiplication, Burst Balloons |
| Stocks | Buy and Sell Stock I–IV, with cooldown |
Notes: Dynamic Programming.
14. Greedy, Trie & Bit Manipulation
Greedy — sort, then take the locally best choice (prove with an exchange argument):
// activity selection: max non-overlapping intervals
sort(iv.begin(), iv.end(), [](auto& a, auto& b) { return a[1] < b[1]; });
int count = 0, end = INT_MIN;
for (auto& x : iv) if (x[0] >= end) { count++; end = x[1]; }
Practise: Jump Game II, Gas Station, Assign Cookies, Minimum Platforms, Fractional Knapsack.
Trie — prefix search: Implement Trie, Word Search II, Longest Common Prefix, Maximum XOR of Two Numbers. Notes: Trie (Prefix Tree).
Bit manipulation — x & (x - 1) removes the lowest set bit; x & -x isolates it; a ^ a = 0:
int single = 0;
for (int x : a) single ^= x; // the element that appears once
for (int mask = 0; mask < (1 << n); mask++) { /* every subset */ }
Practise: Single Number, Counting Bits, Power of Two, Subsets (bitmask), Missing Number.
15. Cheat Sheet & References
Spot the pattern
sorted + pair/triplet → two pointers
contiguous + longest/shortest → sliding window
subarray sum = k → prefix sum + hash map
monotonic yes/no → binary search on answer
next greater/smaller → monotonic stack
top k / k-th → heap of size k
shortest steps, unweighted → BFS
dependencies → topological sort
connectivity → union-find
all combinations → backtracking
count ways / min cost → dynamic programming
Templates
while (l < r) { /* move l or r */ } // two pointers
for (r...) { add(r); while (bad) remove(l++); } // sliding window
while (lo < hi) { mid; ok(mid) ? hi = mid : lo = mid+1; } // binary search
while (st.size() && a[st.top()] < a[i]) st.pop(); // monotonic stack
if (pq.size() > k) pq.pop(); // top k
choose; solve(i + 1); unchoose; // backtracking
dp[i] = f(dp[i-1], dp[i-2]); // dp
Complexities
two pointers / window / prefix / stack: O(n)
sort-based: O(n log n); heap top-k: O(n log k)
BFS/DFS: O(V + E); union-find: ~O(1) per op
subsets: O(2^n); permutations: O(n!)
References