C++ Algorithmic Pattern Reference

Two Pointers & Sliding Window

The two pointers technique uses two indices that move through a data structure (array/string) to solve
problems efficiently 1 . It’s often used on sorted arrays (e.g. finding a pair with given sum) and window
problems. In the sliding window variant, the two pointers define a window (contiguous segment) that
slides forward, expanding or contracting to satisfy a condition 2 .

Strategy: Initialize two indices (e.g. left=0 , right=0 ). Move the right pointer to expand the window
and include new elements. Use a condition (sum, frequency, etc.) to check validity. While invalid, move the
left pointer to shrink the window. Maintain any running counts or sums. This yields O(n) time for many
window problems. If the data is not sorted, use a hash map to count frequencies within the window.

Common pitfalls & edge cases:

- Off-by-one errors when expanding/contracting the window boundaries.
- Failing to update window sum/count when moving pointers.
- Infinite loops if left and right are not progressed correctly.
- For problems requiring unique elements, ensure to track counts (e.g. with unordered_map<char,int> ).
- If using sliding window on unsorted data, remember to move both pointers and maintain invariants.

// Example: Largest subarray with sum <= k (sliding window)

int maxSubarraySumLEK(vector<int>& a, int k) {
int left = 0, sum = 0, maxLen = 0;
for (int right = 0; right < [Link](); right++) {
sum += a[right]; // include a[right] in window
// Shrink window from left while sum > k
while (left <= right && sum > k) {
sum -= a[left]; // remove a[left] from window
left++;
}
// Now window [left..right] has sum <= k
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}

// Example: Two-sum in sorted array (two pointers)

bool twoSumSorted(vector<int>& a, int target) {
int i = 0, j = [Link]() - 1;
while (i < j) {

1
 int s = a[i] + a[j];
if (s == target) {
return true;
} else if (s < target) {
i++; // need larger sum
} else {
j--; // need smaller sum
}
}
return false;
}

Binary Search & Search-on-Answer

Binary search halves the search range by comparing the target with the middle element, achieving $O(\log
n)$ time on sorted data 3 . Key points: use mid = lo + (hi - lo)/2 to avoid overflow; decide to
move left or right based on comparison.

Strategy (classic): Given a sorted array a and a target, maintain lo and hi indices. Compute mid . If
a[mid] equals target (or satisfies predicate), record it (or return), then narrow search (e.g. find first/last
occurrence). If a[mid] is less than target, move lo = mid+1 ; else hi = mid-1 . Continue while
lo <= hi .

Binary search on answer: Use when you must find a threshold value (e.g. minimum largest sum of
subarrays). Define a predicate function check(x) that returns true if answer ≤ x. Then binary search on
the answer range and use check(mid) to guide search. This works if the predicate is monotonic 4 .

Pitfalls:
- Off-by-one in loop conditions ( lo <= hi vs < ).
- Wrong update of lo / hi causing infinite loop (ensure progress).
- Overflow when computing mid (use the safe formula).
- For answer-search, ensure the predicate is monotonic; break ties carefully.

// Template: Binary search in sorted array (find target or insertion point)

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

2
 }
return -1; // or return lo for insertion point if needed
}

// Template: Binary search on answer space

// Example: find minimum x such that check(x) is true.
int searchAnswer(int lo, int hi) {
int ans = hi;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (check(mid)) {
ans = mid; // possible answer, search lower
hi = mid - 1;
} else {
lo = mid + 1; // need a larger answer
}
}
return ans;
}
// bool check(int x) should be defined based on problem.

References: Binary search splits the search interval in half 3 . Binary search on answer is used when you
can check “is the answer ≥ x?” 4 .

Dynamic Programming (DP)

DP solves optimization/counting problems by breaking into subproblems and storing results. Key idea:
define a state and transitions. The three DP fundamentals are overlapping subproblems, optimal
substructure, and state transition equations 5 . The typical approach is: clarify state and choices, define
dp[], then compute 6 .

General strategy:
- Identify what your dp state represents (e.g. dp[i] = best solution up to i, or dp[i][j] = solution using
first i items with condition j).
- Recurrence: Express dp[...] in terms of smaller states. Commonly either top-down (memo) or bottom-
up loops.
- Base cases: initialize (e.g. dp[0][*] ).
- Compute in increasing order of state to respect dependencies.

1D DP (Subarray/Subsequence): e.g. Knapsack / Coin Change / Max Subarray.

- E.g. dp[i] = max(dp[i-1] + a[i], 0) for max subarray sum (Kadane’s algorithm is a DP).
- For 0/1 knapsack: dp[w] = max value for weight ≤ w, loop items and weights backwards.

3
 // Example: 0/1 Knapsack (1D DP optimized by weight)
int knapsack(vector<int>& wt, vector<int>& val, int W) {
vector<int> dp(W+1, 0);
for (int i = 0; i < [Link](); i++) {
for (int w = W; w >= wt[i]; w--) {
dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
}
}
return dp[W];
}

2D DP (Arrays/Strings): e.g. Longest Common Subsequence (LCS), Edit Distance, DP on grids.

- For LCS: dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1] . Recurrence: if chars match,
dp[i][j]=dp[i-1][j-1]+1 , else max(dp[i-1][j], dp[i][j-1]) .
- For grid shortest path: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) .

// Example: LCS (bottom-up DP)

int lcs(string &s1, string &s2) {
int n = [Link](), m = [Link]();
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1[i-1] == s2[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[n][m];
}

Matrix Chain Multiplication (Partition DP): define dp[i][j] = min cost to multiply matrices i..j.
Recurrence: try every split k between i and j:
dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost(i,k,j)) . Use triple loops.

// Example: Matrix Chain Multiplication (dimensions in dims)

int matrixChain(vector<int>& dims) {
int n = [Link]();
vector<vector<int>> dp(n, vector<int>(n, 0));
// dp[i][i] = 0 (single matrix cost)
for (int len = 2; len < n; len++) { // chain length
for (int i = 1; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = INT_MAX;

4
 for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k+1][j]
+ dims[i-1] * dims[k] * dims[j];
dp[i][j] = min(dp[i][j], cost);
}
}
}
return dp[1][n-1];
}

LIS (Longest Increasing Subsequence): can do O(n^2) DP or O(n log n). The DP: dp[i] = 1 +
max(dp[j]) for all j<i with a[j]<a[i] . Then answer = max dp[i] .
- (Pitfall: watch out for strict vs non-strict inequality.)

Common DP pitfalls:
- Incorrect state definition or missing states.
- Forgetting base cases (initialize dp with zeros or -INF).
- Off-by-one in loops.
- High memory/time (optimize space if needed).
- Overcounting (ensure transitions are correct and combinatorial dp divides cases).

DP Summary: Define your state and relation carefully: “clarify state → choices → dp” 6 7 . Use
memoization or iterative tables to store overlapping subproblem results.

Backtracking (DFS on Combinatorial Space)

Backtracking explores all possibilities (e.g. combinations, permutations, subset generation) via recursion. It
is essentially a DFS on a “decision tree” 8 9 .

Strategy: Write a recursive function (often with a path list and parameters/state). At each call, either
record a solution (if end condition) or iterate over next choices. For each choice: add it to path , recurse,
then remove (undo) it on return. This is the “make a choice, recurse, undo” pattern 10 .

vector<vector<int>> res;
void backtrack(int idx, vector<int>& path, vector<int>& nums) {
if (idx == [Link]()) {
res.push_back(path);
return;
}
// NOT include nums[idx]
backtrack(idx+1, path, nums);
// INCLUDE nums[idx]
path.push_back(nums[idx]);
backtrack(idx+1, path, nums);

5
 path.pop_back(); // undo choice
}

This code generates all subsets of nums . For permutations: loop over each element not used yet, mark it
used, recurse, then unmark.

Pitfalls:
- Forgetting to undo changes (e.g. not popping from path).
- Duplicates: if input has duplicates, you may need to skip identical choices or sort first.
- Deep recursion: ensure you avoid exceeding call stack for very deep recursion (though interview problems
usually ≤ 20 levels).

Graph Algorithms
Graphs have many patterns. Key traversals: BFS (breadth-first) and DFS (depth-first) for visits, plus shortest
paths (Dijkstra, Bellman-Ford), topological sort, etc.

BFS and DFS

• BFS (breadth-first search) uses a queue to explore layers. It finds the shortest path (fewest edges) in
unweighted graphs 11 .
• DFS (depth-first search) uses recursion or a stack to explore deep paths first. It is used to detect
cycles, compute connected components, and generate paths. On a tree it also yields traversal orders.

// BFS template (unweighted shortest path / level order)

void bfs(int src, vector<vector<int>>& adj, vector<int>& dist) {
int n = [Link]();
[Link](n, -1);
queue<int> q;
dist[src] = 0;
[Link](src);
while (![Link]()) {
int u = [Link](); [Link]();
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
[Link](v);
}
}
}
}

// DFS template (recursive)

void dfs(int u, vector<vector<int>>& adj, vector<bool>& vis) {
vis[u] = true;

6
 // process u if needed
for (int v : adj[u]) {
if (!vis[v]) {
dfs(v, adj, vis);
}
}
}

Pitfalls (BFS/DFS):
- Forgetting to mark visited, causing infinite loops.
- Stack overflow in DFS if graph is very deep (rare for normal problem sizes).
- For graphs with multiple components, loop over all nodes to start new DFS/BFS if unvisited.

Shortest Paths (Weighted)

• Dijkstra’s algorithm finds shortest paths in a graph with non-negative edge weights. It repeatedly
selects the unvisited vertex with smallest dist[] , then relaxes its edges 12 . Typically
implemented with a min-heap priority_queue for $O(m \log n)$. Pitfall: does not work with negative
weights.

// Dijkstra (with adjacency list of (neighbor, weight))

vector<int> dijkstra(int src, vector<vector<pair<int,int>>>& adj) {
int n = [Link]();
const int INF = 1e9;
vector<int> dist(n, INF);
dist[src] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
[Link]({0, src});
while (![Link]()) {
auto [d,u] = [Link](); [Link]();
if (d > dist[u]) continue; // stale pair
for (auto &edge : adj[u]) {
int v = [Link], w = [Link];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
[Link]({dist[v], v});
}
}
}
return dist;
}

• Bellman-Ford works with negative weights (detecting negative cycles). It relaxes all edges n-1 times,
updating distances. If a distance can be improved in the nth iteration, a negative cycle exists 13 .

7
 // Bellman-Ford (returns true if no negative cycle reachable)
bool bellmanFord(int src, vector<tuple<int,int,int>>& edges, vector<int>& dist,
int n) {
const int INF = 1e9;
[Link](n, INF);
dist[src] = 0;
// Relax edges up to n-1 times
for (int i = 0; i < n-1; i++) {
bool updated = false;
for (auto &e : edges) {
int u, v, w;
tie(u, v, w) = e;
if (dist[u] < INF && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
updated = true;
}
}
if (!updated) break;
}
// Check for negative cycle
for (auto &e : edges) {
int u, v, w;
tie(u, v, w) = e;
if (dist[u] < INF && dist[u] + w < dist[v]) {
return false; // negative cycle found
}
}
return true;
}

Dijkstra vs Bellman-Ford: Bellman-Ford handles negative weights (but is slower) 13 .

Topological Sort (DAG)

For directed acyclic graphs, topological sort orders nodes such that all edges go from earlier to later. Use
DFS post-order or Kahn’s algorithm (queue of in-degree zero). Pitfall: Ensure graph has no cycles.

// Kahn's algorithm for Topo Sort (returns empty if cycle)

vector<int> topoSort(int n, vector<vector<int>>& adj) {
vector<int> indeg(n, 0), order;
for (int u = 0; u < n; u++) {
for (int v : adj[u]) indeg[v]++;
}
queue<int> q;
for (int i = 0; i < n; i++) if (indeg[i] == 0) [Link](i);

8
 while (![Link]()) {
int u = [Link](); [Link]();
order.push_back(u);
for (int v : adj[u]) {
if (--indeg[v] == 0) {
[Link](v);
}
}
}
if ([Link]() != n) return {}; // cycle detected
return order;
}

Union-Find (Disjoint Set Union)

DSU maintains disjoint sets of elements with union and find operations 14 . Useful for connectivity and
Kruskal’s MST. Each set has a “leader” found by find_set(x) .

struct DSU {
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) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
void unite(int a, int b) {
a = find(a); b = find(b);
if (a != b) {
// union by rank
if (rank[a] < rank[b]) swap(a,b);
parent[b] = a;
if (rank[a] == rank[b]) rank[a]++;
}
}
};

Pitfall: Always use path compression and union by rank/size to achieve near-$O(1)$ amortized time 14 .

Heaps / Priority Queues

Heaps solve problems requiring repeated access to max or min elements. C++ priority_queue defaults
to max-heap; use greater<> or negative values for min-heap.

9
Strategy: Use priority_queue<int> for largest, or priority_queue<int, vector<int>,
greater<int>> for smallest. For problems like “find k largest” or “merge k sorted lists”, heaps are ideal.

// Example: K-th largest element using min-heap of size k

int findKthLargest(vector<int>& a, int k) {
priority_queue<int, vector<int>, greater<int>> minpq;
for (int x : a) {
[Link](x);
if ([Link]() > k) [Link]();
}
return [Link]();
}

Pitfalls: Too many elements in heap can cause memory/time issues; always pop when heap exceeds needed
size.

Hashing and Maps

Use unordered maps ( unordered_map / unordered_set ) for frequency counting or fast lookups. E.g.,
sliding window with conditions on counts, or hashing string to int.

Example: Longest substring with ≤K distinct chars (sliding window + map): maintain a count map and
current distinct count.

int longestAtMostKDistinct(string &s, int K) {

unordered_map<char,int> freq;
int left = 0, distinct = 0, ans = 0;
for (int right = 0; right < [Link](); right++) {
if (++freq[s[right]] == 1) distinct++;
while (distinct > K) {
if (--freq[s[left]] == 0) distinct--;
left++;
}
ans = max(ans, right - left + 1);
}
return ans;
}

Pitfalls: high load factor in unordered maps (reserve enough size if needed), iterating while shrinking
(ensure to reduce count to 0 and remove keys if needed).

10
Monotonic Stack
A stack whose elements are in increasing or decreasing order. Useful for next greater/smaller element
problems and sliding window maximum (via deque).

Strategy: Maintain a stack of indices or values. For next greater element: iterate through array, and while
current > stack top, pop and set result. Then push current.

// Next Greater Element (for each element, find next greater to its right)
vector<int> nextGreater(vector<int>& a) {
int n = [Link]();
vector<int> ans(n, -1);
stack<int> st; // stores indices of a in decreasing order
for (int i = 0; i < n; i++) {
while (![Link]() && a[i] > a[[Link]()]) {
ans[[Link]()] = a[i];
[Link]();
}
[Link](i);
}
return ans;
}

Pitfalls: be careful with equal elements (use >= vs > as per problem), and clear remaining stack (they get
default -1 if no greater).

Additional Tips
• String DP (palindromes, substrings): Often similar to array DP; e.g. longest palindromic
subsequence uses 2D DP.
• Greedy: Some interval or scheduling problems use greedy (e.g. sort by end time, always pick earliest
finish). Outline greedy choices and proof why local optimal leads to global.
• Edge cases: Always check for empty input, single element, large values. For recursion or DP, check
boundaries. For graphs, consider disconnected or no-path cases.

By following these strategy outlines and templates, you can tackle a wide range of coding problems. Each
section above provides a pattern, its reasoning, and a code skeleton in C++17 with STL usage and
comments.

Sources: Standard algorithmic strategies and templates 1 2 3 4 6 7 11 15 12 13 14

(consulted for patterns and explanations).

1 Two Pointers Technique - GeeksforGeeks

[Link]

11
 2 Sliding Window Technique - GeeksforGeeks
[Link]

3 4 Binary Search - Algorithms for Competitive Programming

[Link]

5 6 7 Dynamic Programming Common Patterns and Code Template | Labuladong Algo Notes
[Link]

8 9 10 Backtracking Algorithm Common Patterns and Code Template | Labuladong Algo Notes
[Link]

11 Breadth First Search - Algorithms for Competitive Programming

[Link]

12 Dijkstra - finding shortest paths from given vertex - Algorithms for Competitive Programming
[Link]

13 Bellman-Ford - finding shortest paths with negative weights - Algorithms for Competitive Programming
[Link]

14 Disjoint Set Union - Algorithms for Competitive Programming

[Link]

15 Depth First Search - Algorithms for Competitive Programming

[Link]

12