Main Algorithms & Problem-Solving

Patterns
A practical C++ study guide — what the algorithm does, how to recognize it, complexity, and
at least two worked examples for each.

Included: Kadane's Algorithm, Boyer–Moore Majority Vote, Boyer–Moore String Search, Dutch National
Flag, Two Pointers, Sliding Window, Prefix Sum, Binary Search, Merge Sort, Quick Sort, Heap / Priority
Queue, BFS, DFS, Dijkstra, Union-Find (DSU), Topological Sort, Monotonic Stack, Backtracking, and Fast
& Slow Pointers.

How to use this PDF: First learn the pattern/idea, then trace the examples by hand, and finally implement
the pseudocode in C++. The goal is not memorizing code — it is recognizing which algorithmic idea fits a
problem.

Main Algorithms Study Guide Page 1

 1. Kadane's Algorithm
Category: Arrays / Dynamic Programming

Core idea: Find the maximum-sum contiguous subarray in O(n). At each position, decide whether it is
better to extend the previous subarray or start a new one here.

When to recognize it: Use when the problem asks for the maximum/minimum sum of a contiguous
segment, especially when the array can contain negative values.

Complexity: Time: O(n) • Space: O(1)

C++ skeleton:
long long best = a[0], current = a[0];
for (int i = 1; i < n; ++i) {
current = max((long long)a[i], current + a[i]);
best = max(best, current);
}

Worked examples
Example 1: Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Best subarray: [4, -1, 2, 1]
Sum = 6. Kadane keeps the running sum only while doing so is better than starting again.

Example 2: Array: [-5, -2, -8]

The answer is -2, not 0, because the problem asks for a non-empty subarray. Kadane correctly returns
the largest individual value: -2.

2. Boyer–Moore Majority Vote

Category: Arrays / Voting

Core idea: Find an element that appears more than n/2 times using a candidate and a counter.
Matching values increase the count; different values cancel one vote.

When to recognize it: Use when a problem guarantees, or asks you to verify, a strict majority element
(> n/2 occurrences).

Complexity: Time: O(n) • Space: O(1)

C++ skeleton:
int candidate = 0, count = 0;
for (int x : a) {
if (count == 0) candidate = x;
count += (x == candidate ? 1 : -1);
}
// If a majority is NOT guaranteed, do a second pass to verify candidate.

Worked examples
Example 1: [2, 2, 1, 1, 1, 2, 2]
Candidate changes as opposing values cancel each other. Final candidate = 2. It appears 4/7 times, so
it is the majority.

Example 2: [3, 3, 4, 2, 3, 3, 3]
Final candidate = 3. It appears 5/7 times, so 3 is the majority.

3. Boyer–Moore String Search

Category: Strings / Pattern Matching

Main Algorithms Study Guide Page 2

 Core idea: Search for a pattern inside a text by comparing from right to left and using skip rules to
avoid checking every position.

When to recognize it: Useful for exact substring search when you want to skip large parts of the text
rather than checking every character at every shift.

Complexity: Typical performance is sublinear; worst-case depends on the variant and preprocessing.
Space is usually O(alphabet size + pattern length).

C++ skeleton:
// Core idea, not a full production implementation:
// 1. Build a bad-character table for the pattern.
// 2. Align pattern with text.
// 3. Compare from pattern's last character backward.
// 4. On mismatch, shift using the table.

Worked examples
Example 1: Text = "HERE IS A SIMPLE EXAMPLE"
Pattern = "EXAMPLE"
The comparison begins at the pattern's right side. A mismatch lets the algorithm jump forward instead
of shifting by one character.

Example 2: Text = "ABAAABCD"

Pattern = "ABC"
When the rightmost comparison fails, the bad-character information can shift the pattern several
positions, skipping text that cannot possibly match.

4. Dutch National Flag

Category: Arrays / Three-Way Partition

Core idea: Partition an array containing three categories (often 0, 1, 2) into three regions using three
pointers: low, mid, and high.

When to recognize it: Use for in-place three-way partitioning, especially sorting 0/1/2 or separating
values into less-than, equal-to, and greater-than regions.

Complexity: Time: O(n) • Space: O(1)

C++ skeleton:
int low = 0, mid = 0, high = n - 1;
while (mid <= high) {
if (a[mid] == 0) swap(a[low++], a[mid++]);
else if (a[mid] == 1) ++mid;
else swap(a[mid], a[high--]);
}

Worked examples
Example 1: [2, 0, 2, 1, 1, 0] → [0, 0, 1, 1, 2, 2]
0 goes left, 1 stays in the middle, and 2 goes right.

Example 2: [1, 2, 0, 2, 1, 0, 1]
The same three regions are formed in one pass without a second array.

Main Algorithms Study Guide Page 3

 5. Two Pointers
Category: Arrays / Strings

Core idea: Maintain two indices and move one or both according to a condition. This often turns an
O(n²) pair search into O(n).

When to recognize it: Common for sorted arrays, pair-sum problems, palindrome checks, merging, and
problems involving a left and right boundary.

Complexity: Usually O(n) after sorting; sorting itself may cost O(n log n).

C++ skeleton:
sort([Link](), [Link]());
int l = 0, r = n - 1;
while (l < r) {
long long s = a[l] + a[r];
if (s == target) { /* found */ break; }
if (s < target) ++l;
else --r;
}

Worked examples
Example 1: Sorted array [1, 2, 4, 7, 11, 15], target = 15.
1+15 is too large → move right. 1+11 is too small → move left. 4+11 = 15 → found.

Example 2: String "racecar".

Compare left and right characters, moving inward. Every pair matches, so it is a palindrome.

6. Sliding Window
Category: Arrays / Strings

Core idea: Keep a moving interval [left, right] and update the answer as the window expands or
shrinks. Avoid recomputing every subarray.

When to recognize it: Use for contiguous subarray/substring problems with conditions such as fixed
length, sum limits, or distinct-character constraints.

Complexity: Often O(n) because each pointer moves only forward.

C++ skeleton:
int left = 0;
for (int right = 0; right < n; ++right) {
// add a[right]
while (/* window invalid */) {
// remove a[left]
++left;
}
// update answer
}

Worked examples
Example 1: Longest substring without repeating characters: "abcabcbb".
Window grows to "abc". When the next 'a' repeats, move left until the window is valid again. Answer =
3.

Example 2: Maximum sum of a subarray of fixed length k=3 in [2,1,5,1,3,2].

Start with 2+1+5=8; slide by subtracting the outgoing value and adding the incoming value. Maximum
= 9 from [5,1,3].

Main Algorithms Study Guide Page 4

 7. Prefix Sum
Category: Arrays / Range Queries

Core idea: Precompute cumulative sums so a range sum can be answered by subtracting two prefix
values.

When to recognize it: Use when there are many sum queries over static data, or when you need to
transform subarray-sum conditions into prefix relationships.

Complexity: Build: O(n) • Each range query: O(1) • Space: O(n)

C++ skeleton:
vector<long long> pref(n + 1, 0);
for (int i = 0; i < n; ++i)
pref[i + 1] = pref[i] + a[i];

// sum of a[l..r]
long long sum = pref[r + 1] - pref[l];

Worked examples
Example 1: Array [3, 1, 4, 1, 5]. Query sum of indices 1..3: 1+4+1=6. Prefix subtraction answers it
instantly.

Example 2: Array [1, 2, 3, 4, 5]. Query [0..2] = 6 and [2..4] = 12. With prefix sums, both are O(1) after
preprocessing.

8. Binary Search
Category: Searching

Core idea: On a sorted or monotonic search space, check the middle and discard half of the remaining
possibilities.

When to recognize it: Use for sorted arrays or any problem where you can answer a monotonic yes/no
question such as 'is this capacity enough?'

Complexity: Time: O(log n) • Space: O(1) iterative

C++ skeleton:
int l = 0, r = n - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (a[m] == target) return m;
if (a[m] < target) l = m + 1;
else r = m - 1;
}
return -1;

Worked examples
Example 1: Search 23 in [3, 8, 12, 17, 23, 31, 40]. Check the middle, eliminate the wrong half, then
repeat. Found in logarithmic time.

Example 2: Find the minimum capacity needed to ship packages within D days. Binary-search the
capacity and use a linear feasibility check. This is 'binary search on the answer'.

Main Algorithms Study Guide Page 5

 9. Merge Sort
Category: Sorting / Divide & Conquer

Core idea: Split the array into halves, recursively sort both halves, then merge the two sorted halves.

When to recognize it: Use when you need guaranteed O(n log n) sorting and/or stable sorting. It is also
a foundation for inversion-counting problems.

Complexity: Time: O(n log n) • Space: O(n)

C++ skeleton:
void mergeSort(vector<int>& a, int l, int r) {
if (l >= r) return;
int m = l + (r - l) / 2;
mergeSort(a, l, m);
mergeSort(a, m + 1, r);
// merge two sorted halves
}

Worked examples
Example 1: [5, 2, 4, 1] → split [5,2] and [4,1] → sort them → merge [2,5] and [1,4] → [1,2,4,5].

Example 2: Count inversions in [2, 4, 1, 3, 5]. During merge, when 1 is chosen before remaining [2,4],
it creates two inversions: (2,1) and (4,1).

10. Quick Sort / Partition

Category: Sorting / Divide & Conquer

Core idea: Choose a pivot and partition elements around it. Recursively sort the two sides.

When to recognize it: Useful for fast in-memory sorting and especially for understanding
partition-based algorithms and quickselect.

Complexity: Average: O(n log n) • Worst: O(n²) • Stack: average O(log n)

C++ skeleton:
int partition(vector<int>& a, int l, int r) {
int pivot = a[r], i = l;
for (int j = l; j < r; ++j)
if (a[j] < pivot)
swap(a[i++], a[j]);
swap(a[i], a[r]);
return i;
}

Worked examples
Example 1: [7, 2, 1, 6, 8, 5, 3, 4], pivot=4.
Partition puts values smaller than 4 on the left and larger values on the right. Then recursively partition
both regions.

Example 2: Quickselect: find the kth smallest element. After partitioning, recurse only into the side
containing k. Average time becomes O(n), rather than fully sorting.

11. Heap / Priority Queue

Category: Data Structures / Greedy

Core idea: Maintain the largest or smallest element efficiently. A heap gives O(log n) insertion/removal
and O(1) access to the top.

Main Algorithms Study Guide Page 6

 When to recognize it: Use for top-k problems, repeatedly taking the minimum/maximum, scheduling,
merging sorted sequences, and Dijkstra's algorithm.

Complexity: Push/pop: O(log n) • Top: O(1)

C++ skeleton:
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;

[Link](10);
[Link](10);
int x = [Link]();

Worked examples
Example 1: Find the 3 largest values in [7, 1, 9, 4, 8, 2]. Keep a min-heap of size 3. The heap contains
only the current top three candidates.

Example 2: Task scheduling: repeatedly execute the task with the highest priority. Push tasks into a
priority queue and pop the best available task each time.

12. BFS — Breadth-First Search

Category: Graphs / Trees

Core idea: Explore a graph level by level using a queue. In an unweighted graph, the first time you
reach a node is through a shortest path in number of edges.

When to recognize it: Use for shortest paths in unweighted graphs, level-order tree traversal,
connected components, and minimum number of moves.

Complexity: Time: O(V+E) • Space: O(V)

C++ skeleton:
queue<int> q;
vector<bool> vis(n, false);
[Link](start);
vis[start] = true;

while (![Link]()) {
int u = [Link](); [Link]();
for (int v : adj[u]) {
if (!vis[v]) {
vis[v] = true;
[Link](v);
}
}
}

Worked examples
Example 1: Grid shortest path: from S to T when each move costs 1. BFS visits all cells at distance 1,
then distance 2, etc. The first time T is reached is shortest.

Example 2: Tree [1 with children 2,3; 2 has child 4]. BFS order is 1, 2, 3, 4 — exactly level by level.

Main Algorithms Study Guide Page 7

 13. DFS — Depth-First Search
Category: Graphs / Trees

Core idea: Go as deep as possible along one path before backtracking. Implement with recursion or an
explicit stack.

When to recognize it: Use for connected components, cycle detection, graph traversal, tree problems,
and as a foundation for topological sorting/backtracking.

Complexity: Time: O(V+E) • Space: O(V)

C++ skeleton:
void dfs(int u) {
vis[u] = true;
for (int v : adj[u])
if (!vis[v]) dfs(v);
}

Worked examples
Example 1: Graph edges: 0-1, 0-2, 1-3. Starting at 0, DFS can visit 0 → 1 → 3, then backtrack and visit
2.

Example 2: Count connected components: run DFS from every unvisited node. Each new DFS marks
exactly one component, so the number of DFS starts is the answer.

14. Dijkstra's Algorithm

Category: Graphs / Shortest Path

Core idea: Repeatedly finalize the unvisited node with the smallest known distance, then relax its
outgoing edges.

When to recognize it: Use for shortest paths from one source when all edge weights are non-negative.

Complexity: With binary heap: O((V+E) log V)

C++ skeleton:
priority_queue<pair<long long,int>,
vector<pair<long long,int>>,
greater<pair<long long,int>>> pq;

dist[s] = 0;
[Link]({0, s});

while (![Link]()) {
auto [d, u] = [Link](); [Link]();
if (d != dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (dist[v] > d + w) {
dist[v] = d + w;
[Link]({dist[v], v});
}
}
}

Worked examples
Example 1: Edges: A-B=4, A-C=1, C-B=2. From A, direct B costs 4, but A→C→B costs 3. Dijkstra
updates B to 3.

Example 2: Road network with non-negative travel times. Starting from a city, Dijkstra computes the
shortest travel time to every reachable city.

Main Algorithms Study Guide Page 8

 15. Union-Find / DSU
Category: Graphs / Connectivity

Core idea: Maintain disjoint sets with two optimizations: path compression and union by size/rank.

When to recognize it: Use for dynamic connectivity, Kruskal's minimum spanning tree, grouping, and
checking whether two nodes belong to the same component.

Complexity: Amortized almost O(1) per operation: O(alpha(n)).

C++ skeleton:
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) return;
if (sz[a] < sz[b]) swap(a, b);
parent[b] = a;
sz[a] += sz[b];
}

Worked examples
Example 1: Start with {1},{2},{3},{4}. Unite(1,2) and Unite(3,4). Now 1 and 2 are connected, while 1
and 3 are not.

Example 2: Kruskal: sort edges by weight and add an edge only if its endpoints are in different DSU
sets. This builds a minimum spanning tree without cycles.

16. Topological Sort

Category: Graphs / DAGs

Core idea: Order vertices so every directed edge u→v places u before v. It exists only for a directed
acyclic graph (DAG).

When to recognize it: Use for prerequisites, dependency resolution, course scheduling, build systems,
and DAG dynamic programming.

Complexity: Time: O(V+E) • Space: O(V)

C++ skeleton:
// Kahn's algorithm
queue<int> q;
for (int i = 0; i < n; ++i)
if (indegree[i] == 0) [Link](i);

while (![Link]()) {
int u = [Link](); [Link]();
order.push_back(u);
for (int v : adj[u])
if (--indegree[v] == 0) [Link](v);
}

Worked examples
Example 1: Prerequisites: Math → Algorithms, Programming → Algorithms. A valid order can be Math,
Programming, Algorithms.

Example 2: Build dependencies: A→C and B→C. You cannot build C before A and B. Topological sorting
produces an order respecting both dependencies.

Main Algorithms Study Guide Page 9

 17. Monotonic Stack
Category: Arrays / Stack

Core idea: Maintain a stack whose values are always increasing or decreasing. Elements that can no
longer be useful are popped once.

When to recognize it: Use for next greater/smaller element, daily temperatures, stock span, histogram
rectangle, and many 'nearest element' problems.

Complexity: Usually O(n) because each element is pushed and popped at most once.

C++ skeleton:
vector<int> st;
for (int i = 0; i < n; ++i) {
while (![Link]() && a[[Link]()] < a[i]) {
int j = [Link](); st.pop_back();
// i is the next greater index for j
}
st.push_back(i);
}

Worked examples
Example 1: [2, 1, 2, 4, 3]. Next greater values are [4,2,4,-1,-1]. The stack removes elements when the
current value becomes their first greater value.

Example 2: Daily temperatures [73,74,75,71,69,72,76,73]. For each day, pop colder days when a
warmer day arrives; the difference in indices gives the wait.

18. Backtracking
Category: Recursion / Search

Core idea: Build a partial solution, recursively explore choices, and undo the choice before trying the
next one.

When to recognize it: Use for permutations, combinations, subsets, N-Queens, Sudoku, maze search,
and constraint problems.

Complexity: Often exponential because the algorithm explores a decision tree.

C++ skeleton:
void backtrack(vector<int>& path) {
if (/* complete */) {
answer.push_back(path);
return;
}
for (int choice : choices) {
if (/* allowed */) {
path.push_back(choice);
backtrack(path);
path.pop_back(); // undo
}
}
}

Worked examples
Example 1: Permutations of [1,2,3]. Choose 1, then 2, then 3 → [1,2,3]. Undo 3 and try another choice,
producing all 6 permutations.

Example 2: N-Queens: place one queen per row. If a queen conflicts with a previous queen, stop
exploring that branch and backtrack.

Main Algorithms Study Guide Page 10

 19. Fast & Slow Pointers
Category: Linked Lists / Cycle Detection

Core idea: Move one pointer one step and another two steps. If they meet, a cycle exists. The same
idea can locate the middle of a linked list.

When to recognize it: Use for cycle detection, finding a linked-list midpoint, and some repeated-state
problems.

Complexity: Time: O(n) • Space: O(1)

C++ skeleton:
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;

Worked examples
Example 1: Linked list 1→2→3→4→2. Slow and fast eventually meet inside the cycle, proving that a
cycle exists.

Example 2: List 1→2→3→4→5. Slow moves 1 step while fast moves 2. When fast reaches the end, slow
is around the middle (node 3).

20. Greedy Interval Scheduling

Category: Greedy Algorithms

Core idea: For maximum number of non-overlapping intervals, repeatedly choose the interval that
finishes earliest.

When to recognize it: Use when a locally optimal choice can be proven to preserve the best possible
future. Interval scheduling is the classic example.

Complexity: O(n log n) due to sorting; O(n) after sorting.

C++ skeleton:
sort([Link](), [Link](),
[](auto& a, auto& b) { return [Link] < [Link]; });

int lastEnd = INT_MIN, count = 0;

for (auto [start, end] : intervals) {
if (start >= lastEnd) {
++count;
lastEnd = end;
}
}

Worked examples
Example 1: Intervals [(1,3),(2,4),(3,5),(5,7)]. Choose (1,3), then (3,5), then (5,7): 3 non-overlapping
intervals.

Example 2: [(0,6),(1,2),(3,4),(5,7),(8,9)]. Earliest finishes lead to (1,2),(3,4),(5,7),(8,9), giving 4

intervals.

Main Algorithms Study Guide Page 11

 Quick Recognition Cheat Sheet
Problem signal Think of

Maximum contiguous subarray sum Kadane

Element appears > n/2 Boyer–Moore Majority Vote

Find pattern in long text Boyer–Moore String Search / KMP

Only 0,1,2 or 3 categories Dutch National Flag

Pair in sorted array / palindrome Two Pointers

Contiguous window with a constraint Sliding Window

Many range-sum queries Prefix Sum

Sorted search / monotonic yes-no answer Binary Search

Guaranteed O(n log n) stable sorting Merge Sort

Partition / kth element Quick Sort / Quickselect

Top-k / repeatedly get min or max Heap / Priority Queue

Shortest path, unweighted BFS

Explore graph / components DFS

Shortest path, non-negative weights Dijkstra

Dynamic connectivity / MST DSU

Dependencies / prerequisites Topological Sort

Next greater/smaller element Monotonic Stack

Permutations / combinations / constraints Backtracking

Cycle in linked list / middle node Fast & Slow Pointers

Maximum non-overlapping intervals Greedy Interval Scheduling

Important: These are patterns, not isolated tricks. The fastest way to become good at algorithms is to
practice recognizing the signal in a problem before writing code. For example, “contiguous +
longest/shortest + changing constraint” should immediately make you consider a sliding window; “sorted
+ find a boundary” should make you consider binary search.

Main Algorithms Study Guide Page 12