C++ Interview Patterns ​
Idiomatic C++ templates for the 15 patterns that show up in 90% of coding interviews. Each section gives you: how to recognize the pattern, a compilable template, a real LeetCode example, and precise time and space complexity.
All code assumes:
#include <bits/stdc++.h>
using namespace std;1. Two Pointers ​
Recognize it when: the input is sorted (or can be sorted cheaply), or you're asked about pairs/triples, palindromes, or "in-place" array rearrangement. Anything O(n^2) brute force on a 1D array with pairs is a candidate.
Opposite ends ​
// Two Sum II — sorted, return 1-indexed positions summing to target.
vector<int> twoSumSorted(vector<int>& a, int target) {
int l = 0, r = a.size() - 1;
while (l < r) {
int s = a[l] + a[r];
if (s == target) return {l + 1, r + 1};
if (s < target) ++l;
else --r;
}
return {};
}Same direction (fast/slow) ​
// Valid Palindrome (LC 125) — skip non-alphanumerics.
bool isPalindrome(const string& s) {
int l = 0, r = s.size() - 1;
while (l < r) {
while (l < r && !isalnum(s[l])) ++l;
while (l < r && !isalnum(s[r])) --r;
if (tolower(s[l]) != tolower(s[r])) return false;
++l; --r;
}
return true;
}Complexity: O(n) time, O(1) extra space.
Example problems: LC 1 Two Sum (with sort), LC 15 3Sum, LC 125 Valid Palindrome, LC 167 Two Sum II, LC 26 Remove Duplicates.
2. Sliding Window ​
Recognize it when: the problem says "contiguous subarray" or "substring" with a constraint (length, sum, distinct chars, etc.). You're computing something over a moving range.
Fixed-size window ​
// Max sum of any subarray of size k.
long long maxSumK(const vector<int>& a, int k) {
long long sum = 0;
for (int i = 0; i < k; ++i) sum += a[i];
long long best = sum;
for (int i = k; i < (int)a.size(); ++i) {
sum += a[i] - a[i - k];
best = max(best, sum);
}
return best;
}Variable-size window ​
// Longest Substring Without Repeating Characters (LC 3).
int lengthOfLongestSubstring(const string& s) {
unordered_map<char,int> last; // char -> most recent index
int best = 0, l = 0;
for (int r = 0; r < (int)s.size(); ++r) {
auto it = last.find(s[r]);
if (it != last.end() && it->second >= l) l = it->second + 1;
last[s[r]] = r;
best = max(best, r - l + 1);
}
return best;
}Complexity: O(n) time, O(k) space (alphabet or window size).
Example problems: LC 3 Longest Substring, LC 76 Minimum Window Substring, LC 209 Min Subarray Sum, LC 438 Find All Anagrams.
3. Prefix Sums ​
Recognize it when: the problem asks repeated range-sum queries, or you need "sum from i to j" inside a loop. Combine with a hashmap for "how many subarrays have sum X".
1D prefix sum ​
// Build once:
vector<long long> pre(n + 1, 0);
for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] + a[i];
// Query sum of a[l..r] inclusive:
long long rangeSum = pre[r + 1] - pre[l];2D prefix sum (LC 304) ​
int R = mat.size(), C = mat[0].size();
vector<vector<long long>> pre(R + 1, vector<long long>(C + 1, 0));
for (int i = 0; i < R; ++i)
for (int j = 0; j < C; ++j)
pre[i+1][j+1] = mat[i][j] + pre[i][j+1] + pre[i+1][j] - pre[i][j];
// Sum of submatrix (r1,c1)-(r2,c2) inclusive:
long long s = pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1];Difference array (range updates in O(1)) ​
vector<long long> diff(n + 1, 0);
// Add v to a[l..r]:
diff[l] += v;
diff[r + 1] -= v;
// Recover final array:
vector<long long> a(n);
long long run = 0;
for (int i = 0; i < n; ++i) { run += diff[i]; a[i] = run; }Subarray Sum Equals K (LC 560) ​
int subarraySum(vector<int>& a, int k) {
unordered_map<long long,int> seen{{0, 1}}; // empty prefix
long long pre = 0; int ans = 0;
for (int x : a) {
pre += x;
auto it = seen.find(pre - k);
if (it != seen.end()) ans += it->second;
++seen[pre];
}
return ans;
}Complexity: O(n) preprocessing, O(1) per range query. Subarray-sum hashmap variant is O(n).
4. Monotonic Stack ​
Recognize it when: problem asks for "next greater / next smaller / previous greater / previous smaller" element, or for histogram / largest-rectangle style geometry.
// Next Greater Element to the right. res[i] = first j > i with a[j] > a[i], else -1.
vector<int> nextGreater(const vector<int>& a) {
int n = a.size();
vector<int> res(n, -1);
stack<int> st; // stack of indices, values strictly decreasing
for (int i = 0; i < n; ++i) {
while (!st.empty() && a[st.top()] < a[i]) {
res[st.top()] = a[i];
st.pop();
}
st.push(i);
}
return res;
}Largest Rectangle in Histogram (LC 84) ​
int largestRectangleArea(vector<int>& h) {
h.push_back(0); // sentinel
stack<int> st;
int best = 0;
for (int i = 0; i < (int)h.size(); ++i) {
while (!st.empty() && h[st.top()] > h[i]) {
int top = st.top(); st.pop();
int left = st.empty() ? -1 : st.top();
best = max(best, h[top] * (i - left - 1));
}
st.push(i);
}
return best;
}Complexity: O(n) amortized time, O(n) space. Each index is pushed and popped at most once.
Example problems: LC 496 Next Greater, LC 739 Daily Temperatures, LC 84 Largest Rectangle, LC 42 Trapping Rain Water.
5. Monotonic Deque ​
Recognize it when: you need the min/max of a sliding window efficiently. A plain monotonic stack can't drop from the front — a deque can.
// Sliding Window Maximum (LC 239).
vector<int> maxSlidingWindow(vector<int>& a, int k) {
deque<int> dq; // indices, values strictly decreasing
vector<int> out;
for (int i = 0; i < (int)a.size(); ++i) {
if (!dq.empty() && dq.front() <= i - k) dq.pop_front(); // drop out-of-window
while (!dq.empty() && a[dq.back()] < a[i]) dq.pop_back(); // maintain monotone
dq.push_back(i);
if (i >= k - 1) out.push_back(a[dq.front()]);
}
return out;
}Complexity: O(n) time, O(k) space.
6. Binary Search ​
Recognize it when: the search space is sorted or the answer is monotone (predicate that flips from false to true exactly once).
Classic: element in sorted array ​
int binarySearch(const vector<int>& a, int target) {
int l = 0, r = a.size() - 1; // inclusive
while (l <= r) {
int m = l + (r - l) / 2; // avoid overflow
if (a[m] == target) return m;
if (a[m] < target) l = m + 1;
else r = m - 1;
}
return -1;
}Lower bound (first index with a[i] >= target) ​
int lowerBound(const vector<int>& a, int target) {
int l = 0, r = a.size(); // half-open [l, r)
while (l < r) {
int m = l + (r - l) / 2;
if (a[m] < target) l = m + 1;
else r = m;
}
return l; // may equal a.size()
}Upper bound (first index with a[i] > target) ​
int upperBound(const vector<int>& a, int target) {
int l = 0, r = a.size();
while (l < r) {
int m = l + (r - l) / 2;
if (a[m] <= target) l = m + 1;
else r = m;
}
return l;
}Equivalent STL: lower_bound(a.begin(), a.end(), t) and upper_bound(...).
Binary search on the answer (LC 875 Koko) ​
bool canFinish(const vector<int>& piles, int h, long long k) {
long long hours = 0;
for (int p : piles) hours += (p + k - 1) / k; // ceil(p / k)
return hours <= h;
}
int minEatingSpeed(vector<int>& piles, int h) {
int l = 1, r = *max_element(piles.begin(), piles.end());
while (l < r) {
int m = l + (r - l) / 2;
if (canFinish(piles, h, m)) r = m;
else l = m + 1;
}
return l;
}Search in Rotated Sorted Array (LC 33) ​
int search(vector<int>& a, int target) {
int l = 0, r = a.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (a[m] == target) return m;
if (a[l] <= a[m]) { // left half sorted
if (a[l] <= target && target < a[m]) r = m - 1;
else l = m + 1;
} else { // right half sorted
if (a[m] < target && target <= a[r]) l = m + 1;
else r = m - 1;
}
}
return -1;
}Complexity: O(log n) time, O(1) space. "Binary search on answer" is O(log(range) * cost(check)).
7. BFS (Breadth-First Search) ​
Recognize it when: shortest path in an unweighted graph, "minimum steps/moves", or level-order traversal.
Level-by-level BFS on a graph ​
int shortestPath(int src, int dst, const vector<vector<int>>& adj) {
int n = adj.size();
vector<int> dist(n, -1);
queue<int> q;
q.push(src); dist[src] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
if (u == dst) return dist[u];
for (int v : adj[u]) if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
return -1;
}Grid BFS (4-directional) ​
// Number of Islands (LC 200).
int numIslands(vector<vector<char>>& g) {
int R = g.size(), C = g[0].size(), cnt = 0;
const int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1};
for (int i = 0; i < R; ++i)
for (int j = 0; j < C; ++j)
if (g[i][j] == '1') {
++cnt;
queue<pair<int,int>> q;
q.push({i, j}); g[i][j] = '0';
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
if (g[nr][nc] == '1') {
g[nr][nc] = '0';
q.push({nr, nc});
}
}
}
}
return cnt;
}Multi-source BFS (LC 994 Rotting Oranges) ​
Seed the queue with every source before starting. Layer count = distance from nearest source.
queue<pair<int,int>> q;
for (int i = 0; i < R; ++i)
for (int j = 0; j < C; ++j)
if (g[i][j] == 2) q.push({i, j});
// then normal BFS from the entire frontierComplexity: O(V + E) time, O(V) space. For a grid, V = R·C.
Example problems: LC 200 Islands, LC 127 Word Ladder, LC 994 Rotting Oranges, LC 752 Open the Lock.
8. DFS (Depth-First Search) ​
Recognize it when: you need connected components, backtracking, cycle detection, or tree traversal. Preferred over BFS when the structure is naturally recursive.
Recursive DFS on a graph ​
vector<vector<int>> adj;
vector<int> vis;
void dfs(int u) {
vis[u] = 1;
for (int v : adj[u]) if (!vis[v]) dfs(v);
}Iterative DFS (avoids stack overflow on deep graphs) ​
void dfsIter(int src) {
stack<int> st; st.push(src);
while (!st.empty()) {
int u = st.top(); st.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int v : adj[u]) if (!vis[v]) st.push(v);
}
}Clone Graph (LC 133) ​
struct Node { int val; vector<Node*> neighbors; };
unordered_map<Node*, Node*> copies;
Node* cloneGraph(Node* n) {
if (!n) return nullptr;
if (copies.count(n)) return copies[n];
Node* c = new Node{n->val, {}};
copies[n] = c;
for (Node* nb : n->neighbors) c->neighbors.push_back(cloneGraph(nb));
return c;
}Complexity: O(V + E) time, O(V) space (recursion stack + visited).
9. Topological Sort ​
Recognize it when: you have dependencies/prerequisites and need an order, or the question is "is this DAG?" / "can you finish all courses?".
Kahn's algorithm (BFS on indegrees) ​
// Course Schedule II (LC 210) — return a valid order or [] if impossible.
vector<int> findOrder(int n, vector<vector<int>>& prereqs) {
vector<vector<int>> adj(n);
vector<int> indeg(n, 0);
for (auto& p : prereqs) { // [a, b] means b -> a
adj[p[1]].push_back(p[0]);
++indeg[p[0]];
}
queue<int> q;
for (int i = 0; i < n; ++i) if (indeg[i] == 0) q.push(i);
vector<int> order;
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);
}
return (int)order.size() == n ? order : vector<int>{};
}DFS-based (postorder = reverse topo) ​
vector<int> order;
vector<int> state; // 0 unvisited, 1 on stack, 2 done
bool cyclic = false;
function<void(int)> dfs = [&](int u) {
state[u] = 1;
for (int v : adj[u]) {
if (state[v] == 1) cyclic = true;
else if (state[v] == 0) dfs(v);
}
state[u] = 2;
order.push_back(u); // postorder
};
// After running DFS from every unvisited node, reverse(order).Complexity: O(V + E) time, O(V) space.
10. Dijkstra's Shortest Path ​
Recognize it when: weighted graph, all edge weights are non-negative, and you want shortest path from a source.
// Network Delay Time (LC 743).
// times[i] = {u, v, w}. Returns time for signal to reach ALL nodes, or -1.
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<pair<int,int>>> adj(n + 1); // adj[u] = {v, w}
for (auto& t : times) adj[t[0]].push_back({t[1], t[2]});
vector<long long> dist(n + 1, LLONG_MAX);
dist[k] = 0;
priority_queue<pair<long long,int>,
vector<pair<long long,int>>,
greater<>> pq; // min-heap by distance
pq.push({0, k});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // stale entry
for (auto [v, w] : adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
long long ans = 0;
for (int i = 1; i <= n; ++i) ans = max(ans, dist[i]);
return ans == LLONG_MAX ? -1 : (int)ans;
}Complexity: O((V + E) log V) with a binary heap. Use 0-1 BFS (deque) for weights in {0, 1}.
11. Union-Find (DSU) ​
Recognize it when: you're dynamically merging groups, asking "are x and y connected?", counting connected components, or detecting cycles in an undirected graph.
struct DSU {
vector<int> parent, rank_;
int components;
DSU(int n) : parent(n), rank_(n, 0), components(n) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // path compression (halving)
x = parent[x];
}
return x;
}
bool unite(int a, int b) { // returns true if merged
a = find(a); b = find(b);
if (a == b) return false;
if (rank_[a] < rank_[b]) swap(a, b);
parent[b] = a;
if (rank_[a] == rank_[b]) ++rank_[a];
--components;
return true;
}
bool connected(int a, int b) { return find(a) == find(b); }
};
// Number of Connected Components (LC 323):
int countComponents(int n, vector<vector<int>>& edges) {
DSU d(n);
for (auto& e : edges) d.unite(e[0], e[1]);
return d.components;
}Complexity: O(alpha(n)) per op — effectively O(1) amortized. O(n) space.
Example problems: LC 323 Components, LC 684 Redundant Connection, LC 547 Friend Circles, LC 721 Accounts Merge.
12. Dynamic Programming ​
Recognize it when: the problem asks "how many ways", "min/max cost", or "can you reach X" and the brute force has overlapping subproblems.
1D DP (LC 70 Climbing Stairs) ​
int climbStairs(int n) {
if (n <= 2) return n;
int a = 1, b = 2, c; // rolling variables, O(1) space
for (int i = 3; i <= n; ++i) { c = a + b; a = b; b = c; }
return b;
}2D DP (LC 72 Edit Distance) ​
int minDistance(const string& a, const string& b) {
int m = a.size(), n = b.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
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];
}Space-compressed 2D → 1D (rolling array) ​
When each row of a 2D DP only depends on the previous row, keep two rows (or one, iterating carefully):
// Unique Paths (LC 62) compressed to O(n).
int uniquePaths(int m, int n) {
vector<int> dp(n, 1);
for (int i = 1; i < m; ++i)
for (int j = 1; j < n; ++j) dp[j] += dp[j-1];
return dp[n-1];
}Top-down memoization ​
unordered_map<long long, int> memo;
function<int(int,int)> solve = [&](int i, int state) -> int {
if (/* base case */) return 0;
long long key = ((long long)i << 20) | state;
auto it = memo.find(key);
if (it != memo.end()) return it->second;
int ans = /* recurrence */;
return memo[key] = ans;
};Top-down vs bottom-up: top-down is easier to derive (recurrence reads naturally). Bottom-up is typically faster (no recursion overhead) and makes space compression obvious. Use top-down first if the state space is sparse.
Complexity: states × transitions per state. Most interview DPs are O(n), O(n*m), or O(n^2).
13. Backtracking ​
Recognize it when: problem asks for all combinations/permutations/subsets/placements, or solves a constraint puzzle (N-queens, sudoku).
Template: choose / recurse / un-choose ​
void backtrack(state& cur, result& out) {
if (isSolution(cur)) { out.push_back(cur); return; }
for (auto choice : choicesFrom(cur)) {
if (!promising(cur, choice)) continue; // prune
apply(cur, choice); // choose
backtrack(cur, out); // recurse
undo(cur, choice); // un-choose
}
}Subsets (LC 78) ​
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> out;
vector<int> cur;
function<void(int)> rec = [&](int i) {
if (i == (int)nums.size()) { out.push_back(cur); return; }
rec(i + 1); // skip
cur.push_back(nums[i]);
rec(i + 1); // take
cur.pop_back();
};
rec(0);
return out;
}Permutations (LC 46) ​
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> out;
function<void(int)> rec = [&](int i) {
if (i == (int)nums.size()) { out.push_back(nums); return; }
for (int j = i; j < (int)nums.size(); ++j) {
swap(nums[i], nums[j]);
rec(i + 1);
swap(nums[i], nums[j]);
}
};
rec(0);
return out;
}N-Queens (LC 51) — with pruning ​
int totalNQueens(int n) {
vector<bool> col(n), diag1(2*n), diag2(2*n);
int ans = 0;
function<void(int)> rec = [&](int r) {
if (r == n) { ++ans; return; }
for (int c = 0; c < n; ++c) {
if (col[c] || diag1[r+c] || diag2[r-c+n]) continue;
col[c] = diag1[r+c] = diag2[r-c+n] = true;
rec(r + 1);
col[c] = diag1[r+c] = diag2[r-c+n] = false;
}
};
rec(0);
return ans;
}Complexity: typically O(branching^depth). Subsets = O(2^n · n), permutations = O(n! · n). Space O(depth) for recursion.
14. Trie ​
Recognize it when: you repeatedly query prefixes of strings, autocomplete, word search over a dictionary.
Array-based (fixed alphabet, lowercase a-z) ​
struct Trie {
struct Node { array<int,26> next{}; bool end = false; };
vector<Node> pool{Node{}}; // pool[0] is root
void insert(const string& w) {
int u = 0;
for (char ch : w) {
int c = ch - 'a';
if (!pool[u].next[c]) {
pool.push_back(Node{});
pool[u].next[c] = pool.size() - 1;
}
u = pool[u].next[c];
}
pool[u].end = true;
}
bool search(const string& w) const {
int u = walk(w);
return u != -1 && pool[u].end;
}
bool startsWith(const string& p) const { return walk(p) != -1; }
private:
int walk(const string& s) const {
int u = 0;
for (char ch : s) {
int c = ch - 'a';
if (!pool[u].next[c]) return -1;
u = pool[u].next[c];
}
return u;
}
};Hashmap-based (arbitrary characters) ​
struct Trie {
struct Node {
unordered_map<char, unique_ptr<Node>> next;
bool end = false;
};
Node root;
void insert(const string& w) {
Node* u = &root;
for (char ch : w) {
auto& nxt = u->next[ch];
if (!nxt) nxt = make_unique<Node>();
u = nxt.get();
}
u->end = true;
}
};Complexity: O(L) per insert/search/startsWith (L = string length). Space O(N·L) for N words.
Example problems: LC 208 Implement Trie, LC 212 Word Search II, LC 648 Replace Words.
15. Heap / Priority Queue Patterns ​
C++ priority_queue is a max-heap by default. For a min-heap:
priority_queue<int> maxH;
priority_queue<int, vector<int>, greater<int>> minH;Top K elements (LC 215 — kth largest) ​
Maintain a min-heap of size k. Any number larger than the top displaces it.
int findKthLargest(vector<int>& a, int k) {
priority_queue<int, vector<int>, greater<>> pq;
for (int x : a) {
pq.push(x);
if ((int)pq.size() > k) pq.pop();
}
return pq.top();
}Complexity: O(n log k) time, O(k) space.
Merge K Sorted Lists (LC 23) ​
struct ListNode { int val; ListNode* next; };
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
for (auto* h : lists) if (h) pq.push(h);
ListNode dummy, *tail = &dummy;
while (!pq.empty()) {
auto* n = pq.top(); pq.pop();
tail->next = n; tail = n;
if (n->next) pq.push(n->next);
}
return dummy.next;
}Complexity: O(N log k) where N = total nodes, k = number of lists.
Median from Data Stream (LC 295) — two heaps ​
Keep a max-heap of the lower half and a min-heap of the upper half, balanced so |low| - |high| ∈ {0, 1}.
class MedianFinder {
priority_queue<int> low; // max-heap
priority_queue<int, vector<int>, greater<>> high; // min-heap
public:
void addNum(int x) {
low.push(x);
high.push(low.top()); low.pop(); // move largest of low
if (high.size() > low.size()) { low.push(high.top()); high.pop(); }
}
double findMedian() {
if (low.size() > high.size()) return low.top();
return (low.top() + high.top()) / 2.0;
}
};Complexity: O(log n) per addNum, O(1) per findMedian.
Cheat Sheet: Pattern Recognition ​
| Clue in the problem | Pattern |
|---|---|
| sorted array, pair/triple, in-place | Two Pointers |
| contiguous subarray/substring with constraint | Sliding Window |
| many range-sum queries | Prefix Sum |
| next greater/smaller, histogram | Monotonic Stack |
| sliding window min/max | Monotonic Deque |
| sorted OR monotone predicate | Binary Search |
| shortest path in unweighted graph, level order | BFS |
| connected components, backtracking, recursion | DFS |
| dependencies, "can you finish all ..." | Topological Sort |
| shortest path with non-negative weights | Dijkstra |
| dynamic grouping, "are X and Y connected" | Union-Find |
| overlapping subproblems, optimal substructure | DP |
| enumerate all X (subsets, perms, placements) | Backtracking |
| prefix queries, autocomplete, dictionary lookup | Trie |
| top k, k sorted streams, running median | Heap |
Memorize the templates, practice recognizing the clues, and most interview problems reduce to "which of these do I apply, and how do I glue them together?"