Skip to content
DSA Grind
All 26 sections

Algorithm Template Cheat Sheet — All 21 Patterns

NoteUpdated
On this page

One page. Every skeleton. Each pattern’s full template section (with knobs, rules, and gotchas) lives in NN-Pattern/pattern-guide.md under ## 0. The Template. This file is the night-before-the-interview condensation.

Java only. Deque/ArrayDeque everywhere — never java.util.Stack, never LinkedList as a queue.

How to use this page

  1. Read the problem. Name the pattern out loud using the trigger table below.
  2. Open that pattern’s ## 0. The Template and copy the skeleton.
  3. Change only the knobs the guide names — do not re-derive the loop.
  4. Trace it on a 4–6 element input before you claim it works.

Trigger → Pattern lookup

The problem says… Pattern Template file
sorted array, find a pair summing to X Two Pointers 01
subarray / substring with a property Sliding Window 02
count, group, “seen before”, subarray sums to k Hashing / Prefix Sum 03
linked-list cycle, middle, “happy number” Fast & Slow Pointers 04
overlapping ranges, meeting rooms Merge Intervals 05
n numbers from 1..n, O(1) space Cyclic Sort 06
reverse / reorder a linked list in place LL Reversal 07
shortest / minimum steps, level by level BFS 08
all paths, connectivity, tree height DFS 09
running median, balance two halves Two Heaps 10
all subsets / permutations / combinations Backtracking 11
sorted, or a monotonic answer space, O(log n) Binary Search 12
top / k-th largest, k most frequent Top-K (Heap) 13
count the ways, min/max with overlapping subproblems DP 14
nodes + edges, shortest path, dependencies Graph 16
dynamic connectivity, friend circles, cycle (undirected) Union-Find 17
prefix search, autocomplete, word dictionary Trie 18
locally-best choice, “maximum number you can select” Greedy 19
next / previous greater or smaller element Monotonic Stack 20
nesting / matching; FIFO; sliding-window max Stacks & Queues 21

01 — Two Pointers (opposite ends)

int left = 0, right = arr.length - 1;
while (left < right) {                       // '<' — l==r is one element
    int sum = arr[left] + arr[right];
    if (sum == target) return ...;
    else if (sum < target) left++;           // need bigger
    else                   right--;          // need smaller
}

Same-direction variant (in-place filter): slow = write cursor, fast = read cursor.

02 — Sliding Window (variable size)

int left = 0, best = 0;
for (int right = 0; right < n; right++) {
    add(nums[right]);                         // EXPAND
    while (invalid()) { remove(nums[left]); left++; }   // SHRINK
    best = Math.max(best, right - left + 1);  // RECORD
}

LONGEST → while (INVALID), record after the while. SHORTEST → while (VALID), record inside the while. Fixed size k: sum += nums[i]; if (i >= k) sum -= nums[i-k]; if (i >= k-1) record;

03 — Hashing / Prefix Sum

freq.merge(c, 1, Integer::sum);                        // count
map.computeIfAbsent(key, k -> new ArrayList<>()).add(v); // group

Map<Integer,Integer> prefix = new HashMap<>();
prefix.put(0, 1);                                       // ← the seed everyone forgets
int sum = 0, count = 0;
for (int x : nums) { sum += x; count += prefix.getOrDefault(sum - k, 0);
                     prefix.merge(sum, 1, Integer::sum); }

04 — Fast & Slow Pointers

ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {   // BOTH null checks
    slow = slow.next; fast = fast.next.next;
    if (slow == fast) { /* cycle */ }
}
// cycle ENTRY: on meeting, reset p = head; advance p and slow 1 step each until p == slow.

05 — Merge Intervals

Arrays.sort(iv, (a, b) -> Integer.compare(a[0], b[0]));  // by START to merge
if (cur[0] <= last[1]) last[1] = Math.max(last[1], cur[1]);   // overlap → extend
else out.add(cur);                                            // disjoint → new

Sort by end for greedy max-non-overlapping. Min-heap of end times for room counting.

06 — Cyclic Sort

int i = 0;
while (i < n) {
    int correct = nums[i] - 1;
    if (nums[i] != nums[correct]) swap(nums, i, correct);   // do NOT i++ after a swap
    else i++;
}

07 — Linked List Reversal

ListNode prev = null, curr = head;
while (curr != null) {
    ListNode next = curr.next;   // SAVE
    curr.next = prev;            // FLIP
    prev = curr;                 // ADVANCE
    curr = next;
}
return prev;                     // the NEW head

Head might change? Use ListNode dummy = new ListNode(0, head); and return dummy.next;

08 — BFS

Queue<T> q = new ArrayDeque<>(); q.offer(start); seen.add(start);
int level = 0;
while (!q.isEmpty()) {
    int size = q.size();                       // ← FREEZE = one level
    for (int i = 0; i < size; i++) {
        T cur = q.poll();
        for (T next : neighbours(cur))
            if (seen.add(next)) q.offer(next); // mark ON ENQUEUE
    }
    level++;
}

Multi-source: seed the queue with all sources before the loop. Nothing else changes.

09 — DFS

int dfs(TreeNode node) {                       // return a value UP (post-order)
    if (node == null) return 0;
    return combine(node.val, dfs(node.left), dfs(node.right));
}
PRE  visit, left, right   → serialize
IN   left, visit, right   → sorted output on a BST
POST left, right, visit   → heights, bottom-up aggregation

10 — Two Heaps (running median)

PriorityQueue<Integer> lo = new PriorityQueue<>(Comparator.reverseOrder()); // smaller half
PriorityQueue<Integer> hi = new PriorityQueue<>();                          // larger half

lo.offer(num);  hi.offer(lo.poll());              // enforce max(lo) <= min(hi)
if (hi.size() > lo.size()) lo.offer(hi.poll());   // rebalance

median = lo.size() > hi.size() ? lo.peek() : (lo.peek() + hi.peek()) / 2.0;

11 — Backtracking

void backtrack(int start, List<Integer> path, List<List<Integer>> out) {
    out.add(new ArrayList<>(path));               // COPY, never `path` itself
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i-1]) continue;  // dedupe (sorted input)
        path.add(nums[i]);                        // CHOOSE
        backtrack(i + 1, path, out);              // EXPLORE
        path.remove(path.size() - 1);             // UN-CHOOSE
    }
}

i + 1 = no reuse · i = unlimited reuse · 0 + used[] = permutations

12 — Binary Search (boundary form — memorise this one)

int lo = 0, hi = n;                    // hi EXCLUSIVE
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;      // overflow-safe
    if (predicate(mid)) hi = mid;      // might be the answer → keep
    else                lo = mid + 1;  // definitely not → discard
}
return lo;

Works on any monotonic predicate, not just sorted arrays — that’s “binary search on the answer” (LC 875, 1011, 410). Never write lo = mid (infinite loop).

13 — Top K

PriorityQueue<Integer> heap = new PriorityQueue<>();   // MIN-heap for the k LARGEST
for (int x : nums) { heap.offer(x); if (heap.size() > k) heap.poll(); }

The heap’s top is always the element you’re most willing to throw away. k largest → min-heap · k smallest → max-heap · k closest → max-heap by distance

14 — Dynamic Programming

// 1. STATE: say dp[i] in English   2. RECURRENCE   3. BASE CASE   4. ORDER   5. ANSWER
int[] dp = new int[n + 1];
dp[0] = base;
for (int i = 1; i <= n; i++) dp[i] = f(dp[i - 1], dp[i - 2], ...);
return dp[n];

Stuck? Write the brute-force recursion first, then add Integer[] memo. Memoising never changes the answer, only the speed.

16 — Graph

List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }  // drop 2nd if directed
The question asks for Algorithm
fewest steps, unweighted BFS
all paths / traversal / connectivity DFS
a valid order given dependencies Topological Sort (Kahn’s)
grouping, “are these connected” Union-Find
cheapest path, non-negative weights Dijkstra
negative weights / negative-cycle check Bellman-Ford

17 — Union-Find (DSU)

int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; }

boolean union(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return false;                          // ← already connected ⇒ CYCLE
    if (rank[rx] < rank[ry]) parent[rx] = ry;
    else if (rank[rx] > rank[ry]) parent[ry] = rx;
    else { parent[ry] = rx; rank[rx]++; }
    components--; return true;
}

18 — Trie

class Node { Node[] children = new Node[26]; boolean isWord; }

Node cur = root;
for (char c : word.toCharArray()) {
    int i = c - 'a';
    if (cur.children[i] == null) cur.children[i] = new Node();
    cur = cur.children[i];
}
cur.isWord = true;      // ← without this, search("app") matches inside "apple"

19 — Greedy

Arrays.sort(items, (a, b) -> Integer.compare(a[KEY], b[KEY]));   // choosing KEY *is* the problem
for (int[] item : items) if (compatible(item, lastTaken)) { take(item); lastTaken = item[END]; }

Max non-overlapping → sort by end. Merge → sort by start. Before coding: “why is the locally best choice globally optimal?” No answer ⇒ it’s DP.

20 — Monotonic Stack

Deque<Integer> stack = new ArrayDeque<>();       // INDICES, not values
for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {   // '<' → next GREATER
        int idx = stack.pop();
        res[idx] = nums[i];                      // or (i - idx) for a distance
    }
    stack.push(i);
}

Flip to > for next smaller. Leftovers on the stack keep the default (-1 or 0). O(n): each index pushed once, popped once.

21 — Stacks & Queues

// Monotonic deque — sliding-window max in O(n)
Deque<Integer> dq = new ArrayDeque<>();          // INDICES, values decreasing front→back
for (int i = 0; i < n; i++) {
    if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();       // slid out
    while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();  // dominated
    dq.offerLast(i);
    if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
}
// Queue from two stacks — refill ONLY when `out` is empty (amortised O(1))
private void shift() { if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop()); }
// Ring buffer — store `count`, derive the rear; never store a tail pointer
buf[(head + count) % k] = v; count++;            // enQueue
head = (head + 1) % k; count--;                  // deQueue

Java Collections — the senior-signal table

Need Use Never Why
Stack ArrayDeque (push/pop/peek) java.util.Stack Stack extends Vector → synchronized, iterates bottom-to-top
Queue ArrayDeque (offer/poll/peek) LinkedList node-per-element, poor cache locality
Deque / monotonic window ArrayDeque LinkedList same
Heap PriorityQueue — min-heap by default; Comparator.reverseOrder() for max
Counting a–z int[26] HashMap no hashing, no boxing
Grid coordinate int[]{r,c} or r*cols+c "r,c" String string hashing + parsing per access
Visited set boolean[] / boolean[][] HashSet<Integer> array indexing beats hashing
Sorted keys + floor/ceiling TreeMap HashMap HashMap has no ordering
Build a string in a loop StringBuilder String += O(n²) allocations — strings are immutable

Five one-liners that show up in every review

int mid = lo + (hi - lo) / 2;                    // NOT (lo + hi) / 2 — overflows
(a, b) -> Integer.compare(a, b);                 // NOT a - b — overflows
out.add(new ArrayList<>(path));                  // NOT out.add(path) — reference to mutating list
if (!stack.isEmpty() && nums[stack.peek()] ...)  // isEmpty FIRST — peek() returns null → NPE on unbox
if (seen.add(next)) q.offer(next);               // mark visited on ENQUEUE, not dequeue

Complexity reference

Pattern Time Space
Two Pointers O(n), O(n log n) if you must sort O(1)
Sliding Window O(n) — left only moves forward O(1) or O(k)
Hashing / Prefix Sum O(n) O(n)
Fast & Slow Pointers O(n) O(1)
Merge Intervals O(n log n) — sort dominates O(n)
Cyclic Sort O(n) — ≤ n swaps total O(1)
LL Reversal O(n) O(1)
BFS / DFS O(V + E) O(V)
Two Heaps O(log n) insert, O(1) median O(n)
Backtracking O(n·2ⁿ) subsets, O(n·n!) permutations O(n) recursion depth
Binary Search O(log n), O(n log M) on the answer O(1)
Top K (heap) O(n log k) O(k)
DP O(states × transitions) O(states), often reducible to O(1) rows
Union-Find ~O(α(n)) ≈ O(1) amortised O(n)
Trie O(L) per op O(total chars × alphabet)
Greedy O(n log n) — sort dominates O(1)
Monotonic Stack O(n) — each index in/out once O(n)
Monotonic Deque O(n) O(k)