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.
Top comments (0)