Coding Interview Patterns: Master the Templates That Solve Every Problem

Why Patterns Matter

Recognizing patterns is the key to solving coding interview problems quickly. Instead of memorizing solutions, learn the underlying patterns. Most interview problems are not entirely new—they are variations of well-known templates. By mastering a handful of core patterns, you can decompose unfamiliar problems into pieces you already know how to solve. This shifts the interview from a guessing game into a structured approach: identify the pattern, apply the template, and customize it to the specific constraints.

The patterns below are ordered roughly by frequency of appearance in interviews. Problems at companies like Amazon, Google, and Meta often combine two or more of these patterns, so understanding the building blocks is more important than memorizing any single solution.

The 15 Essential Patterns

1. Two Pointers

When to use: Sorted arrays, finding pairs, or problems where you need to compare elements from different positions simultaneously. The two pointers pattern works because sorted data gives you directional information—if a sum is too small, moving the left pointer forward increases it; if too large, moving the right pointer backward decreases it.

Key insight: Two pointers reduce a nested O(n²) brute force loop to O(n) by exploiting the sorted order of data or by using pointer movement rules that eliminate impossible pairs.

int left = 0, right = arr.length - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == target) return new int[]{left, right};
    else if (sum < target) left++;
    else right--;
}

Walkthrough: For Two Sum II on [2, 7, 11, 15] with target 9: left points to 2, right points to 15. Sum is 17, too large, so move right. Now sum is 2 + 11 = 13, still too large. Move right again. Now 2 + 7 = 9, found it.

Common mistakes: Forgetting to handle duplicates in problems like 3Sum—always skip duplicate values after finding a valid triplet. Another mistake is not considering that the array may not be sorted, which is a prerequisite for this pattern.

Real-world use case: Scheduling algorithms where you need to find non-overlapping time slots from two sorted lists of meeting times.

Problems: Two Sum II, Container With Most Water, 3Sum, Remove Duplicates from Sorted Array

2. Sliding Window

When to use: Subarray or substring problems where you need to find a contiguous sequence that satisfies some condition. The window expands and contracts as you scan through the data, maintaining state about the current window.

Key insight: Instead of recalculating the window from scratch each time, you add the new element entering the window and remove the element leaving it. This turns O(n × k) into O(n).

int windowSum = 0, maxSum = 0;
for (int i = 0; i < n; i++) {
    windowSum += arr[i];
    if (i >= k) windowSum -= arr[i - k];
    maxSum = Math.max(maxSum, windowSum);
}

Walkthrough: For Maximum Sum Subarray of size 3 on [1, 4, 2, 10, 2, 3, 1, 0, 20]: window starts at [1,4,2]=7, slides to [4,2,10]=16, then [2,10,2]=14, then [10,2,3]=15, and so on. The maximum is 23 from [2, 3, 1, 0, 20]—wait, that is size 5. The answer for fixed size 3 is 16.

Common mistakes: Using the wrong window type. Fixed-size windows use a simple for loop with i >= k. Variable-size windows need a while loop inside to shrink the window. Confusing these two leads to off-by-one errors.

Real-world use case: Network packet analysis—detecting anomalies within a rolling time window, or calculating average response time over the last N requests.

Problems: Maximum Sum Subarray, Longest Substring Without Repeating Characters, Minimum Window Substring, Sliding Window Maximum

3. Fast & Slow Pointers

When to use: Cycle detection in linked lists, finding the middle element, or problems involving repeated transformations (like Happy Number where you repeatedly replace a number with the sum of its squared digits).

Key insight: If there is a cycle, the fast pointer will eventually meet the slow pointer inside the cycle. If there is no cycle, the fast pointer reaches the end. The meeting point reveals useful structural information about the data.

ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true;
}

Walkthrough: For finding the middle of a linked list, the fast pointer reaches the end when the slow pointer is exactly at the middle. For cycle detection, once they meet, reset one pointer to head and move both at the same speed—their next meeting point is the cycle start.

Common mistakes: Not handling the case where the list has zero or one element. Forgetting to check fast.next != null before accessing fast.next.next, which causes a NullPointerException.

Real-world use case: Detecting infinite loops in process scheduling, or finding循环 references in object graphs during garbage collection.

Problems: Linked List Cycle, Happy Number, Middle of Linked List, Find the Duplicate Number

4. Merge Intervals

When to use: Problems involving overlapping ranges, time intervals, or any data that can be represented as start-end pairs. The key operation is merging two intervals if they overlap, or inserting a new interval into a sorted list.

Key insight: Always sort intervals by start time first. Then iterate once—either merge the current interval with the previous one, or start a new group.

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

Walkthrough: For intervals [[1,3],[2,6],[8,10],[15,18]]: sort is already done. [1,3] starts merged. [2,6] overlaps (6 >= 2), merge to [1,6]. [8,10] does not overlap (6 < 8), add as new. [15,18] does not overlap, add as new. Result: [[1,6],[8,10],[15,18]].

Common mistakes: Forgetting to sort first. Comparing end times instead of start times when deciding whether to merge. Not updating the end time correctly when merging.

Real-world use case: Calendar scheduling—finding available meeting slots across multiple people's busy times, or merging CPU task time ranges.

Problems: Merge Intervals, Insert Interval, Non-overlapping Intervals, Meeting Rooms II

5. Binary Search

When to use: Sorted data, or any problem where you can define a search space and eliminate half of it based on a condition. Binary search is not limited to arrays—it works on any monotonic function.

Key insight: The critical detail is correctly defining what left, right, and mid represent, and updating them to avoid infinite loops. Use left + (right - left) / 2 instead of (left + right) / 2 to prevent integer overflow.

int left = 0, right = arr.length - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
}

Walkthrough: For searching 7 in [2, 5, 7, 8, 12]: left=0, right=4, mid=2, arr[2]=7, found. For searching 3: mid=2, arr[2]=7 > 3, so right=1. Now mid=0, arr[0]=2 < 3, so left=1. Now left > right, search ends—3 is not in the array.

Common mistakes: Off-by-one errors in loop conditions (< vs <=) and pointer updates (mid vs mid + 1). These depend on whether right represents an inclusive bound or the array length.

Real-world use case: Searching a sorted log file for a specific timestamp, or finding the insertion point for a new record in a sorted database.

Problems: Binary Search, Search in Rotated Sorted Array, Find Minimum in Rotated Array, Koko Eating Bananas

6. DFS (Depth-First Search)

When to use: Graph or tree traversal when you need to explore as deep as possible before backtracking. DFS is natural for problems involving paths, connectivity, and exhaustively exploring all possibilities.

Key insight: DFS uses a stack (either explicit or via recursion). It explores one branch fully before moving to the next. This makes it ideal for problems where you need to find any path, or enumerate all paths.

void dfs(TreeNode node) {
    if (node == null) return;
    // Process node here (pre-order)
    dfs(node.left);
    // Process between children (in-order)
    dfs(node.right);
    // Process after children (post-order)
}

Walkthrough: For Number of Islands, you iterate through the grid. When you find a land cell, you run DFS to mark all connected land cells as visited, incrementing the island count by 1. The DFS floods outward in all four directions.

Common mistakes: Not tracking visited nodes in graphs (leads to infinite loops in cyclic graphs). Forgetting to handle the base case (null node or out-of-bounds index). Not restoring state during backtracking.

Real-world use case: File system directory traversal, dependency resolution in build systems, detecting deadlocks in resource allocation graphs.

Problems: Number of Islands, Path Sum, Binary Tree Paths, Clone Graph, Word Search

7. BFS (Breadth-First Search)

When to use: Level-order traversal, shortest path in unweighted graphs, or when you need to process nodes level by level. BFS guarantees the shortest path in unweighted graphs because it explores all nodes at distance d before any at distance d+1.

Key insight: BFS uses a queue. Track the queue size at each level to process one level at a time. This is essential for level-order problems.

Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        // Process node
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

Walkthrough: For Rotting Oranges, you start BFS from all rotten oranges simultaneously. Each BFS level represents one minute. Fresh oranges adjacent to rotten ones become rotten. The answer is the number of BFS levels needed.

Common mistakes: Not capturing queue.size() before the inner loop—this changes as you add children, mixing levels. Using DFS when the problem explicitly asks for shortest path (DFS does not guarantee shortest).

Real-world use case: Social network friend suggestions (finding degrees of separation), network broadcast routing, finding nearest exit in a maze.

Problems: Level Order Traversal, Rotting Oranges, Word Ladder, Binary Tree Right Side View

8. Backtracking

When to use: Generate all combinations, permutations, or subsets. Backtracking is DFS with a choice: at each step, you try all valid options, recurse, and then undo the choice (backtrack) to explore other options.

Key insight: The template is always the same—make a choice, recurse, undo the choice. The variation is in the pruning condition that skips invalid branches early.

void backtrack(List<Integer> path, int[] nums) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int num : nums) {
        if (path.contains(num)) continue;
        path.add(num);
        backtrack(path, nums);
        path.remove(path.size() - 1);
    }
}

Walkthrough: For Permutations of [1,2,3]: start with empty path. Add 1, recurse—add 2, recurse—add 3, recurse—path is full, save [1,2,3]. Backtrack, remove 3. No more options at depth 3, backtrack, remove 2. Try 3 instead—add 3, recurse—add 2, path [1,3,2], save. Continue exhaustively.

Common mistakes: Not using a deep copy when adding to results—new ArrayList<>(path) is critical because the path object is reused. Forgetting to remove the last element after recursion. Not pruning invalid branches, which causes TLE on large inputs.

Real-world use case: Generating all possible configurations for load balancer rules, or solving constraint satisfaction problems like scheduling with dependencies.

Problems: Permutations, Combinations, N-Queens, Sudoku Solver, Combination Sum

9. Dynamic Programming

When to use: Optimization problems with overlapping subproblems and optimal substructure. If the brute force solution involves the same subproblem being solved multiple times, DP eliminates that redundancy.

Key insight: Identify the state (what changes between subproblems), the recurrence relation (how to build the current state from previous states), and the base case. Start with top-down memoization if you are unsure, then convert to bottom-up for space optimization.

int[] dp = new int[n + 1];
dp[0] = base case;
for (int i = 1; i <= n; i++) {
    dp[i] = recurrence relation;
}
return dp[n];

Walkthrough: For Climbing Stairs (n=5): dp[0]=1, dp[1]=1. dp[2] = dp[1]+dp[0] = 2. dp[3] = dp[2]+dp[1] = 3. dp[4] = dp[3]+dp[2] = 5. dp[5] = dp[4]+dp[3] = 8. You can reach step 5 in 8 ways.

Common mistakes: Choosing the wrong state definition—too many dimensions makes the solution too slow, too few makes it incorrect. Not handling base cases properly. Using recursion without memoization (leads to exponential time).

Real-world use case: Resource allocation optimization, shortest path with weighted edges, optimal pricing strategies, sequence alignment in bioinformatics.

Problems: Climbing Stairs, Coin Change, Longest Common Subsequence, Edit Distance, Knapsack

10. Greedy

When to use: Problems where making the locally optimal choice at each step leads to a globally optimal solution. Greedy works when the problem has greedy choice property and optimal substructure, but no overlapping subproblems.

Key insight: Prove that the greedy choice is always safe. Often this involves sorting by a specific criterion first. If you cannot prove the greedy property, try DP instead.

Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int count = 0, end = Integer.MIN_VALUE;
for (int[] interval : intervals) {
    if (interval[0] >= end) {
        count++;
        end = interval[1];
    }
}

Walkthrough: For Activity Selection, sorting by end time ensures you always pick the activity that finishes earliest, leaving maximum room for subsequent activities. This greedy choice is provably optimal.

Common mistakes: Applying greedy to problems that require DP (like 0/1 Knapsack). Not proving the greedy property before committing to the approach. Sorting by the wrong criterion.

Real-world use case: Huffman coding, job scheduling to maximize throughput, minimizing late deliveries with earliest deadline first.

Problems: Jump Game, Activity Selection, Task Scheduler, Gas Station

11. Heap / Priority Queue

When to use: Finding the kth largest or smallest element, merging sorted collections, or maintaining a dynamic set where you need quick access to the extreme element. A min-heap of size k tracks the k largest elements seen so far.

Key insight: A heap gives O(log n) insert and O(1) peek. For top-k problems, maintain a heap of size k—when it grows beyond k, remove the smallest (for top-k largest). This is more efficient than sorting the entire array.

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int num : nums) {
    pq.offer(num);
    if (pq.size() > k) pq.poll();
}
return pq.peek();

Walkthrough: For Kth Largest in [3,2,1,5,6,4] with k=2: insert 3 (heap=[3]), insert 2 (heap=[2,3]), insert 1 (heap=[1,2,3], remove 1 → [2,3]), insert 5 (remove 2 → [3,5]), insert 6 (remove 3 → [5,6]), insert 4 (remove 4, wait—heap is [4,5,6], remove 4 → [5,6]). Peek returns 5.

Common mistakes: Using a max-heap when you need a min-heap or vice versa. Not removing elements when the heap exceeds size k, which defeats the purpose of the optimization.

Real-world use case: Real-time leaderboards in gaming, merging K sorted log streams, finding the median of a data stream.

Problems: Kth Largest Element, Merge K Sorted Lists, Top K Frequent Elements, Find Median from Data Stream

12. Union-Find

When to use: Problems involving connected components, determining if two elements are in the same group, or cycle detection in undirected graphs. Union-Find is particularly efficient when you have a stream of union and find operations.

Key insight: Path compression and union by rank keep operations nearly O(1). Without these optimizations, a sequence of operations can degrade to O(n) per operation.

int[] parent;
int[] rank;

void union(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return;
    if (rank[px] < rank[py]) { parent[px] = py; }
    else if (rank[px] > rank[py]) { parent[py] = px; }
    else { parent[py] = px; rank[px]++; }
}

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

Walkthrough: For Number of Provinces, each person starts as their own parent. When you process an edge between two people, you union their sets. The number of distinct parents at the end is the number of provinces.

Common mistakes: Forgetting path compression, which causes the tree to become unbalanced. Not initializing parent[i] = i for every element. Confusing union by rank with union by size—they achieve the same goal but with different logic.

Real-world use case: Network connectivity analysis, friend circle recommendations in social networks, Kruskal's minimum spanning tree algorithm.

Problems: Number of Provinces, Redundant Connection, Accounts Merge, Largest Component Size by Common Factor

13. Trie

When to use: Prefix search, word games, autocomplete systems, or any problem where you need to store and retrieve strings efficiently by their characters. A Trie avoids redundant comparisons by sharing prefixes.

Key insight: Each node represents a character. The path from root to a node spells a prefix. Marking nodes as "end of word" lets you distinguish between complete words and mere prefixes.

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd;
}

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;
}

Walkthrough: For Word Search II, you build a Trie from all words, then DFS the grid. At each cell, you follow the Trie branch—if the character matches, you continue deeper. If you reach an isEnd node, you found a word. This avoids checking every word independently.

Common mistakes: Not handling the case where a word is a prefix of another word (e.g., "app" and "apple"). Not unmarking isEnd when deleting words. Using a HashMap for children instead of an array when the character set is known and small.

Real-world use case: Autocomplete in search engines, IP routing tables, spell checkers, word games like Boggle.

Problems: Implement Trie, Word Search II, Autocomplete System, Palindrome Pairs

14. Stack

When to use: Problems involving matching pairs (parentheses, brackets), evaluating expressions, or maintaining a sequence where the most recent element is the most relevant. A stack naturally tracks "undo" operations and nested structures.

Key insight: Push elements onto the stack as you encounter them. Pop when you find a matching condition. The stack always holds elements that have not yet been matched.

Stack<Integer> stack = new Stack<>();
for (int num : nums) {
    while (!stack.isEmpty() && stack.peek() < num) {
        result[stack.pop()] = num;
    }
    stack.push(num);
}

Walkthrough: For Valid Parentheses with "()[]{}": push '(', push nothing (match found, pop '('), push '[', no match, push ']', match found, pop '[', push '{', push '}', match found, pop '{'. Stack is empty at the end—valid.

Common mistakes: Not checking if the stack is empty before peeking (causes error). Using the wrong comparison direction (checking < when you need >). Forgetting that Java's Stack class extends Vector and is synchronized—for interview purposes it works, but in production prefer ArrayDeque.

Real-world use case: Undo/redo functionality in text editors, evaluating mathematical expressions, validating nested configuration files.

Problems: Valid Parentheses, Next Greater Element, Simplify Path, Mini Parser

15. Monotonic Stack

When to use: Next greater or smaller element problems. A monotonic stack maintains elements in sorted order (either increasing or decreasing). When a new element violates the monotonic property, you pop and process the removed elements.

Key insight: Each element is pushed and popped at most once, giving O(n) total time. The stack at any point contains elements that have not yet found their answer.

int[] result = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = n - 1; i >= 0; i--) {
    while (!stack.isEmpty() && stack.peek() <= nums[i]) {
        stack.pop();
    }
    result[i] = stack.isEmpty() ? -1 : stack.peek();
    stack.push(nums[i]);
}

Walkthrough: For Daily Temperatures [73,74,75,71,69,72,76,73], iterate right to left. For 73 (last element), stack is empty, result is 0. For 76, stack=[76], 73 < 76, so result for 73 is 1. Continue until you fill all results.

Common mistakes: Iterating in the wrong direction—left-to-right gives next greater to the right, right-to-left gives next greater to the left. Forgetting to handle the empty stack case (answer is -1 or 0). Not popping elements that are equal to the current one when the problem requires strict inequality.

Real-world use case: Stock price analysis (finding next day with higher price), temperature forecasting,CPU task scheduling where you need the next faster processor.

Problems: Daily Temperatures, Next Greater Element, Largest Rectangle in Histogram, Trapping Rain Water

Pattern Selection Guide

Use this decision tree when you encounter a new problem:

1. Is the data sorted or can it be sorted? → Two Pointers or Binary Search
2. Is it about a contiguous subarray or substring? → Sliding Window
3. Is it a linked list with potential cycles? → Fast & Slow Pointers
4. Are there overlapping intervals? → Merge Intervals
5. Is it a graph or tree traversal? → DFS (use when you need all paths) or BFS (use when you need shortest path)
6. Do you need to generate all possible combinations? → Backtracking
7. Is it an optimization with repeated subproblems? → Dynamic Programming
8. Can you make a locally optimal choice at each step? → Greedy
9. Do you need the kth element from a dynamic set? → Heap
10. Are there connected components to track? → Union-Find
11. Is it about string prefixes? → Trie
12. Is it about matching or nesting structures? → Stack
13. Do you need the next greater/smaller element? → Monotonic Stack

Tips for Recognizing Patterns in Interviews

Read the constraints first. Constraints often hint at the expected complexity. O(n log n) suggests sorting plus a linear scan. O(n) with a constraint on values suggests counting or bucket sort. O(n²) suggests DP or brute force with pruning.

Look for keywords. "Contiguous" screams sliding window. "Sorted" suggests two pointers or binary search. "Shortest path in unweighted" means BFS. "All combinations" or "all possible" means backtracking. "Optimal" with overlapping subproblems means DP.

Ask clarifying questions. Is the input sorted? Are there duplicates? What are the size constraints? These answers often narrow down which pattern applies.

Draw examples. Work through 2-3 small examples by hand before coding. This reveals the pattern naturally—watch how the algorithm behaves on paper.

Start with brute force. If you cannot identify the pattern, describe the brute force approach first. Then look for optimizations: can you eliminate redundant work (DP), exploit order (binary search/two pointers), or prune the search space (backtracking)?

Practice Problems by Difficulty

Beginner: Two Sum II, Valid Parentheses, Maximum Subarray, Binary Search, Reverse Linked List

Intermediate: 3Sum, Group Anagrams, Course Schedule, Kth Largest Element, Word Break

Advanced: Trapping Rain Water, Alien Dictionary, Merge K Sorted Lists, Minimum Window Substring, N-Queens

Resources

• DSA Roadmap - Complete learning path
• Practice Problems - Practice problems by pattern
• DSA Cheat Sheet - Quick reference
• System Design Guide - Architecture rounds
• Java DSA Templates - Java implementations