Cheat SheetsDSA PatternsCoding Patterns

Coding Patterns — Cheat Sheet

DSA Patterns · 13 topics. Download the PDF or the Instagram carousel and share it.

Cheat Sheet · AiCanCode.org
Coding Patterns
DSA Patterns13 topicsQuick revision reference
1

Sliding Window

Process a window of elements that slides across an array or string.

  • ✓Problem involves a contiguous subarray or substring
  • ✓Looking for a maximum, minimum, or count within a window
  • ✓Keywords: "longest", "shortest", "contains", "subarray", "substring"
  • ✓Window size is either fixed or dynamic based on a condition
  • ✓Instead of recomputing the entire window on every step, maintain a running state (sum, freq map, etc.) and update it incrementally as the window slides.
Template
// Fixed-size window
int windowSum = 0, maxSum = 0;
for (int i = 0; i < nums.length; i++) {
    windowSum += nums[i];
    if (i >= k - 1) {
        maxSum = Math.max(maxSum, windowSum);
        windowSum -= nums[i - (k - 1)];
    }
}

// Variable-size window (two pointers)
int left = 0, result = 0;
Map<Character, Integer> freq = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
    freq.merge(s.charAt(right), 1, Integer::sum);
    // shrink window while condition violated
    while (freq.size() > k) {
        char c = s.charAt(left++);
        freq.merge(c, -1, Integer::sum);
        if (freq.get(c) == 0) freq.remove(c);
    }
    result = Math.max(result, right - left + 1);
}
2

Two Pointers

Use two indices to scan from both ends or at different speeds.

  • ✓Array or string is sorted (or can be sorted)
  • ✓Looking for a pair, triplet, or partition
  • ✓Need to remove duplicates or reverse in-place
  • ✓Keywords: "two sum", "palindrome", "partition", "opposite ends"
  • ✓Move the left pointer right when the current sum is too small, move the right pointer left when too large. The sorted order guarantees you never need to revisit elements.
Template
// Opposite-direction two pointers (sorted array)
int left = 0, right = nums.length - 1;
while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == target) {
        // found pair
        left++; right--;
    } else if (sum < target) {
        left++;
    } else {
        right--;
    }
}

// Same-direction two pointers (in-place remove)
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
    if (nums[fast] != val) {
        nums[slow++] = nums[fast];
    }
}
3

Fast & Slow Pointers

Floyd's cycle detection — two pointers at different speeds.

  • ✓Detecting a cycle in a linked list or sequence
  • ✓Finding the start of a cycle
  • ✓Finding the middle of a linked list
  • ✓Detecting a duplicate without extra space
  • ✓When fast and slow meet inside a cycle, reset slow to head. Moving both one step at a time from there brings them to the cycle entrance — a mathematical property of the meeting point.
Template
// Detect cycle
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true; // cycle exists
}
return false;

// Find cycle start
if (hasCycle) {
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    // slow == fast == cycle start
}

// Find middle of linked list
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
// slow is at middle
4

Binary Search

Halve the search space every step on any monotonic condition.

  • ✓Array is sorted or partially sorted
  • ✓Finding a boundary (first/last occurrence)
  • ✓Answer is a number and feasibility is monotonic ("can I do it in X days?")
  • ✓Looking for a peak, minimum in rotated, or kth element
  • ✓Always define: what does mid represent, and which half can I eliminate? The three templates — find exact, find leftmost, find rightmost — cover all cases. Get the loop invariant right and the off-by-one errors disappear.
Template
// Classic binary search
int left = 0, right = nums.length - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
}

// Binary search on answer (e.g. "minimum capacity to ship in D days")
int left = minCapacity, right = maxCapacity;
while (left < right) {
    int mid = left + (right - left) / 2;
    if (feasible(mid)) right = mid;   // mid works, try smaller
    else left = mid + 1;              // mid fails, need larger
}
return left; // smallest feasible value
5

Tree Traversal

Visit every node in a tree — recursively (DFS) or level-by-level (BFS).

  • ✓DFS: depth, path sum, subtree comparison, LCA
  • ✓BFS: level order, minimum depth, right side view
  • ✓Inorder on BST gives sorted sequence
  • ✓Postorder when you need subtree results before parent
  • ✓For most DFS tree problems, define a recursive function that returns something meaningful (height, count, bool) and propagates results bottom-up. Trust the recursion — you only need to handle the current node and its two children.
Template
// DFS — recursive (postorder example)
int height(TreeNode node) {
    if (node == null) return 0;
    int left  = height(node.left);
    int right = height(node.right);
    return 1 + Math.max(left, right);
}

// BFS — level order
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
    int size = q.size(); // nodes at current level
    for (int i = 0; i < size; i++) {
        TreeNode node = q.poll();
        if (node.left  != null) q.offer(node.left);
        if (node.right != null) q.offer(node.right);
    }
}
6

Graph BFS / DFS

Explore all reachable nodes in a graph, tracking visited state.

  • ✓Counting connected components or islands
  • ✓Shortest path in unweighted graph → BFS
  • ✓Topological sort / dependency ordering → DFS or BFS (Kahn's)
  • ✓Cycle detection in directed graph → DFS with color states
  • ✓Multi-source BFS when starting from multiple nodes simultaneously
  • ✓Mark a cell/node visited BEFORE pushing it onto the queue (BFS), not after popping — otherwise you push duplicates and get TLE. For DFS cycle detection, use three states: unvisited (0), in-stack (1), done (2).
Template
// BFS — shortest path / multi-source
boolean[][] visited = new boolean[rows][cols];
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{startR, startC});
visited[startR][startC] = true;
int steps = 0;
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!q.isEmpty()) {
    int size = q.size();
    for (int i = 0; i < size; i++) {
        int[] cur = q.poll();
        for (int[] d : dirs) {
            int nr = cur[0] + d[0], nc = cur[1] + d[1];
            if (inBounds(nr, nc) && !visited[nr][nc] && grid[nr][nc] == 1) {
                visited[nr][nc] = true;
                q.offer(new int[]{nr, nc});
            }
        }
    }
    steps++;
}

// DFS — cycle detection (directed graph)
// 0 = unvisited, 1 = in-stack, 2 = done
int[] state = new int[n];
boolean hasCycle(int node, List<List<Integer>> adj) {
    state[node] = 1;
    for (int nei : adj.get(node)) {
        if (state[nei] == 1) return true;
        if (state[nei] == 0 && hasCycle(nei, adj)) return true;
    }
    state[node] = 2;
    return false;
}
7

Dynamic Programming

Break the problem into overlapping subproblems and cache results.

  • ✓Counting ways, maximizing/minimizing a value, or checking feasibility
  • ✓Problem can be broken into overlapping subproblems
  • ✓Keywords: "minimum cost", "maximum profit", "number of ways", "can you reach"
  • ✓Greedy doesn't work — local optimal ≠ global optimal
  • ✓Define dp[i] clearly before writing any code. Ask: "what does dp[i] represent?" Then write the recurrence and base cases. The transition almost always looks at dp[i-1] or dp[i-w] or dp[i][j-1].
Template
// 1D DP — climbing stairs / coin change
int[] dp = new int[n + 1];
dp[0] = 1; // base case
for (int i = 1; i <= n; i++) {
    for (int coin : coins) {
        if (i >= coin) dp[i] += dp[i - coin];
    }
}

// 2D DP — LCS / edit distance
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (s1.charAt(i-1) == s2.charAt(j-1)) {
            dp[i][j] = dp[i-1][j-1] + 1;
        } else {
            dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
        }
    }
}
8

Backtracking

Explore all possibilities by building candidates and pruning dead ends.

  • ✓Generating all subsets, permutations, or combinations
  • ✓Grid/string problems asking to "find all valid paths"
  • ✓Constraint satisfaction (N-Queens, Sudoku)
  • ✓Keywords: "all possible", "generate all", "find all combinations"
  • ✓The pattern is always: choose → recurse → unchoose. The "unchoose" step (removing the last element from your path) is what makes backtracking distinct from plain DFS. Always pass a start index to avoid re-using elements.
Template
// Subsets / Combinations template
List<List<Integer>> result = new ArrayList<>();
void backtrack(int start, List<Integer> current, int[] nums) {
    result.add(new ArrayList<>(current)); // add a copy
    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);           // choose
        backtrack(i + 1, current, nums); // recurse
        current.remove(current.size() - 1); // unchoose
    }
}

// Permutations template
void permute(int[] nums, List<Integer> current, boolean[] used) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        current.add(nums[i]);
        permute(nums, current, used);
        current.remove(current.size() - 1);
        used[i] = false;
    }
}
9

Monotonic Stack

A stack maintained in sorted order to find next greater/smaller elements.

  • ✓Finding the next greater or smaller element for each position
  • ✓Calculating spans, areas, or distances based on surrounding elements
  • ✓Keywords: "next greater", "daily temperatures", "histogram", "trapping water"
  • ✓Processing elements where future elements affect past calculations
  • ✓Elements are pushed and popped at most once → O(n) total. For "next greater to the right", iterate left-to-right with a decreasing stack. For "previous smaller", iterate right-to-left or use an increasing stack.
Template
// Next Greater Element (monotonic decreasing stack)
int[] result = new int[nums.length];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>(); // stores indices

for (int i = 0; i < nums.length; i++) {
    // pop elements smaller than current — current is their answer
    while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
        result[stack.pop()] = nums[i];
    }
    stack.push(i);
}

// Largest Rectangle in Histogram pattern
stack.push(-1); // sentinel
for (int i = 0; i <= heights.length; i++) {
    int h = (i == heights.length) ? 0 : heights[i];
    while (stack.peek() != -1 && heights[stack.peek()] > h) {
        int height = heights[stack.pop()];
        int width  = i - stack.peek() - 1;
        maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
}
10

Merge Intervals

Sort intervals by start time, then sweep and merge overlapping ones.

  • ✓Given a list of intervals, find overlaps or merge them
  • ✓Scheduling / meeting room problems
  • ✓Inserting a new interval into a sorted list
  • ✓Finding minimum number of groups/rooms to cover all intervals
  • ✓Two intervals [a,b] and [c,d] overlap if and only if c ≤ b (after sorting by start). The merged interval is [a, max(b, d)]. Always sort first — the sweep only works in order.
Template
// Merge overlapping intervals
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> merged = new ArrayList<>();
merged.add(intervals[0]);

for (int i = 1; i < intervals.length; i++) {
    int[] last = merged.get(merged.size() - 1);
    if (intervals[i][0] <= last[1]) {
        // overlap — extend the end
        last[1] = Math.max(last[1], intervals[i][1]);
    } else {
        merged.add(intervals[i]);
    }
}

// Count minimum rooms (or groups) needed
Arrays.sort(starts); Arrays.sort(ends);
int rooms = 0, maxRooms = 0, j = 0;
for (int i = 0; i < n; i++) {
    if (starts[i] < ends[j]) { rooms++; maxRooms = Math.max(maxRooms, rooms); }
    else { rooms--; j++; }
}
11

Top K Elements

Use a heap to track the K largest or smallest elements in O(n log k).

  • ✓Finding kth largest or kth smallest element
  • ✓Top K frequent elements
  • ✓Merging K sorted lists
  • ✓Finding the median of a stream (two heaps)
  • ✓Keywords: "k largest", "k most frequent", "k closest"
  • ✓Min-heap of size k → gives you k largest (root = kth largest). Max-heap of size k → gives you k smallest (root = kth smallest). Always ask: which end of the heap do I want to evict from?
Template
// Kth Largest — min-heap of size k
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
    minHeap.offer(num);
    if (minHeap.size() > k) minHeap.poll(); // remove smallest
}
return minHeap.peek(); // kth largest

// Top K Frequent — bucket approach or heap
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) freq.merge(n, 1, Integer::sum);

PriorityQueue<Integer> heap = new PriorityQueue<>(
    (a, b) -> freq.get(a) - freq.get(b)  // min-heap by frequency
);
for (int key : freq.keySet()) {
    heap.offer(key);
    if (heap.size() > k) heap.poll();
}
12

Linked List In-Place

Reverse, merge, or restructure linked lists without extra space.

  • ✓Reversing all or part of a linked list
  • ✓Merging two sorted lists or K sorted lists
  • ✓Rearranging nodes (odd-even, rotate, reorder)
  • ✓Deep copying a list with random pointers
  • ✓Always draw 3-4 nodes on paper and trace pointer changes before coding. Keep a 'prev' pointer when reversing. Use a dummy head node to handle edge cases at the start of the list cleanly.
Template
// Reverse a linked list (iterative)
ListNode prev = null, curr = head;
while (curr != null) {
    ListNode next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
}
return prev; // new head

// Merge two sorted lists
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
    if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
    else                  { tail.next = l2; l2 = l2.next; }
    tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
13

Trie (Prefix Tree)

A tree for storing strings character-by-character for fast prefix lookups.

  • ✓Prefix matching or autocomplete
  • ✓Storing a dictionary of words for repeated lookups
  • ✓Word search in a 2D board (Trie prunes dead-end paths)
  • ✓Finding longest common prefix across many strings
  • ✓Each TrieNode holds children[26] (for lowercase letters) and a boolean isEnd. Insert: for each char, create child if absent then move down. Search: traverse and check isEnd. StartsWith: traverse and return true if path exists.
Template
class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd = false;
}

class Trie {
    private TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null)
                node.children[idx] = new TrieNode();
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return node.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return true;
    }
}
Learn this free with Aria, your AI tutor → AiCanCode.org/learn/dsa-patterns