DSA Patterns Master Guide

Most interview problems are variants of a small set of patterns. Your job is not to memorize 500 solutions, but to map a problem to a pattern, recall a small algorithm template, and adapt it. This guide shows you how to identify each pattern, when to use it, the typical steps, common pitfalls, and a focused LeetCode practice set.

---

How to Use This Guide

• Read the identification cues. Train your eyes to spot keywords and shapes.
• Memorize the small algorithm steps. Build the solution skeleton first.
• Practice 3 to 5 problems per pattern with spaced repetition.
• After solving, write a 5 line retrospective: pattern, key decision, complexity, 1 pitfall, 1 variation.

---

Two Pointers

Visual:

head <---- array ----> tail
l ->  .........  <- r
fast/slow for cycle detection

Java template:

int l = 0, r = nums.length - 1;
while (l < r) {
  long sum = (long) nums[l] + nums[r];
  if (sum == target) { /* use/update */ l++; r--; }
  else if (sum < target) l++;
  else r--;
}

• Identify it when:
  • Array or string, sorted or sortable.
  • Need pair, triplet, or partitioning.
  • Move pointers inward or with fast-slow positions.
• Core options: head-tail inward, same direction fast-slow, in-place partitioning.
• Steps template:
  1. Sort if needed.
  2. Initialize left and right or slow and fast.
  3. Move based on comparison, update answer, avoid duplicates.
• Pitfalls: off-by-one, duplicate handling, infinite loops when both pointers fail to move.
• Complexity: O(n) or O(n log n) with sort, O(1) extra space.
• LeetCode set: Reverse String 344; Two Sum II 167; Remove Duplicates from Sorted Array 26; Container With Most Water 11; Trapping Rain Water 42.

Sliding Window

Visual:

[l ........ r]  grow r; while invalid -> shrink l

Java template (variable window):

int l = 0;
Map<Character,Integer> freq = new HashMap<>();
int best = 0;
for (int r = 0; r < s.length(); r++) {
  char c = s.charAt(r);
  freq.put(c, freq.getOrDefault(c, 0) + 1);
  while (!isValid(freq)) {
    char d = s.charAt(l++);
    freq.put(d, freq.get(d) - 1);
    if (freq.get(d) == 0) freq.remove(d);
  }
  best = Math.max(best, r - l + 1);
}

• Identify it when:
  • Substring or subarray with length k, or best score within constraints.
  • Max, min, first, shortest, or longest subarray meeting a property.
• Options: fixed size, growing-shrinking, frequency maps for distinct or count constraints.
• Steps template:
  1. Expand right, add element to state.
  2. While invalid, shrink left, remove from state.
  3. Track best answer during valid windows.
• Pitfalls: forgetting to shrink, not updating answer at correct time, wrong invariant.
• Complexity: O(n).
• LeetCode set: Maximum Sum Subarray of Size K (educative style); Longest Substring Without Repeating Characters 3; Minimum Size Subarray Sum 209; Longest Repeating Character Replacement 424; Sliding Window Maximum 239.

Prefix Sum

Visual:

P[i] = a[0] + ... + a[i];  sum(l..r) = P[r] - P[l-1]

Java template (subarray sum = k):

Map<Integer,Integer> seen = new HashMap<>();
seen.put(0, 1);
int pref = 0, count = 0;
for (int x : nums) {
  pref += x;
  count += seen.getOrDefault(pref - k, 0);
  seen.put(pref, seen.getOrDefault(pref, 0) + 1);
}

• Identify it when:
  • Range sum or count of something in a range.
  • Need O(1) queries after O(n) preprocessing or subarray sums with hash map.
• Options: plain prefix sums; prefix counts; prefix modulo for divisible subarrays.
• Steps template:
  1. Maintain running prefix.
  2. Use hash map to store first seen prefix or counts.
  3. Query subarray via prefix[j] - prefix[i-1] or map lookups.
• Pitfalls: off-by-one with index 0; clearing map incorrectly.
• LeetCode set: Running Sum 1480; Subarray Sum Equals K 560; Find Pivot Index 724; Continuous Subarray Sum 523; Range Sum Query 303.

Binary Search

Visual:

lo .... mid .... hi   (predicate monotonic)

Java template (leftmost true):

int lo = L, hi = R, ans = -1;
while (lo <= hi) {
  int mid = lo + (hi - lo) / 2;
  if (check(mid)) { ans = mid; hi = mid - 1; }
  else lo = mid + 1;
}

• Identify it when:
  • Array is sorted or answer is monotonic in a search space.
  • You can ask: if I pick mid, should I go left or right.
• Options: index search, boundary search, binary search on answer.
• Steps template:
  1. low, high; while low <= high.
  2. mid; check condition C(mid).
  3. Move low or high; track best boundary.
• Pitfalls: infinite loop when mid calculation or update is wrong; off-by-one on boundaries.
• LeetCode set: Binary Search 704; Search Insert Position 35; Search in Rotated Sorted Array 33; Find Minimum in Rotated Sorted Array 153; Median of Two Sorted Arrays 4.

Intervals and Merge

Visual:

---- ----    -----   --
  \___merge___/   push

Java template (merge intervals):

Arrays.sort(iv, (a,b) -> Integer.compare(a[0], b[0]));
List<int[]> res = new ArrayList<>();
for (int[] cur : iv) {
  if (res.isEmpty() || cur[0] > res.get(res.size()-1)[1]) res.add(new int[]{cur[0], cur[1]});
  else res.get(res.size()-1)[1] = Math.max(res.get(res.size()-1)[1], cur[1]);
}

• Identify it when:
  • Merge, insert, or schedule non-overlapping intervals.
• Options: sort by start; sweep line; priority queue by end time.
• Steps template:
  1. Sort by start.
  2. If overlap with last, merge; else push.
  3. For meeting rooms, track end times in min-heap.
• LeetCode set: Merge Intervals 56; Insert Interval 57; Meeting Rooms II 253; Non-overlapping Intervals 435; Employee Free Time 759.

Trees (DFS and BFS)

Visual:

   n
  / \n l   r

Java template (DFS):

int dfs(TreeNode node) {
  if (node == null) return 0;
  int L = dfs(node.left), R = dfs(node.right);
  return combine(L, R, node);
}

• Identify it when:
  • Binary tree traversal, path sums, symmetric or balanced checks.
• Options: pre/in/post-order DFS; BFS level order; recursion vs stack.
• Steps template:
  1. Choose traversal order.
  2. Define function(node) -> combine child results.
  3. Handle base case null.
• LeetCode set: Maximum Depth of Binary Tree 104; Symmetric Tree 101; Binary Tree Level Order Traversal 102; Lowest Common Ancestor 236; Serialize and Deserialize Binary Tree 297.

Graphs

Visual:

Topo: queue of indegree==0
BFS: frontier layers

Java template (Topo Kahn):

Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
List<Integer> order = new ArrayList<>();
while (!q.isEmpty()) {
  int u = q.poll(); order.add(u);
  for (int v : adj[u]) if (--indeg[v] == 0) q.add(v);
}

• Identify it when:
  • Connectivity, shortest path, topological order, or components.
• Options: BFS, DFS, Dijkstra, Union-Find, Kahn for topo, cycle detection.
• Steps template:
  1. Build adjacency list.
  2. Pick traversal based on weights.
  3. Track visited, parent, or distance.
• LeetCode set: Number of Islands 200; Clone Graph 133; Course Schedule 207; Word Ladder 127; Network Delay Time 743.

Linked List

Visual:

head -> a -> b -> c

Java template (reverse):

ListNode prev = null, cur = head;
while (cur != null) {
  ListNode nxt = cur.next;
  cur.next = prev; prev = cur; cur = nxt;
}

• Identify it when:
  • Reversals, merging, cycle detection, reordering.
• Options: fast-slow pointers; dummy head; in-place reverse.
• Steps template:
  1. Use dummy; split or reverse part.
  2. Connect carefully with saved next.
  3. Use fast-slow for cycle and middle.
• LeetCode set: Reverse Linked List 206; Linked List Cycle 141; Merge Two Sorted Lists 21; Add Two Numbers 2; Copy List with Random Pointer 138.

Stack and Monotonic Stack

Visual:

Maintain increasing/decreasing stack of indices

Java template (monotonic):

int n = nums.length;
int[] ans = new int[n];
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
  while (!st.isEmpty() && breakCond(nums[st.peek()], nums[i])) {
    int j = st.pop(); ans[j] = i - j;
  }
  st.push(i);
}

• Identify it when:
  • Next greater element, valid parentheses, span or histogram problems.
• Options: plain stack for validation; monotonic increasing or decreasing stacks.
• Steps template:
  1. For parentheses, push expected closers.
  2. For monotonic, pop while break condition, compute area or distance.
  3. Push current with index/value.
• LeetCode set: Valid Parentheses 20; Min Stack 155; Daily Temperatures 739; Next Greater Element II 503; Largest Rectangle in Histogram 84.

Dynamic Programming

Visual:

Table f[i][j] or 1D rolling array

Java template (bottom-up):

for (int i = 0; i <= n; i++) {
  for (int j = 0; j <= m; j++) {
    dp[i][j] = bestOfChoices(i,j);
  }
}

• Identify it when:
  • Overlapping subproblems, optimal substructure, count ways or max score.
• Options: 1D or 2D DP, knapsack, LIS, partition, edit distance.
• Steps template:
  1. Define state f(i, j).
  2. Write recurrence from choices.
  3. Order of evaluation bottom-up; or memoize top-down.
• LeetCode set: Climbing Stairs 70; House Robber 198; Longest Increasing Subsequence 300; Coin Change 322; Edit Distance 72.

Backtracking

Visual:

choose -> explore -> undo

Java template:

List<List<Integer>> ans = new ArrayList<>();
void dfs(int i) {
  if (done(i)) { ans.add(new ArrayList<>(path)); return; }
  for (int c : choices(i)) {
    if (!feasible(c)) continue;
    apply(c); path.add(c);
    dfs(next(i));
    path.remove(path.size()-1); undo(c);
  }
}

• Identify it when:
  • Search all combinations, permutations, n-queens, subsets with constraints.
• Options: choose or skip; for loops with start index; pruning with feasibility checks.
• Steps template:
  1. Add current choice.
  2. Recurse to next position.
  3. Backtrack by undoing choice.
• LeetCode set: Subsets 78; Permutations 46; Combination Sum 39; N-Queens 51; Word Search 79.

Heap and Priority Queue

Visual:

Maintain size K; max-heap or min-heap by need

Java template (top K):

PriorityQueue<int[]> h = new PriorityQueue<>((a,b)->a[0]-b[0]);
for (int[] x : items) {
  h.offer(x);
  if (h.size() > K) h.poll();
}

• Identify it when:
  • Top K, running median, scheduling by earliest finishing or highest frequency.
• Options: min-heap, max-heap, custom comparator, heap of heaps.
• Steps template:
  1. Push candidates with priority.
  2. Pop to maintain size K or pick next job.
  3. For streaming, rebalance two heaps.
• LeetCode set: Kth Largest Element in an Array 215; Top K Frequent Elements 347; Merge K Sorted Lists 23; Reorganize String 767; Find Median from Data Stream 295.

Greedy

Visual:

sort by key; take if feasible

Java template:

Arrays.sort(items, (a,b) -> key(a) - key(b));
for (var it : items) if (feasible(it)) take(it);

• Identify it when:
  • Local choices lead to global optimum for scheduling, intervals, or coin-like problems.
• Options: sort by a ratio, earliest finish, or difference; prove exchange argument.
• Steps template:
  1. Sort by greedy key.
  2. Pick if feasible; skip otherwise.
  3. Maintain running answer.
• LeetCode set: Assign Cookies 455; Jump Game 55; Gas Station 134; Task Scheduler 621; Candy 135.

Bit Manipulation

Visual:

XOR cancels pairs; masks enumerate subsets

Java template:

int ans = 0;
for (int x : nums) ans ^= x;

• Identify it when:
  • Parity, unique number among duplicates, subsets via bitmasks.
• Options: XOR, bit count, bit DP, masks.
• Steps template:
  1. Use XOR to cancel pairs.
  2. Shift and mask to test bits.
  3. Precompute bit counts if needed.
• LeetCode set: Single Number 136; Number of 1 Bits 191; Counting Bits 338; Sum of Two Integers 371; Maximum Product of Word Lengths 318.

Union-Find (Disjoint Set)

Visual:

parent + rank; path compression

Java template:

int find(int x){ return p[x]==x? x : (p[x]=find(p[x])); }
void unite(int a,int b){ int ra=find(a), rb=find(b); if (ra==rb) return; if (rank[ra]<rank[rb]) p[ra]=rb; else if (rank[rb]<rank[ra]) p[rb]=ra; else { p[rb]=ra; rank[ra]++; } }

• Identify it when:
  • Grouping connectivity, number of components, cycle detection in undirected graphs.
• Options: union by rank, path compression, union by size.
• Steps template:
  1. Make set for every node.
  2. For every edge, union(u, v).
  3. Count unique parents.
• LeetCode set: Number of Provinces 547; Redundant Connection 684; Accounts Merge 721; Graph Valid Tree 261; Smallest String With Swaps 1202.

Math and Geometry

Visual:

Use identities; cross product for orientation

Java snippet (fast pow):

long pow(long a, long e){ long r=1; while(e>0){ if((e&1)==1) r*=a; a*=a; e>>=1; } return r; }

• Identify it when:
  • Pure math function or geometric constraints.
• Options: binary exponentiation, integer sqrt, vector cross product, angle sorting.
• Steps template:
  1. Reduce using algebraic identity.
  2. Watch overflow and precision.
  3. Use geometry primitives.
• LeetCode set: Power of Two 231; Sqrt(x) 69; Happy Number 202; Plus One 66; Rotate Image 48.

Design, LRU, and System-Style Questions

Visual:

HashMap + DoublyLinkedList -> O(1) get/put/evict

Java sketch (LRU core):

class LRU {
  static class Node{int k,v; Node p,n;}
  Map<Integer,Node> map = new HashMap<>();
  Node h = new Node(), t = new Node();
  LRU(){ h.n=t; t.p=h; }
  void moveFront(Node x){ remove(x); insertAfter(h,x);}
  void insertAfter(Node a, Node x){ x.n=a.n; x.p=a; a.n.p=x; a.n=x; }
  void remove(Node x){ x.p.n=x.n; x.n.p=x.p; }
}

• Identify it when:
  • Caching, rate limiting, LFU/LRU, simple system components.
• Options: hashmap + doubly linked list; counters with TTL; token bucket.
• Steps template:
  1. Design API surface.
  2. Pick core data structure pair.
  3. Define complexity and eviction behavior.
• LeetCode set: Min Stack 155; LRU Cache 146; LFU Cache 460; Design Twitter 355; Serialize and Deserialize Binary Tree 297.

---

Practice Plan

• Week 1: Two Pointers, Sliding Window, Prefix Sum.
• Week 2: Binary Search, Intervals, Trees.
• Week 3: Graphs, Linked List, Stack.
• Week 4: DP, Backtracking.
• Week 5: Heap, Greedy, Bit Manipulation.
• Week 6: Union-Find, Math, Design.

For each pattern session: solve 3 problems blind, then 1 timed, then explain out loud the choices, invariants, and complexity.

Pattern Decision Cheat Sheet

• Subarray with constraint -> Sliding Window.
• Range sums -> Prefix Sum.
• Sorted or monotone answer -> Binary Search.
• Merge or schedule -> Intervals + Greedy or Heap.
• Paths, connectivity -> Graph + BFS/DFS or Union-Find.
• Build from choices -> DP or Backtracking.
• Top K or stream -> Heap.
• Next greater or validation -> Stack or Monotonic Stack.

---

Table of Contents

• Two Pointers
• Sliding Window
• Prefix Sum
• Binary Search
• Intervals and Merge
• Trees (DFS and BFS)
• Graphs
• Linked List
• Stack and Monotonic Stack
• Dynamic Programming
• Backtracking
• Heap and Priority Queue
• Greedy
• Bit Manipulation
• Union-Find (Disjoint Set)
• Math and Geometry
• Design, LRU, and System-Style Questions