DSA Patterns Cheat Sheet
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!)
Full DSA Patterns documentation