Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

DSA Patterns Documentation

The 15 coding-interview patterns — how to spot each one, a C++ template and the classic problems to practise.

Most coding interview problems are variations of about 15 patterns. Learn to spot the pattern from the problem statement and you already know the shape of the solution. Each pattern below has when to use it, a C++ template and classic problems to practise in Practice.

1. How to Recognise the Pattern

The problem says… Try
sorted array, find a pair / triplet Two pointers
contiguous subarray / substring, "longest/shortest with condition" Sliding window
subarray sum equals k, range sums Prefix sum + hash map
sorted / monotonic, "minimum possible maximum", "first true" Binary search (on index or on answer)
linked list cycle, middle node Fast & slow pointers
intervals, meetings, merge overlapping Sort + merge intervals
next greater / smaller element, histogram Monotonic stack
top K, K-th largest, merge K sorted Heap
tree paths, depth, subtree answers DFS (recursion)
level by level, shortest steps in unweighted graph/grid BFS
dependencies, ordering of tasks Topological sort
connected groups, "are they connected?", cycle in undirected graph Union–Find
all combinations / permutations / subsets Backtracking
count ways, min/max cost, overlapping subproblems Dynamic programming
locally best choice works (prove it!) Greedy
prefix / word search / autocomplete Trie
XOR, single number, subsets as masks Bit manipulation

2. Two Pointers

When: sorted arrays, pairs/triplets, reversing, removing duplicates in place, palindromes.

// pair with target sum in a sorted array
int l = 0, r = n - 1;
while (l < r) {
    int s = a[l] + a[r];
    if (s == target) return {l, r};
    if (s < target) l++; else r--;
}

Complexity: O(n) time, O(1) space. Practise: Two Sum II, 3Sum, Container With Most Water, Remove Duplicates from Sorted Array, Valid Palindrome, Trapping Rain Water.

3. Sliding Window

When: longest/shortest contiguous subarray or substring meeting a condition.

// longest substring without repeating characters (variable window)
unordered_map<char, int> cnt;
int best = 0;
for (int l = 0, r = 0; r < s.size(); r++) {
    cnt[s[r]]++;
    while (cnt[s[r]] > 1) cnt[s[l++]]--;     // shrink until valid
    best = max(best, r - l + 1);
}

Fixed window of size k: add a[r], remove a[r - k] once r >= k. Complexity: O(n). Practise: Max Sum Subarray of Size K, Longest Substring Without Repeating Characters, Minimum Window Substring, Longest Repeating Character Replacement, Permutation in String. Notes: Sliding Window.

4. Prefix Sum & Hashing

When: range sums, "subarray sum equals k", counting pairs, frequency questions.

// number of subarrays with sum k (works with negatives)
unordered_map<long long, int> seen{{0, 1}};
long long sum = 0; int count = 0;
for (int x : a) {
    sum += x;
    if (seen.count(sum - k)) count += seen[sum - k];
    seen[sum]++;
}

Complexity: O(n) time, O(n) space. Practise: Two Sum, Subarray Sum Equals K, Contiguous Array, Longest Consecutive Sequence, Group Anagrams, Range Sum Query.

5. Binary Search (and on the Answer)

When: sorted data, or a monotonic yes/no question ("can we do it with capacity X?").

// first index where a[i] >= x (lower_bound)
int lo = 0, hi = n;              // answer in [lo, hi]
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] >= x) hi = mid; else lo = mid + 1;
}

// binary search on the answer: smallest capacity that works
long long lo = 1, hi = 1e18;
while (lo < hi) {
    long long mid = lo + (hi - lo) / 2;
    if (canDo(mid)) hi = mid; else lo = mid + 1;
}

Complexity: O(log n) × cost of the check. Practise: Search in Rotated Sorted Array, Find Peak Element, Koko Eating Bananas, Capacity to Ship Packages, Aggressive Cows, Median of Two Sorted Arrays.

6. Fast & Slow Pointers

When: linked list cycle, middle node, cycle start, "happy number".

ListNode *slow = head, *fast = head;
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return true;    // cycle
}
return false;                          // slow is the middle when the loop ends

Practise: Linked List Cycle I & II, Middle of the Linked List, Palindrome Linked List, Find the Duplicate Number, Happy Number.

7. Merge Intervals

When: overlapping ranges, meeting rooms, insert interval.

sort(iv.begin(), iv.end());
vector<vector<int>> out;
for (auto &cur : iv) {
    if (out.empty() || out.back()[1] < cur[0]) out.push_back(cur);
    else out.back()[1] = max(out.back()[1], cur[1]);
}

Complexity: O(n log n). Practise: Merge Intervals, Insert Interval, Non-overlapping Intervals, Meeting Rooms II (sort + min-heap of end times).

8. Monotonic Stack

When: next/previous greater or smaller element, spans, largest rectangle.

// next greater element to the right
vector<int> ans(n, -1);
stack<int> st;                         // indices, values decreasing
for (int i = 0; i < n; i++) {
    while (!st.empty() && a[st.top()] < a[i]) {
        ans[st.top()] = a[i];
        st.pop();
    }
    st.push(i);
}

Complexity: O(n) — each index is pushed and popped once. Practise: Next Greater Element, Daily Temperatures, Stock Span, Largest Rectangle in Histogram, Sliding Window Maximum (monotonic deque).

9. Heap / Top K

When: K largest/smallest, K-th element, merge K sorted lists, running median.

// k largest elements: keep a min-heap of size k
priority_queue<int, vector<int>, greater<int>> pq;
for (int x : a) {
    pq.push(x);
    if (pq.size() > k) pq.pop();
}
// pq.top() is the k-th largest

Complexity: O(n log k). Practise: Kth Largest Element, Top K Frequent Elements, K Closest Points, Merge K Sorted Lists, Find Median from Data Stream (two heaps), Task Scheduler.

10. Tree DFS & BFS

DFS — return information up from subtrees:

int height(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(height(root->left), height(root->right));
}

BFS — level order:

queue<TreeNode*> q; q.push(root);
while (!q.empty()) {
    int sz = q.size();
    for (int i = 0; i < sz; i++) {
        TreeNode* node = q.front(); q.pop();
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

Practise: Max Depth, Diameter, Balanced Tree, Lowest Common Ancestor, Path Sum, Level Order / Zigzag, Right Side View, Validate BST, Serialize/Deserialize.

11. Graph BFS / DFS, Topological Sort & Union–Find

// BFS shortest path in an unweighted graph / grid
vector<int> dist(n, -1); queue<int> q;
dist[src] = 0; q.push(src);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
}
// topological sort (Kahn) — also detects cycles
vector<int> indeg(n), order; queue<int> q;
for (int u = 0; u < n; u++) for (int v : adj[u]) indeg[v]++;
for (int u = 0; u < n; u++) if (!indeg[u]) q.push(u);
while (!q.empty()) {
    int u = q.front(); q.pop(); order.push_back(u);
    for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
}
// order.size() < n → there is a cycle
// union–find with path compression and union by size
vector<int> parent(n), sz(n, 1);
iota(parent.begin(), parent.end(), 0);
function<int(int)> find = [&](int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); };
auto unite = [&](int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return false;
    if (sz[a] < sz[b]) swap(a, b);
    parent[b] = a; sz[a] += sz[b];
    return true;
};

Practise: Number of Islands, Rotting Oranges, Word Ladder, Course Schedule I & II, Clone Graph, Number of Provinces, Redundant Connection, Network Delay Time (Dijkstra). Notes: Graphs — BFS and DFS.

12. Backtracking

When: generate all combinations, permutations, subsets, or search with constraints (N-Queens, Sudoku).

void solve(int start, vector<int>& path) {
    result.push_back(path);                   // record a subset
    for (int i = start; i < n; i++) {
        if (i > start && a[i] == a[i - 1]) continue;   // skip duplicates (array sorted)
        path.push_back(a[i]);                 // choose
        solve(i + 1, path);                   // explore
        path.pop_back();                      // un-choose
    }
}

Practise: Subsets I & II, Permutations, Combination Sum, Palindrome Partitioning, Word Search, N-Queens, Sudoku Solver.

13. Dynamic Programming

When: count the ways / min or max cost, and the same subproblem repeats. Steps: define state → write the recurrence → set base cases → choose order (memoisation top-down or table bottom-up) → optimise space.

// 1-D: climbing stairs / house robber shape
vector<int> dp(n + 1);
dp[0] = 1; dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];

// 2-D: longest common subsequence
vector<vector<int>> L(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        L[i][j] = (s[i-1] == t[j-1]) ? L[i-1][j-1] + 1 : max(L[i-1][j], L[i][j-1]);
Family Examples
1-D Climbing Stairs, House Robber, Decode Ways, Jump Game
Grid Unique Paths, Minimum Path Sum, Dungeon Game
Knapsack 0/1 Knapsack, Partition Equal Subset Sum, Coin Change, Target Sum
Strings LCS, Edit Distance, Longest Palindromic Subsequence, Word Break
LIS Longest Increasing Subsequence, Russian Doll Envelopes
Intervals Matrix Chain Multiplication, Burst Balloons
Stocks Buy and Sell Stock I–IV, with cooldown

Notes: Dynamic Programming.

14. Greedy, Trie & Bit Manipulation

Greedy — sort, then take the locally best choice (prove with an exchange argument):

// activity selection: max non-overlapping intervals
sort(iv.begin(), iv.end(), [](auto& a, auto& b) { return a[1] < b[1]; });
int count = 0, end = INT_MIN;
for (auto& x : iv) if (x[0] >= end) { count++; end = x[1]; }

Practise: Jump Game II, Gas Station, Assign Cookies, Minimum Platforms, Fractional Knapsack.

Trie — prefix search: Implement Trie, Word Search II, Longest Common Prefix, Maximum XOR of Two Numbers. Notes: Trie (Prefix Tree).

Bit manipulation — x & (x - 1) removes the lowest set bit; x & -x isolates it; a ^ a = 0:

int single = 0;
for (int x : a) single ^= x;          // the element that appears once
for (int mask = 0; mask < (1 << n); mask++) { /* every subset */ }

Practise: Single Number, Counting Bits, Power of Two, Subsets (bitmask), Missing Number.

15. Cheat Sheet & References

Spot the pattern

sorted + pair/triplet          → two pointers
contiguous + longest/shortest  → sliding window
subarray sum = k               → prefix sum + hash map
monotonic yes/no               → binary search on answer
next greater/smaller           → monotonic stack
top k / k-th                   → heap of size k
shortest steps, unweighted     → BFS
dependencies                   → topological sort
connectivity                   → union-find
all combinations               → backtracking
count ways / min cost          → dynamic programming

Templates

while (l < r) { /* move l or r */ }                       // two pointers
for (r...) { add(r); while (bad) remove(l++); }           // sliding window
while (lo < hi) { mid; ok(mid) ? hi = mid : lo = mid+1; } // binary search
while (st.size() && a[st.top()] < a[i]) st.pop();         // monotonic stack
if (pq.size() > k) pq.pop();                              // top k
choose; solve(i + 1); unchoose;                           // backtracking
dp[i] = f(dp[i-1], dp[i-2]);                              // dp

Complexities

two pointers / window / prefix / stack: O(n)
sort-based: O(n log n); heap top-k: O(n log k)
BFS/DFS: O(V + E); union-find: ~O(1) per op
subsets: O(2^n); permutations: O(n!)

References