Leetcode Patterns

1. Sliding Window Pattern

Used when you need to inspect subarrays or substrings that involve consecutive elements.

Problem: Find the maximum sum of a subarray of size 'k'

class Solution {
public:
    int maxSumSubarray(vector<int>& nums, int k) {
        int maxSum = 0, windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }
        maxSum = windowSum;

        for (int i = k; i < nums.size(); i++) {
            windowSum += nums[i] - nums[i - k];
            maxSum = max(maxSum, windowSum);
        }
        return maxSum;
    }
};

2. Two Pointers Pattern

Efficient for problems involving pairs of elements or comparisons within an array.

Problem: Find two numbers in a sorted array that add up to a target sum.

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return {left + 1, right + 1};
            } else if (sum < target) {
                left++;  // move the left pointer to increase the sum
            } else {
                right--;  // move the right pointer to decrease the sum
            }
        }
        return {};
    }
};

3. Fast and Slow Pointers (Tortoise and Hare)

Used to detect cycles in linked lists or arrays.

Problem: Detect if a linked list has a cycle.

class Solution {
public:
    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; // cycle detected
            }
        }
        return false;
    }
};

4. Merge Intervals Pattern

Used when working with overlapping intervals, such as scheduling.

Problem: Merge overlapping intervals.

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());  // sort by start time
        vector<vector<int>> merged;

        for (const auto& interval : intervals) {
            if (merged.empty() || merged.back()[1] < interval[0]) {
                merged.push_back(interval);  // no overlap, add the interval
            } else {
                merged.back()[1] = max(merged.back()[1], interval[1]);  // merge intervals
            }
        }
        return merged;
    }
};

5. Binary Search Pattern

Ideal when searching for a target in a sorted array or a monotonic function.

Problem: Find the first position of a target in a sorted array.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 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;
    }
};

6. Backtracking Pattern

Used for problems that involve exploring all possible solutions, such as permutations, combinations, or subsets.

Problem: Generate all subsets of a set.

class Solution {
public:
    void backtrack(vector<int>& nums, vector<vector<int>>& result, vector<int>& subset, int index) {
        result.push_back(subset);  // add current subset to the result
        for (int i = index; i < nums.size(); i++) {
            subset.push_back(nums[i]);  // include nums[i]
            backtrack(nums, result, subset, i + 1);  // recursively explore further
            subset.pop_back();  // exclude nums[i], backtrack to previous state
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> subset;
        backtrack(nums, result, subset, 0);
        return result;
    }
};

7. Dynamic Programming (DP) Pattern

Used when a problem can be broken down into overlapping subproblems, with optimal substructure.

Problem: Solve the 0/1 Knapsack problem.

class Solution {
public:
    int knapsack(vector<int>& weights, vector<int>& values, int W) {
        int n = weights.size();
        vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= W; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        return dp[n][W];
    }
};

8. Greedy Pattern

Used when making local optimal choices at each step leads to a global optimal solution.

Problem: Find the minimum number of coins to make up a target amount.

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        sort(coins.rbegin(), coins.rend());  // sort coins in descending order
        int count = 0;
        for (int coin : coins) {
            if (amount >= coin) {
                count += amount / coin;  // use as many large coins as possible
                amount %= coin;
            }
        }
        return amount == 0 ? count : -1;  // return -1 if the amount cannot be made
    }
};

9. Topological Sort (Graph Traversal)

Used for problems involving dependency resolution, such as scheduling tasks.

Problem: Find the order of courses to take given prerequisites.

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> indegree(numCourses, 0);
        vector<vector<int>> graph(numCourses);

        for (const auto& pre : prerequisites) {
            graph[pre[1]].push_back(pre[0]);
            indegree[pre[0]]++;
        }

        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) q.push(i);  // start with courses having no prerequisites
        }

        vector<int> order;
        while (!q.empty()) {
            int course = q.front();
            q.pop();
            order.push_back(course);
            for (int next : graph[course]) {
                if (--indegree[next] == 0) {
                    q.push(next);
                }
            }
        }

        return order.size() == numCourses ? order : vector<int>();  // return an empty array if a cycle exists
    }
};

10. Union-Find (Disjoint Set Union) Pattern

Used for problems involving connected components in graphs.

Problem: Detect if a graph contains a cycle.

class Solution {
public:
    int findParent(vector<int>& parent, int node) {
        if (parent[node] != node) {
            parent[node] = findParent(parent, parent[node]);  // path compression
        }
        return parent[node];
    }

    bool unionNodes(vector<int>& parent, vector<int>& rank, int u, int v) {
        int rootU = findParent(parent, u);
        int rootV = findParent(parent, v);
        if (rootU == rootV) return false;  // cycle detected

        if (rank[rootU] > rank[rootV]) {
            parent[rootV] = rootU;
        } else if (rank[rootU] < rank[rootV]) {
            parent[rootU] = rootV;
        } else {
            parent[rootV] = rootU;
            rank[rootU]++;
        }
        return true;
    }

    bool hasCycle(int n, vector<vector<int>>& edges) {
        vector<int> parent(n), rank(n, 0);
        iota(parent.begin(), parent.end(), 0);  // initialize each node as its own parent

        for (const auto& edge : edges) {
            if (!unionNodes(parent, rank, edge[0], edge[1])) {
                return true;  // cycle found
            }
        }
        return false;  // no cycle
    }
};

11. Cyclic Sort Pattern

When to Use: When you're dealing with a range of numbers from 1 to n or 0 to n, and you're asked to rearrange or find missing/duplicate numbers.

Code Idea:

vector<int> cyclicSort(vector<int>& nums) {
    int i = 0;
    while (i < nums.size()) {
        int correctIndex = nums[i] - 1;
        if (nums[i] != nums[correctIndex]) {
            swap(nums[i], nums[correctIndex]);
        } else {
            i++;
        }
    }
    return nums;
}

Problems:

Find the Missing Number
Find All Duplicates in an Array
Set Mismatch

12. BFS/DFS Pattern

When to Use:

When you're working with graphs or trees (or matrix as a grid).

Data structures and Algorithms

Use DFS for deep traversal.
Use BFS for shortest path in unweighted graphs.

DFS Code (Recursive):

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor])
            dfs(neighbor, graph, visited);
    }
}

BFS Code:

void bfs(int start, vector<vector<int>>& graph) {
    queue<int> q;
    vector<bool> visited(graph.size(), false);
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front(); q.pop();
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

Problems:

Clone Graph
Number of Provinces
Word Ladder

13. Island (Matrix traversal) Pattern

When to Use: When you are given a 2D grid and need to count or explore connected components.

DFS in Matrix:

void dfs(vector<vector<char>>& grid, int r, int c) {
    if (r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size() || grid[r][c] == '0')
        return;

    grid[r][c] = '0'; // mark visited

    dfs(grid, r+1, c);
    dfs(grid, r-1, c);
    dfs(grid, r, c+1);
    dfs(grid, r, c-1);
}

Problems:

Number of Islands
Surrounded Regions
Flood Fill

14. In-place Reversal of Linked List

When to Use: To reverse a linked list or part of it, especially in O(1) space.

Code:

ListNode* reverseList(ListNode* head) {
    ListNode* prev = NULL;
    while (head) {
        ListNode* nextNode = head->next;
        head->next = prev;
        prev = head;
        head = nextNode;
    }
    return prev;
}

Problems:

Reverse Linked List
Reverse Nodes in k-Group
Palindrome Linked List

15. Two Heaps Pattern

When to Use: Used in problems where you need to find median, or maintain order statistics dynamically.

DFS in Matrix:

priority_queue<int> maxHeap; // for left half
priority_queue<int, vector<int>, greater<int>> minHeap; // for right half

void addNum(int num) {
    if (maxHeap.empty() || num <= maxHeap.top()) maxHeap.push(num);
    else minHeap.push(num);

    // balance
    if (maxHeap.size() > minHeap.size() + 1) {
        minHeap.push(maxHeap.top()); maxHeap.pop();
    } else if (minHeap.size() > maxHeap.size()) {
        maxHeap.push(minHeap.top()); minHeap.pop();
    }
}

Problems:

Median of Data Stream
Sliding Window Median

16. Modified Binary Search Pattern

When to Use: When you do binary search not on the values, but on a condition, index, or to solve min/max problems.

Code:

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 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;
}

Modified use case: Find smallest number ≥ target.

Problems:

Search in Rotated Array
Peak Element
Koko Eating Bananas

17. Top K Elements

When you need to find k largest/smallest elements or frequent elements.

Code:

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int num : nums) freq[num]++;

    priority_queue<pair<int, int>> maxHeap;
    for (auto& [num, count] : freq)
        maxHeap.push({count, num});

    vector<int> res;
    while (k--) {
        res.push_back(maxHeap.top().second);
        maxHeap.pop();
    }
    return res;
}

Problems:

Top K Frequent Elements
K Closest Numbers
Top K Frequent Words

18. 0/1 Knapsack Pattern

Used in DP when choosing to either include or exclude an item.

Code:

int knapsack(vector<int>& weight, vector<int>& value, int W) {
    int n = weight.size();
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));

    for (int i=1; i<=n; i++) {
        for (int w=0; w<=W; w++) {
            if (weight[i-1] <= w)
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1]);
            else
                dp[i][w] = dp[i-1][w];
        }
    }
    return dp[n][W];
}

Problems:

Subset Sum
Partition Equal Subset Sum
Target Sum

19. Bitwise XOR

When you need to cancel out duplicate values or perform toggling.

Code:

int findSingleNumber(vector<int>& nums) {
    int res = 0;
    for (int num : nums) res ^= num;
    return res;
}

Problems:

Single Number
Find Missing Number
XOR of All Subsets

20. K-way Merge

When merging k sorted arrays or lists.

Code:

struct Compare {
    bool operator()(pair<int, pair<int, int>>& a, pair<int, pair<int, int>>& b) {
        return a.first > b.first;
    }
};

vector<int> mergeKSortedLists(vector<vector<int>>& lists) {
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, Compare> pq;
    vector<int> indices(lists.size(), 0), result;

    for (int i = 0; i < lists.size(); i++) {
        if (!lists[i].empty())
            pq.push({lists[i][0], {i, 0}});
    }

    while (!pq.empty()) {
        auto [val, pos] = pq.top(); pq.pop();
        result.push_back(val);
        int i = pos.first, j = pos.second + 1;
        if (j < lists[i].size()) pq.push({lists[i][j], {i, j}});
    }

    return result;
}

Problems:

Merge K Sorted Lists
Smallest Range Covering Elements from K Lists

21. Monotonic Stack

Used to find next/previous greater/smaller elements

Code:

vector<int> nextGreater(vector<int>& nums) {
    vector<int> res(nums.size(), -1);
    stack<int> st;

    for (int i = 0; i < nums.size(); i++) {
        while (!st.empty() && nums[i] > nums[st.top()]) {
            res[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }

    return res;
}

Problems:

Daily Temperatures
Largest Rectangle in Histogram
Next Greater Element

22. Multi-threaded

When optimizing tasks with parallelism or for handling concurrent operations (not core DSA but used in system design/interviews).

Example Idea (Java):

class MyRunnable implements Runnable {
    public void run() {
        System.out.println("Thread is running");
    }
}

Problems:

Multi-threaded FizzBuzz
Building H2O
Print in Order

23. Kth Smallest/Largest Element

Asked directly to find k-th smallest/largest, can use heaps or quickselect.

Heap Code:

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap;

    for (int num : nums) {
        minHeap.push(num);
        if (minHeap.size() > k) minHeap.pop();
    }
    return minHeap.top();
}

Problems:

Kth Smallest Element in BST
Kth Largest Element in Array
Find K Closest Elements