20 Essential Problem-Solving Patterns in C++

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.

Blog

20 Essential Problem-Solving Patterns in C++

Habibur Rahman Shihab

Join Our Newsletter. No Spam, Only the good stuff.

Related