Getting everything ready for you…

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

0s

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