37 DSA patterns that solve most interview problems
Most coding interview questions are a known pattern in disguise. Each guide below explains when the pattern applies, the template that solves it, the mistakes to avoid, and the problems to practise it on.
Learn a pattern here, then watch it run step by step in the animated problems, or revise it fast with the 2-minute revision videos.
Two Pointers 3
Two Pointers — Opposite EndsPlace L at index 0 and R at index n−1. Compare and move one pointer inward each step based on the result — they converge until they meet.
Same Direction Two PointersSlow pointer writes valid values; fast pointer scans ahead. Both move left to right — fast races forward while slow only advances when a valid element is found.
Sort + Fix One + Two PointersSort the array first. Fix one element (outer loop), then use opposite-end two pointers on the remaining suffix to find pairs that complete the target. O(n²) total.
Sliding Window 2
Dynamic Sliding WindowWindow size is not fixed. Expand right to grow; when constraint violated, shrink from left until valid again. Track the best window seen.
Fixed Sliding WindowWindow of exactly k elements slides one position at a time. Build once in O(k), then add right element − remove left element in O(1) per step.
Prefix Sum 1
Kadane's Algorithm 1
Hashing 1
Binary Search 2
Classic Binary SearchHalve the search space each step. Maintain lo & hi boundaries — compute mid, compare nums[mid] to target, discard the half that cannot contain the answer. Repeat until found or lo > hi.
Binary Search on AnswerDon't search the array — search the answer range. Set lo = min possible, hi = max possible, binary search for the boundary where isFeasible(mid) flips from false to true (or vice versa).
Stack 3
Monotonic Decreasing StackMaintain a stack of indices in decreasing value order. When nums[i] > nums[stack.top()], the current index i is the Next Greater Element for every index we pop. Each element is pushed/popped at most once — O(n) total.
Monotonic Increasing StackMaintain indices in increasing height order. When height[i] < height[stack.top()], pop and compute area = height × width (width = distance to previous smaller bar). A sentinel 0 at end flushes all remaining bars. O(n) — each bar pushed/popped once.
Simple StackPush elements onto the stack; when a closing bracket arrives, pop the top and verify it matches. LIFO guarantees correct nesting order. If the stack is empty on a close or non-empty after scan — invalid.
Linked List 3
Fast / Slow Pointers — Floyd's Cycle DetectionTwo pointers at different speeds — slow moves 1 step, fast moves 2 steps — to detect cycles, find midpoints, and locate cycle entry nodes in O(1) space.
Two-Pointer Merge / Remove NthFast pointer races ahead by n+1 steps to create an exact offset gap; then both move together until fast hits null — slow lands perfectly one step before the target node to snip it out. Merge pattern interleaves two sorted chains into one with a dummy-head sentinel.
In-Place List ReversalWalk a linked list with three pointers — save the next node, flip the current node's pointer backward, then slide the window forward — reversing the chain in O(n) time with O(1) extra space.
Heap 3
K-Way Merge (Min-Heap)Push the head of each sorted list into a min-heap. Always poll() the global minimum → append to result → push its next node into the heap. Repeat until heap is empty.
Top K Elements (Min-Heap)Keep a min-heap of exactly K elements. For each new number: offer(num), if size > K then poll() (drop smallest). After all elements, peek() = Kth largest.
Two Heaps (Running Median)Keep a LO max-heap (lower half) and HI min-heap (upper half), always balanced within 1. After each insert, lo.peek() and hi.peek() give the median in O(1).
Trees 4
BFS Level Order TraversalUse a queue to visit nodes level by level, left to right. Snapshot size = q.size() at the start of each iteration to process exactly one level at a time. The queue naturally enforces FIFO level ordering.
BST OperationsExploit the BST invariant (left < root < right) to eliminate half the tree per step. Validate by propagating bounds down. Search by comparing and going left or right. Build balanced BST by always picking the array midpoint as root.
DFS Tree TraversalOne recursive pattern, three visit timings. Change when you call result.add(node.val) — before, between, or after the recursive calls — to get pre-, in-, or post-order traversal.
Tree Path ProblemsTwo complementary patterns: backtracking DFS tracks the current path from root to leaf, adding/removing nodes as you descend and backtrack. Max-gain DFS uses bottom-up return values to evaluate paths passing through any node — the global answer is updated at each step while the return value propagates only the best single branch upward.
Breadth-First Search 2
Multi-Source BFSEnqueue ALL source nodes before the BFS loop begins. The infection wavefront then expands from every source simultaneously — as if they all started at time = 0. Each node records the distance to its nearest source. One BFS pass, zero re-runs.
Standard BFSEnqueue the root, mark it visited. Each outer loop iteration drains one full level — poll every node in the current batch, enqueue their unvisited children. First time a node is reached = shortest distance. Expand like ripples in water, level by level.
Graphs 5
Bellman-Ford / K-Stop | Graph PatternsRelax all edges V−1 times. Supports negative weights. K-stop variant: do exactly K relaxation rounds.
Dijkstra's Shortest Path | Graph PatternsMin-heap greedy — always process the closest unvisited node first. Non-negative weights only.
Prim's MST | Graph PatternsGrow MST greedily — always add the cheapest edge connecting the tree to an unvisited node
Topological Sort (Kahn's BFS) | Graph PatternsProcess nodes with in-degree 0 first — linear ordering of a DAG
Union-Find (DSU) | Graph PatternsPath compression + union by rank — near-O(1) per operation for connectivity queries
Backtracking 3
Combinations + PruningSort candidates first, then at each step: if candidates[i] > remain, break (not continue) — no subsequent elements can work either. Pruning reduces O(2ⁿ) to practical time.
PermutationsUse a boolean[] used array to mark which elements are already in the current permutation. At each recursive call, try every unused element. When curr.size() == n, a complete permutation is found.
Subsets / Power SetAt each element, make two choices: include it in the current subset or skip it. Collect the current path at every node of the recursion tree — no leaf-only collection needed.
Greedy 2
Sort + Greedy / Interval SchedulingSort the events, then greedily scan with a pointer or counter. Sorting eliminates the need to look back — each decision only depends on the current event and the best previous outcome.
Greedy Reach / Jump GameTrack maxReach — the farthest index reachable so far. For Jump Game II, also track currEnd (boundary of current jump) and increment jumps each time i crosses it. One pass, O(n).