Dynamic Programming Patterns

Dynamic Programming solves problems by breaking them into overlapping subproblems and storing
results to avoid recomputation.

0/1 Knapsack Problem

Problem Statement: You have a knapsack with capacity W and n items. Each item has weight w[i] and
value v[i]. Maximize value without exceeding weight capacity. Each item can be taken at most once.

Example:

Weights: [1, 3, 4, 5], Values: [1, 4, 5, 7], Capacity: 7

Optimal: Take items with weights 3 and 4 (values 4 + 5 = 9)

DP State: dp[i][w] = maximum value using first i items with weight limit w

Recurrence:

If weight[i-1] > w: dp[i][w] = dp[i-1][w] (can't include item)

Else: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i-1]] + value[i-1])

cpp

// Space optimized version (O(W) space instead of O(nW))

int knapsackOptimized(vector<int>& weights, vector<int>& values, int capacity) {
vector<int> dp(capacity + 1, 0);

for(int i = 0; i < [Link](); i++) {

// Process backwards to avoid using updated values
for(int w = capacity; w >= weights[i]; w--) {
dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
}
}

return dp[capacity];
}

Longest Common Subsequence (LCS)

Problem Statement: Given two strings, find the length of their longest common subsequence. A
subsequence is derived by deleting some characters without changing the order of remaining characters.

Example:

Input: text1 = "abcde", text2 = "ace"

 Output: 3 (LCS is "ace")

DP State: dp[i][j] = LCS length of text1[0...i-1] and text2[0...j-1]

Recurrence:

If text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1

Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

cpp

// Also returns the actual LCS string

pair<int, string> longestCommonSubsequenceWithString(string text1, string text2) {
int m = [Link](), n = [Link]();
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(text1[i-1] == text2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}

// Reconstruct LCS string

string lcs = "";
int i = m, j = n;
while(i > 0 && j > 0) {
if(text1[i-1] == text2[j-1]) {
lcs = text1[i-1] + lcs;
i--; j--;
} else if(dp[i-1][j] > dp[i][j-1]) {
i--;
} else {
j--;
}
}

return {dp[m][n], lcs};

}

Edit Distance (Levenshtein Distance)

Problem Statement: Given two strings word1 and word2,# Essential Algorithms Reference Guide A
comprehensive guide to important algorithms with C++ implementations
Table of Contents
1. Disjoint Set Union (DSU)

2. Segment Tree

3. Dijkstra's Algorithm
4. Binary Indexed Tree (Fenwick Tree)

5. Trie Data Structure

6. KMP String Matching

7. Binary Search Variations

8. Graph Algorithms

9. Dynamic Programming Patterns

10. Mathematical Algorithms

Disjoint Set Union (DSU)

Use Cases: Connected components, cycle detection, Kruskal's MST, dynamic connectivity

Time Complexity: O(α(n)) per operation (nearly constant)

Implementation

cpp
 class DSU {
vector<int> parent, rank;
public:
DSU(int n) {
[Link](n);
[Link](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;
}

bool connected(int x, int y) {

return find(x) == find(y);
}
};

Example Problem: Number of Connected Components

cpp
 int countComponents(int n, vector<vector<int>>& edges) {
DSU dsu(n);
for(auto& edge : edges) {
[Link](edge[0], edge[1]);
}

int components = 0;
for(int i = 0; i < n; i++) {
if([Link](i) == i) components++;
}
return components;
}

Segment Tree
Use Cases: Range queries, range updates, lazy propagation

Time Complexity: O(log n) per query/update, O(n) build

Basic Range Sum Query

cpp
class SegmentTree {
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 = [Link]();
[Link](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); }
};

Lazy Propagation for Range Updates

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

void push(int node, int start, int end) {

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

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

if(start >= l && end <= r) {

lazy[node] += val;
push(node, start, end);
return;
}

int mid = (start + end) / 2;

updateRange(2*node, start, mid, l, r, val);
updateRange(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];
}

public:
LazySegmentTree(int size) {
n = size;
[Link](4 * n);
[Link](4 * n);
}

void updateRange(int l, int r, int val) {

updateRange(1, 0, n-1, l, r, val);
}
};
Dijkstra's Algorithm
Use Cases: Shortest path in weighted graphs (non-negative weights)

Time Complexity: O((V + E) log V)

Implementation

cpp

vector<int> dijkstra(int start, vector<vector<pair<int, int>>>& graph) {

int n = [Link]();
vector<int> dist(n, INT_MAX);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

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

while(![Link]()) {
int d = [Link]().first;
int u = [Link]().second;
[Link]();

if(d > dist[u]) continue;

for(auto& edge : graph[u]) {

int v = [Link];
int w = [Link];

if(dist[u] + w < dist[v]) {

dist[v] = dist[u] + w;
[Link]({dist[v], v});
}
}
}

return dist;
}

Example: Network Delay Time

cpp
 int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<pair<int, int>>> graph(n + 1);
for(auto& time : times) {
graph[time[0]].push_back({time[1], time[2]});
}

vector<int> dist = dijkstra(k, graph);

int maxTime = 0;
for(int i = 1; i <= n; i++) {
if(dist[i] == INT_MAX) return -1;
maxTime = max(maxTime, dist[i]);
}
return maxTime;
}

Binary Indexed Tree (Fenwick Tree)

Use Cases: Prefix sums, range sum queries with point updates

Time Complexity: O(log n) per operation

Implementation

cpp
 class BIT {
vector<long long> tree;
int n;

public:
BIT(int size) {
n = size;
[Link](n + 1, 0);
}

void update(int idx, int val) {

for(int i = idx; i <= n; i += i & (-i)) {
tree[i] += val;
}
}

long long query(int idx) {

long long sum = 0;
for(int i = idx; i > 0; i -= i & (-i)) {
sum += tree[i];
}
return sum;
}

long long rangeQuery(int l, int r) {

return query(r) - query(l - 1);
}
};

Example: Count Inversions

cpp
 int countInversions(vector<int>& arr) {
// Coordinate compression
vector<int> sorted = arr;
sort([Link](), [Link]());
[Link](unique([Link](), [Link]()), [Link]());

BIT bit([Link]());
int inversions = 0;

for(int i = [Link]() - 1; i >= 0; i--) {

int pos = lower_bound([Link](), [Link](), arr[i]) - [Link]() + 1;
inversions += [Link](pos - 1);
[Link](pos, 1);
}

return inversions;
}

Trie Data Structure

Use Cases: String prefix matching, autocomplete, word search

Time Complexity: O(m) per operation where m is string length

Implementation

cpp
struct TrieNode {
TrieNode* children[26];
bool isEnd;

TrieNode() {
for(int i = 0; i < 26; i++) children[i] = nullptr;
isEnd = false;
}
};

class Trie {
TrieNode* root;

public:
Trie() { root = new TrieNode(); }

void insert(string word) {

TrieNode* curr = root;
for(char c : word) {
int idx = c - 'a';
if(!curr->children[idx]) {
curr->children[idx] = new TrieNode();
}
curr = curr->children[idx];
}
curr->isEnd = true;
}

bool search(string word) {

TrieNode* curr = root;
for(char c : word) {
int idx = c - 'a';
if(!curr->children[idx]) return false;
curr = curr->children[idx];
}
return curr->isEnd;
}

bool startsWith(string prefix) {

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

KMP String Matching

Use Cases: Pattern matching, finding all occurrences

Time Complexity: O(n + m)

Implementation

cpp
vector<int> computeLPS(string pattern) {
int m = [Link]();
vector<int> lps(m, 0);
int len = 0, i = 1;

while(i < m) {
if(pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
} else {
if(len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}

vector<int> KMPSearch(string text, string pattern) {

vector<int> result;
vector<int> lps = computeLPS(pattern);

int n = [Link]();
int m = [Link]();
int i = 0, j = 0;

while(i < n) {
if(pattern[j] == text[i]) {
j++; i++;
}

if(j == m) {
result.push_back(i - j);
j = lps[j - 1];
} else if(i < n && pattern[j] != text[i]) {
if(j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
 return result;
}

Binary Search Variations

Standard Binary Search

cpp

int binarySearch(vector<int>& arr, int target) {

int left = 0, right = [Link]() - 1;

while(left <= right) {

int mid = left + (right - left) / 2;
if(arr[mid] == target) return mid;
else if(arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}

Lower Bound (First occurrence >= target)

cpp

int lowerBound(vector<int>& arr, int target) {

int left = 0, right = [Link]();

while(left < right) {

int mid = left + (right - left) / 2;
if(arr[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}

Upper Bound (First occurrence > target)

cpp
 int upperBound(vector<int>& arr, int target) {
int left = 0, right = [Link]();

while(left < right) {

int mid = left + (right - left) / 2;
if(arr[mid] <= target) left = mid + 1;
else right = mid;
}
return left;
}

Graph Algorithms

Graph Algorithms

DFS Applications
Problem 1: Number of Islands Given a 2D grid of '1's (land) and '0's (water), count the number of
islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or
vertically.

Example:

grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1

Approach: DFS from each unvisited '1' to mark the entire island.

cpp
 class Solution {
void dfs(vector<vector<char>>& grid, int i, int j) {
if(i < 0 || i >= [Link]() || j < 0 || j >= grid[0].size() || grid[i][j] == '0') {
return;
}

grid[i][j] = '0'; // Mark as visited

// Visit all 4 directions

dfs(grid, i+1, j);
dfs(grid, i-1, j);
dfs(grid, i, j+1);
dfs(grid, i, j-1);
}

public:
int numIslands(vector<vector<char>>& grid) {
int islands = 0;

for(int i = 0; i < [Link](); i++) {

for(int j = 0; j < grid[0].size(); j++) {
if(grid[i][j] == '1') {
islands++;
dfs(grid, i, j); // Mark entire island
}
}
}

return islands;
}
};

Problem 2: Detect Cycle in Undirected Graph

cpp
 bool hasCycleDFS(int node, int parent, vector<vector<int>>& adj, vector<bool>& visited) {
visited[node] = true;

for(int neighbor : adj[node]) {

if(neighbor == parent) continue; // Skip edge to parent

if(visited[neighbor]) return true; // Back edge found = cycle

if(hasCycleDFS(neighbor, node, adj, visited)) {

return true;
}
}

return false;
}

bool detectCycle(int n, vector<vector<int>>& adj) {

vector<bool> visited(n, false);

for(int i = 0; i < n; i++) {

if(!visited[i]) {
if(hasCycleDFS(i, -1, adj, visited)) {
return true;
}
}
}

return false;
}

BFS Applications
Problem 1: Shortest Path in Unweighted Graph Find shortest distance between two nodes in
unweighted graph.

Example:

Graph: 0-1-2-3, 0-2

Shortest path from 0 to 3: 0→2→3 (distance = 2)

cpp
 int shortestPath(int start, int end, vector<vector<int>>& adj) {
if(start == end) return 0;

queue<int> q;
vector<bool> visited([Link](), false);
vector<int> distance([Link](), -1);

[Link](start);
visited[start] = true;
distance[start] = 0;

while(![Link]()) {
int node = [Link]();
[Link]();

for(int neighbor : adj[node]) {

if(!visited[neighbor]) {
visited[neighbor] = true;
distance[neighbor] = distance[node] + 1;
[Link](neighbor);

if(neighbor == end) return distance[neighbor];

}
}
}

return -1; // No path exists

}

Problem 2: Word Ladder Given two words (beginWord and endWord) and a dictionary, find length of
shortest transformation sequence from beginWord to endWord, changing only one letter at a time.

Example:

beginWord = "hit", endWord = "cog"

wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5 ("hit" → "hot" → "dot" → "dog" → "cog")

cpp
 int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> wordSet([Link](), [Link]());
if([Link](endWord) == [Link]()) return 0;

queue<string> q;
[Link](beginWord);
int level = 1;

while(![Link]()) {
int size = [Link]();

for(int i = 0; i < size; i++) {

string word = [Link]();
[Link]();

if(word == endWord) return level;

// Try changing each character

for(int j = 0; j < [Link](); j++) {
char original = word[j];
for(char c = 'a'; c <= 'z'; c++) {
if(c == original) continue;

word[j] = c;
if([Link](word) != [Link]()) {
[Link](word);
[Link](word); // Mark as visited
}
}
word[j] = original; // Restore
}
}
level++;
}

return 0;
}

Topological Sort Applications

Problem 1: Course Schedule There are numCourses courses labeled 0 to numCourses-1. Some courses
have prerequisites. Return true if you can finish all courses.

Example:

Input: numCourses = 2, prerequisites = [[1,0]]

 Output: true (take course 0 first, then course 1)

Approach: If graph has a cycle, impossible to complete all courses.

cpp

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {

vector<vector<int>> adj(numCourses);
vector<int> indegree(numCourses, 0);

// Build graph
for(auto& prereq : prerequisites) {
adj[prereq[1]].push_back(prereq[0]);
indegree[prereq[0]]++;
}

// Topological sort using Kahn's algorithm

queue<int> q;
for(int i = 0; i < numCourses; i++) {
if(indegree[i] == 0) [Link](i);
}

int completed = 0;
while(![Link]()) {
int course = [Link]();
[Link]();
completed++;

for(int nextCourse : adj[course]) {

indegree[nextCourse]--;
if(indegree[nextCourse] == 0) {
[Link](nextCourse);
}
}
}

return completed == numCourses;

}

Problem 2: Find Order to Complete Courses Return the ordering of courses you should take to finish all
courses.

cpp
 vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adj(numCourses);
vector<int> indegree(numCourses, 0);

for(auto& prereq : prerequisites) {

adj[prereq[1]].push_back(prereq[0]);
indegree[prereq[0]]++;
}

queue<int> q;
for(int i = 0; i < numCourses; i++) {
if(indegree[i] == 0) [Link](i);
}

vector<int> order;
while(![Link]()) {
int course = [Link]();
[Link]();
order.push_back(course);

for(int nextCourse : adj[course]) {

indegree[nextCourse]--;
if(indegree[nextCourse] == 0) {
[Link](nextCourse);
}
}
}

return [Link]() == numCourses ? order : vector<int>();

}

Dynamic Programming Patterns

Knapsack (0/1)

cpp
 int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
int n = [Link]();
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

for(int i = 1; i <= n; i++) {

for(int w = 1; w <= capacity; 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][capacity];
}

Longest Common Subsequence

cpp

int longestCommonSubsequence(string text1, string text2) {

int m = [Link](), n = [Link]();
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(text1[i-1] == text2[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

cpp
 int minDistance(string word1, string word2) {
int m = [Link](), n = [Link]();
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(word1[i-1] == word2[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];
}

Mathematical Algorithms

Fast Exponentiation

cpp

long long fastPow(long long base, long long exp, long long mod) {
long long result = 1;
base %= mod;

while(exp > 0) {
if(exp & 1) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1;
}

return result;
}

GCD and LCM

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

long long lcm(long long a, long long b) {

return (a / gcd(a, b)) * b;
}

Sieve of Eratosthenes

cpp

vector<bool> sieveOfEratosthenes(int n) {
vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;

for(int i = 2; i * i <= n; i++) {

if(isPrime[i]) {
for(int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}

return isPrime;
}

Matrix Exponentiation

cpp
 vector<vector<long long>> multiply(vector<vector<long long>>& A,
vector<vector<long long>>& B, int mod) {
int n = [Link]();
vector<vector<long long>> C(n, vector<long long>(n, 0));

for(int i = 0; i < n; i++) {

for(int j = 0; j < n; j++) {
for(int k = 0; k < n; k++) {
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
}
}
}

return C;
}

vector<vector<long long>> matrixPower(vector<vector<long long>>& matrix,

long long n, int mod) {
int size = [Link]();
vector<vector<long long>> result(size, vector<long long>(size, 0));

// Identity matrix
for(int i = 0; i < size; i++) result[i][i] = 1;

while(n > 0) {
if(n & 1) result = multiply(result, matrix, mod);
matrix = multiply(matrix, matrix, mod);
n >>= 1;
}

return result;
}

Quick Reference

Common Time Complexities

Sorting: O(n log n)

Binary Search: O(log n)

DFS/BFS: O(V + E)
Dijkstra: O((V + E) log V)

Union-Find: O(α(n)) ≈ O(1)

 Segment Tree: O(log n) query/update
Trie: O(m) where m is string length

Space Optimization Tips

Use 1D arrays when possible for DP
Coordinate compression for large ranges

Lazy propagation for range updates

Path compression in Union-Find

Common Patterns
Two Pointers: Sorted arrays, palindromes

Sliding Window: Subarray problems

Binary Search: Answer search problems

DP: Optimization problems

Graph: Connectivity, shortest paths

This reference guide covers essential algorithms for competitive programming and technical interviews.
Practice implementing these algorithms and understanding when to apply each technique.