Algorithm Techniques with Code Examples
1. Sliding Window
Application: Used for problems involving contiguous sequences, like maximum subarray sum,
longest substring without repeating characters.
Code Example (C++):
int maxSum(vector<int>& nums, int k) {
int sum = 0, maxSum = 0;
for (int i = 0; i < k; i++) sum += nums[i];
maxSum = sum;
for (int i = k; i < [Link](); i++) {
sum += nums[i] - nums[i - k];
maxSum = max(maxSum, sum);
}
return maxSum;
}
2. Two Pointers
Application: Efficient technique for solving problems like pair sums, array partitioning.
Code Example:
bool hasPairWithSum(vector<int>& nums, int target) {
int left = 0, right = [Link]() - 1;
sort([Link](), [Link]());
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) return true;
else if (sum < target) left++;
else right--;
}
return false;
}
3. Binary Search
Application: Find elements or conditions efficiently in sorted arrays or search spaces.
Code Example:
int binarySearch(vector<int>& nums, int target) {
int left = 0, right = [Link]() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
4. Hash Map / Hash Set
Application: Fast lookup, frequency counting, and avoiding duplicates.
Code Example:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> seen;
for (int num : nums) {
if ([Link](num)) return true;
[Link](num);
}
return false;
}
5. Greedy
Application: Problems where local optimal choices lead to a global optimum.
Code Example:
int maxActivities(vector<pair<int, int>>& activities) {
sort([Link](), [Link](), [](auto& a, auto& b) {
return [Link] < [Link];
});
int count = 1, lastEnd = activities[0].second;
for (int i = 1; i < [Link](); i++) {
if (activities[i].first >= lastEnd) {
count++;
lastEnd = activities[i].second;
}
}
return count;
}
6. Backtracking
Application: Generate permutations, combinations, and solve constraint problems like Sudoku.
Code Example:
void backtrack(vector<vector<int>>& res, vector<int>& curr, vector<bool>&
used, vector<int>& nums) {
if ([Link]() == [Link]()) {
res.push_back(curr);
return;
}
for (int i = 0; i < [Link](); i++) {
if (used[i]) continue;
used[i] = true;
curr.push_back(nums[i]);
backtrack(res, curr, used, nums);
curr.pop_back();
used[i] = false;
}
}
7. Dynamic Programming (DP)
Application: Solves optimization problems by breaking them into subproblems, caching results.
Code Example:
int fib(int n) {
if (n <= 1) return n;
vector<int> dp(n+1);
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; ++i)
dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}
8. Bit Manipulation
Application: Efficient computations on binary representations, like subsets or flags.
Code Example:
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
9. Prefix Sum
Application: Answer range sum queries efficiently.
Code Example:
vector<int> prefixSum(vector<int>& nums) {
vector<int> pre([Link]());
pre[0] = nums[0];
for (int i = 1; i < [Link](); i++)
pre[i] = pre[i-1] + nums[i];
return pre;
}
10. Union-Find (Disjoint Set Union - DSU)
Application: Detect cycles, connected components in graphs.
Code Example:
vector<int> parent;
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void unite(int x, int y) {
parent[find(x)] = find(y);
}
11. Topological Sort
Application: Order tasks with dependencies (DAG).
Code Example:
vector<int> topoSort(int V, vector<vector<int>>& adj) {
vector<int> indegree(V, 0);
for (auto& list : adj)
for (int v : list) indegree[v]++;
queue<int> q;
for (int i = 0; i < V; ++i)
if (indegree[i] == 0) [Link](i);
vector<int> order;
while (![Link]()) {
int u = [Link](); [Link]();
order.push_back(u);
for (int v : adj[u]) {
if (--indegree[v] == 0) [Link](v);
}
}
return order;
}
12. Trie (Prefix Tree)
Application: String matching, autocomplete.
Code Example:
struct TrieNode {
TrieNode* children[26] = {};
bool isEnd = false;
};
void insert(TrieNode* root, string word) {
for (char c : word) {
if (!root->children[c - 'a'])
root->children[c - 'a'] = new TrieNode();
root = root->children[c - 'a'];
}
root->isEnd = true;
}
13. Graph BFS
Application: Shortest paths, level traversal in unweighted graphs.
Code Example:
void bfs(int start, vector<vector<int>>& adj, vector<bool>& visited) {
queue<int> q;
[Link](start);
visited[start] = true;
while (![Link]()) {
int node = [Link](); [Link]();
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
[Link](neighbor);
}
}
}
}
14. Graph DFS
Application: Cycle detection, connected components, pathfinding.
Code Example:
void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited) {
visited[node] = true;
for (int neighbor : adj[node]) {
if (!visited[neighbor]) dfs(neighbor, adj, visited);
}
}
15. Segment Tree
Application: Range queries and updates efficiently.
Code Example:
vector<int> tree;
void build(vector<int>& nums, int node, int start, int end) {
if (start == end) tree[node] = nums[start];
else {
int mid = (start + end) / 2;
build(nums, 2*node, start, mid);
build(nums, 2*node+1, mid+1, end);
tree[node] = tree[2*node] + tree[2*node+1];
}
}
16. Monotonic Stack
Application: Next greater/smaller element problems.
Code Example:
vector<int> nextGreater(vector<int>& nums) {
vector<int> res([Link](), -1);
stack<int> st;
for (int i = 0; i < [Link](); i++) {
while (![Link]() && nums[i] > nums[[Link]()]) {
res[[Link]()] = nums[i];
[Link]();
}
[Link](i);
}
return res;
}
17. Sweep Line
Application: Interval-related problems, like meeting rooms or skyline.
Code Example:
int minMeetingRooms(vector<vector<int>>& intervals) {
vector<int> start, end;
for (auto& i : intervals) {
start.push_back(i[0]);
end.push_back(i[1]);
}
sort([Link](), [Link]());
sort([Link](), [Link]());
int rooms = 0, endPtr = 0;
for (int i = 0; i < [Link](); i++) {
if (start[i] < end[endPtr]) rooms++;
else endPtr++;
}
return rooms;
}
18. Line Sweeping with Events
Application: Overlapping intervals, maximum concurrent events.
Code Example:
int maxEvents(vector<vector<int>>& events) {
vector<pair<int, int>> points;
for (auto& e : events) {
points.emplace_back(e[0], 1);
points.emplace_back(e[1], -1);
}
sort([Link](), [Link]());
int count = 0, res = 0;
for (auto& [_, type] : points) {
count += type;
res = max(res, count);
}
return res;
}