This content originally appeared on DEV Community and was authored by Habibur Rahman Shihab
Data Structures and Algorithms (DSA) are crucial for efficient problem-solving. Here are 20 key patterns, with use cases and examples, to help tackle real-world problems. This guide includes concise C++ examples to demonstrate each pattern in action.
1. Sliding Window Pattern
Efficiently solve problems involving subarrays in a linear array by sliding a window across the array.
Use Case: Find the maximum sum subarray of size k.
Example: Find the maximum sum of any contiguous subarray of size k.
int maxSumSubarray(vector<int>& arr, int k) {
int maxSum = 0, windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += arr[i];
}
maxSum = windowSum;
for (int i = k; i < arr.size(); i++) {
windowSum += arr[i] - arr[i - k];
maxSum = max(maxSum, windowSum);
}
return maxSum;
}
2. Two Pointer Pattern
Two pointers work towards a solution by converging from different ends of an array.
Use Case: Find pairs in a sorted array.
Example: Find two numbers that sum up to a target.
vector<int> twoSum(vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) return {left, right};
else if (sum < target) left++;
else right--;
}
return {};
}
3. Fast & Slow Pointers Pattern
Move two pointers at different speeds to detect cycles in linked lists or arrays.
Use Case: Detect a cycle in a linked list.
Example: Find if a linked list has a cycle.
bool hasCycle(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
4. Merge Intervals Pattern
Merge overlapping intervals in an array of intervals.
Use Case: Merge intervals in a list.
Example: Merge overlapping intervals in a list of meeting times.
vector<vector<int>> mergeIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
merged.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
if (merged.back()[1] >= intervals[i][0]) {
merged.back()[1] = max(merged.back()[1], intervals[i][1]);
} else {
merged.push_back(intervals[i]);
}
}
return merged;
}
5. Cyclic Sort Pattern
Sort a cyclically rotated array or group of elements.
Use Case: Sort an array of 1 to n numbers.
Example: Find the missing number in an array of n numbers.
int missingNumber(vector<int>& arr) {
int i = 0;
while (i < arr.size()) {
if (arr[i] != i + 1 && arr[i] <= arr.size()) {
swap(arr[i], arr[arr[i] - 1]);
} else {
i++;
}
}
for (int i = 0; i < arr.size(); i++) {
if (arr[i] != i + 1) return i + 1;
}
return -1;
}
6. In-place Reversal of Linked List Pattern
Reverse parts of a linked list in-place.
Use Case: Reverse a sub-list in a linked list.
Example: Reverse a part of the list between positions m and n.
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (!head) return nullptr;
ListNode *prev = nullptr, *current = head;
while (m > 1) {
prev = current;
current = current->next;
m--; n--;
}
ListNode *connection = prev, *tail = current;
while (n > 0) {
ListNode *next = current->next;
current->next = prev;
prev = current;
current = next;
n--;
}
if (connection) connection->next = prev;
else head = prev;
tail->next = current;
return head;
}
7. Tree BFS Pattern
Traverse a tree level by level using BFS.
Use Case: Traverse a binary tree.
Example: Perform level-order traversal on a binary tree.
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if (!root) return result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
vector<int> currentLevel;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
currentLevel.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(currentLevel);
}
return result;
}
8. Tree DFS Pattern
Traverse a tree using Depth First Search.
Use Case: Explore all nodes in a tree.
Example: Perform pre-order traversal of a binary tree.
void preorder(TreeNode* root, vector<int>& result) {
if (!root) return;
result.push_back(root->val);
preorder(root->left, result);
preorder(root->right, result);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
preorder(root, result);
return result;
}
9. Binary Search Pattern
Efficiently search for elements in sorted arrays using binary search.
Use Case: Search in a sorted array.
Example: Find the index of a target value in a sorted array.
int binarySearch(vector<int>& arr, int target) {
int left = 0, right = arr.size() - 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;
}
10. Backtracking Pattern
Explore all potential solutions using recursive backtracking.
Use Case: Solve constraint satisfaction problems.
Example: Solve the N-Queens problem.
bool isSafe(vector<string>& board, int row, int col, int n) {
for (int i = 0; i < col; i++)
if (board[row][i] == 'Q') return false;
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j] == 'Q') return false;
for (int i = row, j = col; i < n && j >= 0; i++, j--)
if (board[i][j] == 'Q') return false;
return true;
}
void solveNQueens(int col, vector<string>& board, vector<vector<string>>& solutions, int n) {
if (col == n) {
solutions.push_back(board);
return;
}
for (int i = 0; i < n; i++) {
if (isSafe(board, i, col, n)) {
board[i][col] = 'Q';
solveNQueens(col + 1, board, solutions, n);
board[i][col] = '.';
}
}
}
11. Topological Sort Pattern
Sort nodes in a directed graph using topological ordering.
Use Case: Resolve task dependency problems.
Example: Find the order in which tasks should be completed given dependencies.
vector<int> topologicalSort(int vertices, vector<vector<int>>& edges) {
vector<int> sortedOrder;
if (vertices <= 0) return sortedOrder;
unordered_map<int, int> inDegree;
unordered_map<int, vector<int>> graph;
for (int i = 0; i < vertices; i++) {
inDegree[i] = 0;
graph[i] = vector<int>();
}
for (auto& edge : edges) {
int parent = edge[0], child = edge[1];
graph[parent].push_back(child);
inDegree[child]++;
}
queue<int> sources;
for (auto& entry : inDegree) {
if (entry.second == 0) sources.push(entry.first);
}
while (!sources.empty()) {
int vertex = sources.front();
sources.pop();
sortedOrder.push_back(vertex);
for (int child : graph[vertex]) {
inDegree[child]--;
if (inDegree[child] == 0) sources.push(child);
}
}
if (sortedOrder.size() != vertices) return {}; // cycle detected
return sortedOrder;
}
12. Trie Pattern
Use a trie (prefix tree) to solve problems involving word searches.
Use Case: Efficiently store and search strings.
Example: Implement a word search using a Trie.
class TrieNode {
public:
TrieNode* children[26];
bool isEndOfWord;
TrieNode() {
for (int i = 0; i < 26; i++) children[i] = nullptr;
isEndOfWord = false;
}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children[c - 'a']) {
node->children[c - 'a'] = new TrieNode();
}
node = node->children[c - 'a'];
}
node->isEndOfWord = true;
}
bool search(string word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children[c - 'a']) return false;
node = node->children[c - 'a'];
}
return node->isEndOfWord;
}
};
13. Greedy Pattern
Make the most optimal choice at each step to ensure the best overall solution.
Use Case: Solve optimization problems.
Example: Find the minimum number of coins required to make a specific amount.
int minCoins(vector<int>& coins, int amount) {
sort(coins.rbegin(), coins.rend());
int count = 0;
for (int coin : coins) {
if (amount == 0) break;
count += amount / coin;
amount %= coin;
}
return (amount == 0) ? count : -1;
}
14. Knapsack (Dynamic Programming) Pattern
Solve problems involving choices using dynamic programming (DP).
Use Case: Maximize value within weight constraints.
Example: Solve the 0/1 Knapsack problem.
int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
int n = weights.size();
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];
}
15. Subsets Pattern
Solve problems by generating all subsets of a given set.
Use Case: Solve combination or subset problems.
Example: Generate all subsets of a set of numbers.
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result = {{}};
for (int num : nums) {
int n = result.size();
for (int i = 0; i < n; i++) {
vector<int> subset = result[i];
subset.push_back(num);
result.push_back(subset);
}
}
return result;
}
16. Bit Manipulation Pattern
Efficiently solve problems involving bitwise operations.
Use Case: Solve problems using bitwise operators.
Example: Find the single number in an array where every element appears twice except for one.
int singleNumber(vector<int>& nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
17. Union-Find Pattern
Efficiently solve problems involving connected components or dynamic connectivity.
Use Case: Solve problems involving finding connected components in graphs.
Example: Find if there is a cycle in an undirected graph.
class UnionFind {
public:
vector<int> parent, rank;
UnionFind(int n) : parent(n), rank(n, 0) {
for (int i = 0; i < n; ++i) parent[i] = i;
}
int find(int p) {
if (parent[p] != p) parent[p] = find(parent[p]);
return parent[p];
}
bool unionSets(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return false;
if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
else if (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
else {
parent[rootQ] = rootP;
rank[rootP]++;
}
return true;
}
};
18. Monotonic Stack Pattern
Use a stack to maintain a sequence of elements that are either increasing or decreasing to solve certain problems.
Use Case: Solve problems involving the next greater/smaller element.
Example: Find the next greater element for each element in an array.
vector<int> nextGreaterElement(vector<int>& nums) {
vector<int> result(nums.size(), -1);
stack<int> s;
for (int i = 0; i < nums.size(); i++) {
while (!s.empty() && nums[s.top()] < nums[i]) {
result[s.top()] = nums[i];
s.pop();
}
s.push(i);
}
return result;
}
19. Dynamic Programming Pattern
Solve problems by breaking them down into overlapping subproblems and storing the results of subproblems to avoid redundant computations.
Use Case: Solve problems involving optimal substructure and overlapping subproblems.
Example: Solve the longest increasing subsequence problem.
int longestIncreasingSubsequence(vector<int>& nums) {
if (nums.empty()) return 0;
vector<int> dp(nums.size(), 1);
int maxLength = 1;
for (int i = 1; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxLength = max(maxLength, dp[i]);
}
return maxLength;
}
20. Segment Tree Pattern
Efficiently solve range query problems by using a segment tree data structure.
Use Case: Solve problems involving range queries and updates on an array.
Example: Range sum query and update on an array.
class SegmentTree {
private:
vector<int> tree;
int n;
void buildTree(vector<int>& nums, int start, int end, int node) {
if (start == end) {
tree[node] = nums[start];
return;
}
int mid = start + (end - start) / 2;
buildTree(nums, start, mid, 2 * node + 1);
buildTree(nums, mid + 1, end, 2 * node + 2);
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
void updateTree(int start, int end, int idx, int val, int node) {
if (start == end) {
tree[node] = val;
return;
}
int mid = start + (end - start) / 2;
if (idx <= mid) updateTree(start, mid, idx, val, 2 * node + 1);
else updateTree(mid + 1, end, idx, val, 2 * node + 2);
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
int rangeSum(int start, int end, int l, int r, int node) {
if (start > r || end < l) return 0;
if (start >= l && end <= r) return tree[node];
int mid = start + (end - start) / 2;
return rangeSum(start, mid, l, r, 2 * node + 1) + rangeSum(mid + 1, end, l, r, 2 * node + 2);
}
public:
SegmentTree(vector<int>& nums) {
n = nums.size();
tree.resize(4 * n);
buildTree(nums, 0, n - 1, 0);
}
void update(int idx, int val) {
updateTree(0, n - 1, idx, val, 0);
}
int sumRange(int l, int r) {
return rangeSum(0, n - 1, l, r, 0);
}
};
These 20 problem-solving patterns are crucial for mastering DSA. Each pattern can be applied to a wide range of real-world problems, providing an efficient path to optimal solutions.
This content originally appeared on DEV Community and was authored by Habibur Rahman Shihab
Habibur Rahman Shihab | Sciencx (2024-10-25T06:02:36+00:00) 20 Essential Problem-Solving Patterns in C++. Retrieved from https://www.scien.cx/2024/10/25/20-essential-problem-solving-patterns-in-c/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.