LeetCode Patterns Cheat Sheet 2026

All 21 algorithmic patterns — when-to-use signals, time & space complexity, and code templates in Python, Java & C++. One page. Free forever.

By Syed Peera Saheb · Updated July 2026 · Full pattern guide →

Pattern guide with templates

Pattern Recognition Quick Reference

When you see these signals in a problem statement, reach for the corresponding pattern immediately. Recognizing the pattern is half the work — the template handles the rest.

Problem signal	Pattern to use	Complexity
Finding max/min subarray of size k	Sliding Window	O(n)
Pair sum in sorted array	Two Pointers	O(n)
Searching in sorted array	Binary Search	O(log n)
Two sum (find complement)	Hash Map / Set	O(1) average for lookup/insert, O(n) space
Tree height/depth	Trees / DFS	O(n)
Shortest path in unweighted graph	Queue / BFS	O(V + E) for graphs, O(n) for trees
Fibonacci and climbing stairs	Dynamic Programming	Depends on state space
Valid parentheses / bracket matching	Stack	O(n)
Kth largest/smallest element	Heap / Priority Queue	O(log n) insert/delete, O(1) peek
Generate all permutations/combinations/subsets	Backtracking	Exponential
Merge intervals	Intervals	O(n log n)
Range sum queries	Prefix Sum	O(n) build, O(1) per query
Number of islands	Graphs	O(V + E)
Implement Trie (insert/search/startsWith)	Trie	O(m) per operation where m is word length
Number of connected components	Union Find	O(α(n)) per operation
Largest rectangle in histogram	Monotonic Stack	O(n)
Course Schedule (detect cycle)	Topological Sort	O(V + E)
Detecting cycles (Floyd's algorithm)	Linked List	O(n)
Jump game	Greedy	O(n log n)
Single number (XOR trick)	Bit Manipulation	O(1) or O(log n) for most operations
Rotate image 90°	Matrix	O(m × n)

All 21 Patterns — Complete Reference

01

Sliding Window

Efficiently process subarrays or substrings of a fixed or variable size.

Time: O(n) Space: O(k) where k is the window size or alphabet size

When to use

Finding max/min subarray of size k
Longest substring without repeating characters
Minimum window containing all characters

Code template

def sliding_window(arr, k):
    left = 0
    result = 0
    window_state = {}  # track window contents

    for right in range(len(arr)):
        # Expand window: add arr[right]

        # Shrink window when constraint violated
        while False:  # replace with invalid condition
            # Remove arr[left] from state
            left += 1

        # Update result
        result = max(result, right - left + 1)
    return result

public int slidingWindow(int[] arr, int k) {
    int left = 0, result = 0;
    Map<Integer, Integer> windowState = new HashMap<>();

    for (int right = 0; right < arr.length; right++) {
        // Expand window: add arr[right]

        // Shrink window when constraint violated
        while (false) { // replace with invalid condition
            // Remove arr[left] from state
            left++;
        }

        // Update result
        result = Math.max(result, right - left + 1);
    }
    return result;
}

int slidingWindow(vector<int>& arr, int k) {
    int left = 0, result = 0;
    unordered_map<int, int> windowState;

    for (int right = 0; right < (int)arr.size(); right++) {
        // Expand window: add arr[right]

        // Shrink window when constraint violated
        while (false) { // replace with invalid condition
            // Remove arr[left] from state
            left++;
        }

        // Update result
        result = max(result, right - left + 1);
    }
    return result;
}

Full guide + practice problems →

02

Two Pointers

Use two indices moving toward each other or in the same direction to solve linear problems.

Time: O(n) Space: O(1)

When to use

Pair sum in sorted array
Removing duplicates in-place
Container with most water

Code template

def two_pointers(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1
        else:
            right -= 1
    return []

public int[] twoPointers(int[] arr, int target) {
    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--;
    }
    return new int[]{};
}

vector<int> twoPointers(vector<int>& arr, int target) {
    int left = 0, right = (int)arr.size() - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return {left, right};
        else if (sum < target) left++;
        else right--;
    }
    return {};
}

Full guide + practice problems →

03

Binary Search

Halve the search space each step to find an element or boundary in O(log n).

Time: O(log n) Space: O(1) iterative, O(log n) recursive

When to use

Searching in sorted array
Finding first/last occurrence
Binary search on answer (min max problems)

Code template

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Binary search on answer
def binary_search_answer(lo, hi):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

public int binarySearch(int[] arr, int target) {
    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;
    }
    return -1;
}

// Binary search on answer
public int binarySearchAnswer(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = (int)arr.size() - 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;
    }
    return -1;
}

// Binary search on answer
int binarySearchAnswer(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Full guide + practice problems →

04

Hash Map / Set

Trade space for time using O(1) lookup to find pairs, duplicates, and frequencies.

Time: O(1) average for lookup/insert, O(n) space Space: O(n)

When to use

Two sum (find complement)
Anagram grouping
Longest consecutive sequence

Code template

from collections import Counter

# Frequency count
freq = Counter(arr)

# Two sum
def two_sum(nums, target):
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

// Frequency count
Map<Integer, Integer> freq = new HashMap<>();
for (int x : arr) freq.merge(x, 1, Integer::sum);

// Two sum
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>(); // value -> index
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (seen.containsKey(complement))
            return new int[]{seen.get(complement), i};
        seen.put(nums[i], i);
    }
    return new int[]{};
}

// Frequency count
unordered_map<int, int> freq;
for (int x : arr) freq[x]++;

// Two sum
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen; // value -> index
    for (int i = 0; i < (int)nums.size(); i++) {
        int complement = target - nums[i];
        if (seen.count(complement))
            return {seen[complement], i};
        seen[nums[i]] = i;
    }
    return {};
}

Full guide + practice problems →

05

Trees / DFS

Recursive and iterative depth-first traversal for tree structure problems.

Time: O(n) Space: O(h) where h is height; O(n) worst case (skewed)

When to use

Tree height/depth
Path sum problems
Lowest common ancestor

Code template

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Generic DFS template
def dfs(node):
    if not node:
        return  # base case
    # Pre-order: process node here
    dfs(node.left)
    # In-order: process node here
    dfs(node.right)
    # Post-order: process node here

# Path sum
def has_path_sum(root, target):
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == target
    return (has_path_sum(root.left, target - root.val) or
            has_path_sum(root.right, target - root.val))

class TreeNode {
    int val; TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

// Generic DFS template
public void dfs(TreeNode node) {
    if (node == null) return; // base case
    // Pre-order: process node here
    dfs(node.left);
    // In-order: process node here
    dfs(node.right);
    // Post-order: process node here
}

// Path sum
public boolean hasPathSum(TreeNode root, int target) {
    if (root == null) return false;
    if (root.left == null && root.right == null) return root.val == target;
    return hasPathSum(root.left, target - root.val) ||
           hasPathSum(root.right, target - root.val);
}

struct TreeNode {
    int val; TreeNode *left, *right;
    TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

// Generic DFS template
void dfs(TreeNode* node) {
    if (!node) return; // base case
    // Pre-order: process node here
    dfs(node->left);
    // In-order: process node here
    dfs(node->right);
    // Post-order: process node here
}

// Path sum
bool hasPathSum(TreeNode* root, int target) {
    if (!root) return false;
    if (!root->left && !root->right) return root->val == target;
    return hasPathSum(root->left, target - root->val) ||
           hasPathSum(root->right, target - root->val);
}

Full guide + practice problems →

06

Queue / BFS

Level-by-level traversal for shortest paths and layer-based problems.

Time: O(V + E) for graphs, O(n) for trees Space: O(V) for the queue

When to use

Shortest path in unweighted graph
Level-order tree traversal
Rotting oranges / island flooding

Code template

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        # process node

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

public void bfs(Map<Integer, List<Integer>> graph, int start) {
    Set<Integer> visited = new HashSet<>();
    visited.add(start);
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        // process node

        for (int neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
}

void bfs(unordered_map<int, vector<int>>& graph, int start) {
    unordered_set<int> visited = {start};
    queue<int> q;
    q.push(start);

    while (!q.empty()) {
        int node = q.front(); q.pop();
        // process node

        for (int neighbor : graph[node]) {
            if (!visited.count(neighbor)) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}

Full guide + practice problems →

07

Dynamic Programming

Break problems into overlapping subproblems and build up solutions bottom-up.

Time: Depends on state space Space: O(n) with space optimization

When to use

Fibonacci and climbing stairs
Knapsack variants
Longest common subsequence

Code template

# 1D DP (Climbing Stairs)
def climb_stairs(n):
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# 2D DP (Unique Paths)
def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

// 1D DP (Climbing Stairs)
public int climbStairs(int n) {
    int[] dp = new int[n + 1];
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}

// 2D DP (Unique Paths)
public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int[] row : dp) Arrays.fill(row, 1);
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
    return dp[m-1][n-1];
}

// 1D DP (Climbing Stairs)
int climbStairs(int n) {
    vector<int> dp(n + 1);
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}

// 2D DP (Unique Paths)
int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
    return dp[m-1][n-1];
}

Full guide + practice problems →

08

Stack

LIFO structure for matching brackets, evaluating expressions, and monotonic problems.

Time: O(n) Space: O(n)

When to use

Valid parentheses / bracket matching
Next greater element
Daily temperatures

Code template

# Monotonic decreasing stack (next greater element)
def next_greater(arr):
    result = [-1] * len(arr)
    stack = []  # stores indices

    for i in range(len(arr)):
        while stack and arr[stack[-1]] < arr[i]:
            result[stack.pop()] = arr[i]
        stack.append(i)
    return result

// Monotonic decreasing stack (next greater element)
public int[] nextGreater(int[] arr) {
    int[] result = new int[arr.length];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>(); // stores indices

    for (int i = 0; i < arr.length; i++) {
        while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
            result[stack.pop()] = arr[i];
        }
        stack.push(i);
    }
    return result;
}

// Monotonic decreasing stack (next greater element)
vector<int> nextGreater(vector<int>& arr) {
    vector<int> result(arr.size(), -1);
    stack<int> st; // stores indices

    for (int i = 0; i < (int)arr.size(); i++) {
        while (!st.empty() && arr[st.top()] < arr[i]) {
            result[st.top()] = arr[i];
            st.pop();
        }
        st.push(i);
    }
    return result;
}

Full guide + practice problems →

09

Heap / Priority Queue

Efficiently track the k-th largest/smallest element or merge sorted sequences.

Time: O(log n) insert/delete, O(1) peek Space: O(n)

When to use

Kth largest/smallest element
Merge k sorted lists
Task scheduler

Code template

import heapq

# Min-heap
min_heap = []
heapq.heappush(min_heap, val)
top = heapq.heappop(min_heap)   # smallest
peek = min_heap[0]

# Max-heap (negate values)
max_heap = []
heapq.heappush(max_heap, -val)
top = -heapq.heappop(max_heap)  # largest

# Kth largest element
def kth_largest(nums, k):
    return heapq.nlargest(k, nums)[-1]

// Min-heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(val);
int top = minHeap.poll();   // smallest
int peek = minHeap.peek();

// Max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(val);
int largest = maxHeap.poll();

// Kth largest element
public int kthLargest(int[] nums, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int n : nums) {
        pq.offer(n);
        if (pq.size() > k) pq.poll();
    }
    return pq.peek();
}

// Min-heap
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(val);
int top = minHeap.top(); minHeap.pop();  // smallest

// Max-heap (default)
priority_queue<int> maxHeap;
maxHeap.push(val);
int largest = maxHeap.top(); maxHeap.pop();

// Kth largest element
int kthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int n : nums) {
        pq.push(n);
        if ((int)pq.size() > k) pq.pop();
    }
    return pq.top();
}

Full guide + practice problems →

10

Backtracking

Explore all possibilities recursively, pruning invalid branches early.

Time: Exponential Space: O(n) call stack depth

When to use

Generate all permutations/combinations/subsets
N-Queens
Sudoku solver

Code template

def backtrack(result, current, start, nums):
    result.append(current[:])  # record current state

    for i in range(start, len(nums)):
        # Prune: skip duplicates
        if i > start and nums[i] == nums[i-1]:
            continue
        current.append(nums[i])              # choose
        backtrack(result, current, i + 1, nums)  # explore
        current.pop()                        # un-choose

public void backtrack(List<List<Integer>> result, List<Integer> current, int start, int[] nums) {
    result.add(new ArrayList<>(current)); // record current state

    for (int i = start; i < nums.length; i++) {
        // Prune: skip duplicates
        if (i > start && nums[i] == nums[i-1]) continue;

        current.add(nums[i]);                       // choose
        backtrack(result, current, i + 1, nums);    // explore
        current.remove(current.size() - 1);         // un-choose
    }
}

void backtrack(vector<vector<int>>& result, vector<int>& current, int start, vector<int>& nums) {
    result.push_back(current); // record current state

    for (int i = start; i < (int)nums.size(); i++) {
        // Prune: skip duplicates
        if (i > start && nums[i] == nums[i-1]) continue;

        current.push_back(nums[i]);                  // choose
        backtrack(result, current, i + 1, nums);     // explore
        current.pop_back();                          // un-choose
    }
}

Full guide + practice problems →

11

Intervals

Merge, insert, and count overlapping intervals after sorting by start time.

Time: O(n log n) Space: O(n)

When to use

Merge intervals
Insert interval
Meeting rooms (can attend all?)

Code template

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        last = merged[-1]
        if start <= last[1]:
            last[1] = max(last[1], end)  # overlap: extend
        else:
            merged.append([start, end])  # no overlap: new interval
    return merged

public int[][] mergeIntervals(int[][] 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]) {
            last[1] = Math.max(last[1], intervals[i][1]); // overlap: extend
        } else {
            merged.add(intervals[i]); // no overlap: new interval
        }
    }
    return merged.toArray(new int[0][]);
}

vector<vector<int>> mergeIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> merged = {intervals[0]};

    for (int i = 1; i < (int)intervals.size(); i++) {
        auto& last = merged.back();
        if (intervals[i][0] <= last[1]) {
            last[1] = max(last[1], intervals[i][1]); // overlap: extend
        } else {
            merged.push_back(intervals[i]); // no overlap: new interval
        }
    }
    return merged;
}

Full guide + practice problems →

12

Prefix Sum

Precompute cumulative sums to answer range queries in O(1).

Time: O(n) build, O(1) per query Space: O(n)

When to use

Range sum queries
Subarray sum equals k
Number of subarrays with given sum

Code template

def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i in range(len(arr)):
        prefix[i + 1] = prefix[i] + arr[i]
    return prefix

def range_sum(prefix, l, r):
    return prefix[r + 1] - prefix[l]  # inclusive [l, r]

public int[] buildPrefix(int[] arr) {
    int[] prefix = new int[arr.length + 1];
    for (int i = 0; i < arr.length; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}

public int rangeSum(int[] prefix, int l, int r) {
    return prefix[r + 1] - prefix[l]; // inclusive [l, r]
}

vector<int> buildPrefix(vector<int>& arr) {
    vector<int> prefix(arr.size() + 1, 0);
    for (int i = 0; i < (int)arr.size(); i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}

int rangeSum(vector<int>& prefix, int l, int r) {
    return prefix[r + 1] - prefix[l]; // inclusive [l, r]
}

Full guide + practice problems →

13

Graphs

DFS and BFS on adjacency lists for connectivity, cycles, and path problems.

Time: O(V + E) Space: O(V) for visited set

When to use

Number of islands
Clone graph
Course schedule (cycle detection)

Code template

def num_islands(grid):
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == '1':
                dfs(grid, r, c)
                count += 1
    return count

def dfs(grid, r, c):
    if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] != '1':
        return
    grid[r][c] = '0'  # mark visited
    dfs(grid, r + 1, c)
    dfs(grid, r - 1, c)
    dfs(grid, r, c + 1)
    dfs(grid, r, c - 1)

public int numIslands(char[][] grid) {
    int count = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == '1') {
                dfs(grid, r, c);
                count++;
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1') return;
    grid[r][c] = '0'; // mark visited
    dfs(grid, r+1, c); dfs(grid, r-1, c);
    dfs(grid, r, c+1); dfs(grid, r, c-1);
}

void dfs(vector<vector<char>>& grid, int r, int c) {
    if (r < 0 || r >= (int)grid.size() || c < 0 || c >= (int)grid[0].size() || grid[r][c] != '1') return;
    grid[r][c] = '0'; // mark visited
    dfs(grid, r+1, c); dfs(grid, r-1, c);
    dfs(grid, r, c+1); dfs(grid, r, c-1);
}

int numIslands(vector<vector<char>>& grid) {
    int count = 0;
    for (int r = 0; r < (int)grid.size(); r++)
        for (int c = 0; c < (int)grid[0].size(); c++)
            if (grid[r][c] == '1') { dfs(grid, r, c); count++; }
    return count;
}

Full guide + practice problems →

14

Trie

Prefix tree for efficient string search, autocomplete, and word matching.

Time: O(m) per operation where m is word length Space: O(ALPHABET_SIZE × m × n)

When to use

Implement Trie (insert/search/startsWith)
Word search II
Design add/search words

Code template

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;
}

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

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch)) return false;
            node = node.children.get(ch);
        }
        return node.isEnd;
    }
}

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEnd = false;
};

class Trie {
    TrieNode* root = new TrieNode();
public:
    void insert(const string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch))
                node->children[ch] = new TrieNode();
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(const string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) return false;
            node = node->children[ch];
        }
        return node->isEnd;
    }
};

Full guide + practice problems →

15

Union Find

Disjoint set union for grouping, connectivity, and cycle detection.

Time: O(α(n)) per operation Space: O(n)

When to use

Number of connected components
Redundant connection (cycle detection)
Accounts merge

Code template

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        elif self.rank[px] > self.rank[py]:
            self.parent[py] = px
        else:
            self.parent[py] = px
            self.rank[px] += 1
        return True

class UnionFind {
    int[] parent, rank;

    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // path compression
        return parent[x];
    }

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

class UnionFind {
    vector<int> parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }

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

    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) swap(px, py);
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        return true;
    }
};

Full guide + practice problems →

16

Monotonic Stack

Maintain a sorted stack to find next/previous greater or smaller elements in O(n).

Time: O(n) Space: O(n)

When to use

Largest rectangle in histogram
Trapping rain water
Daily temperatures

Code template

# Largest Rectangle in Histogram
def largest_rectangle(heights):
    stack = [-1]
    max_area = 0

    for i in range(len(heights) + 1):
        h = 0 if i == len(heights) else heights[i]
        while stack[-1] != -1 and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

// Largest Rectangle in Histogram
public int largestRectangle(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(-1);
    int maxArea = 0;

    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);
    }
    return maxArea;
}

// Largest Rectangle in Histogram
int largestRectangle(vector<int>& heights) {
    stack<int> st;
    st.push(-1);
    int maxArea = 0;

    for (int i = 0; i <= (int)heights.size(); i++) {
        int h = (i == (int)heights.size()) ? 0 : heights[i];
        while (st.top() != -1 && heights[st.top()] >= h) {
            int height = heights[st.top()]; st.pop();
            int width = i - st.top() - 1;
            maxArea = max(maxArea, height * width);
        }
        st.push(i);
    }
    return maxArea;
}

Full guide + practice problems →

17

Topological Sort

Linear ordering of vertices in a DAG — essential for dependency problems.

Time: O(V + E) Space: O(V)

When to use

Course Schedule (detect cycle)
Course Schedule II (ordering)
Alien dictionary

Code template

from collections import deque

# Kahn's Algorithm (BFS-based)
def topo_sort(n, prerequisites):
    in_degree = [0] * n
    adj = [[] for _ in range(n)]

    for a, b in prerequisites:
        adj[b].append(a)
        in_degree[a] += 1

    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for nei in adj[node]:
            in_degree[nei] -= 1
            if in_degree[nei] == 0:
                queue.append(nei)

    return order if len(order) == n else []  # empty = cycle exists

// Kahn's Algorithm (BFS-based)
public int[] topoSort(int n, int[][] prerequisites) {
    int[] inDegree = new int[n];
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

    for (int[] edge : prerequisites) {
        adj.get(edge[1]).add(edge[0]);
        inDegree[edge[0]]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) if (inDegree[i] == 0) queue.offer(i);

    int[] order = new int[n];
    int idx = 0;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        order[idx++] = node;
        for (int nei : adj.get(node)) {
            if (--inDegree[nei] == 0) queue.offer(nei);
        }
    }
    return idx == n ? order : new int[]{}; // empty = cycle exists
}

// Kahn's Algorithm (BFS-based)
vector<int> topoSort(int n, vector<vector<int>>& prerequisites) {
    vector<int> inDegree(n, 0);
    vector<vector<int>> adj(n);

    for (auto& edge : prerequisites) {
        adj[edge[1]].push_back(edge[0]);
        inDegree[edge[0]]++;
    }

    queue<int> q;
    for (int i = 0; i < n; i++) if (inDegree[i] == 0) q.push(i);

    vector<int> order;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        order.push_back(node);
        for (int nei : adj[node]) {
            if (--inDegree[nei] == 0) q.push(nei);
        }
    }
    return (int)order.size() == n ? order : vector<int>{}; // empty = cycle exists
}

Full guide + practice problems →

18

Linked List

Pointer manipulation for in-place list operations without extra memory.

Time: O(n) Space: O(1) for in-place operations

When to use

Detecting cycles (Floyd's algorithm)
Reversing a linked list
Finding middle of list

Code template

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Reverse linked list in-place
def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

# Fast / slow pointer
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

class ListNode {
    int val; ListNode next;
    ListNode(int val) { this.val = val; }
}

// Reverse linked list in-place
public ListNode reverse(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// Fast / slow pointer
public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

struct ListNode {
    int val; ListNode* next;
    ListNode(int val) : val(val), next(nullptr) {}
};

// Reverse linked list in-place
ListNode* reverse(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// Fast / slow pointer
bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

Full guide + practice problems →

19

Greedy

Make the locally optimal choice at each step to achieve a globally optimal solution.

Time: O(n log n) Space: O(1)

When to use

Jump game
Gas station
Meeting rooms

Code template

# Jump Game II — greedy
def jump(nums):
    jumps = current_end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
    return jumps

// Jump Game II — greedy
public int jump(int[] nums) {
    int jumps = 0, currentEnd = 0, farthest = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;
        }
    }
    return jumps;
}

// Jump Game II — greedy
int jump(vector<int>& nums) {
    int jumps = 0, currentEnd = 0, farthest = 0;
    for (int i = 0; i < (int)nums.size() - 1; i++) {
        farthest = max(farthest, i + nums[i]);
        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;
        }
    }
    return jumps;
}

Full guide + practice problems →

20

Bit Manipulation

Use bitwise operations to solve XOR, subset, and number theory problems.

Time: O(1) or O(log n) for most operations Space: O(1)

When to use

Single number (XOR trick)
Number of 1 bits (Hamming weight)
Counting bits

Code template

# Common bit tricks
get_bit = lambda n, i: (n >> i) & 1
set_bit = lambda n, i: n | (1 << i)
clear_bit = lambda n, i: n & ~(1 << i)
is_power_of_2 = lambda n: n > 0 and (n & (n - 1)) == 0
lowest_set_bit = lambda n: n & (-n)
clear_lowest_bit = lambda n: n & (n - 1)

# XOR: find single number where all others appear twice
from functools import reduce
single_number = lambda nums: reduce(lambda a, b: a ^ b, nums)

// Common bit tricks
int getBit(int n, int i) { return (n >> i) & 1; }
int setBit(int n, int i) { return n | (1 << i); }
int clearBit(int n, int i) { return n & ~(1 << i); }
boolean isPowerOf2(int n) { return n > 0 && (n & (n - 1)) == 0; }
int lowestSetBit(int n) { return n & (-n); }
int clearLowestBit(int n) { return n & (n - 1); }

// XOR: find single number where all others appear twice
public int singleNumber(int[] nums) {
    int result = 0;
    for (int n : nums) result ^= n;
    return result;
}

// Common bit tricks
int getBit(int n, int i) { return (n >> i) & 1; }
int setBit(int n, int i) { return n | (1 << i); }
int clearBit(int n, int i) { return n & ~(1 << i); }
bool isPowerOf2(int n) { return n > 0 && (n & (n - 1)) == 0; }
int lowestSetBit(int n) { return n & (-n); }
int clearLowestBit(int n) { return n & (n - 1); }

// XOR: find single number where all others appear twice
int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int n : nums) result ^= n;
    return result;
}

Full guide + practice problems →

21

Matrix

Navigate 2D grids with DFS/BFS, rotation, spiral traversal, and flood fill.

Time: O(m × n) Space: O(m × n) for BFS/DFS, O(1) for in-place tricks

When to use

Rotate image 90°
Spiral matrix traversal
Set matrix zeros

Code template

from collections import deque

DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def bfs_grid(grid, start_r, start_c):
    rows, cols = len(grid), len(grid[0])
    queue = deque([(start_r, start_c)])
    visited = {(start_r, start_c)}

    while queue:
        r, c = queue.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc))

int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};

public void bfsGrid(int[][] grid, int startR, int startC) {
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    queue.offer(new int[]{startR, startC});
    visited.add(startR + "," + startC);

    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int r = curr[0], c = curr[1];
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            String key = nr + "," + nc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited.contains(key)) {
                visited.add(key);
                queue.offer(new int[]{nr, nc});
            }
        }
    }
}

int DIRS[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

void bfsGrid(vector<vector<int>>& grid, int startR, int startC) {
    int rows = grid.size(), cols = grid[0].size();
    queue<pair<int,int>> q;
    set<pair<int,int>> visited;
    q.push({startR, startC});
    visited.insert({startR, startC});

    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (auto& d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited.count({nr, nc})) {
                visited.insert({nr, nc});
                q.push({nr, nc});
            }
        }
    }
}

Full guide + practice problems →

Ready to practice?

Use the full Coding Interview Patterns guide to study each pattern in depth, then solve curated problems from our problem set. Filter by company to target the exact patterns asked at Google, Meta, Amazon, and Microsoft.

Browse 200+ Problems Blind 75 List NeetCode 150 Guide

Buy me a coffee