Skip to content

patterns.md

Latest commit

 

History

History
1434 lines (1118 loc) · 79 KB

patterns.md

File metadata and controls

1434 lines (1118 loc) · 79 KB
Raw

Coding interview patterns

For anyone who has covered the matching topic on Topics. Each of the 25 patterns below has the cues that give it away, a Python template to type from memory, and 6 to 10 free LeetCode problems, easy to hard.

Credit: The pattern approach and many cues come from Sean Prashad's LeetCode Patterns and Fahim ul Haq's 14 Patterns to Ace Any Coding Interview Question. Full credits are in Where these patterns come from.

How to use this page

  1. Learn the topic first. Patterns assume you know the data structure. Use Topics.
  2. Read the cues, then type the template from memory into a blank file and run it on the first problem.
  3. Solve the problems in order. The first 1 or 2 with the template open, the rest closed, on a timer: Easy 15 to 20 minutes, Medium 25 to 30, Hard 40 (time limits).
  4. Spend 2 days on one pattern and nothing else. "Spend two days doing ONLY sliding window problems. Then two days on binary search." (Jugal).
  5. Move on when you can name the pattern from the problem statement alone, not after reading the solution (Jugal's 60-day roadmap).
  6. Write a cheat-sheet page for the pattern with the pattern cheat sheet template: cues, your template, 2 anchor problems with a one-line insight each, and your usual bug.
  7. After all 25, mix. Open unseen problems and name the pattern within 3 minutes, before you write code. That is one of the checks in the readiness test.

Every linked problem is free on LeetCode (checked Oct 4, 2026). Every template below was run against test inputs before publishing.

Find the pattern from the problem

Read the problem, then scan this table. Sean Prashad's version of this idea, the "Helpful Tips" tab on LeetCode Patterns, says: "Based on the problem constraints, use these heuristics to identify possible approaches when unsure." Quoted rows come from that tab.

If the problem has Try Go to
A sorted array and a pair or triplet with a target Two pointers, binary search Two pointers
"Seen before", counts, anagram groups, a complement like target - x Hash map or set Hashing
A contiguous subarray or substring: longest, shortest, "at most K" Sliding window Sliding window
Count subarrays with sum k (negatives allowed), many range-sum queries Prefix sums plus a hash map Prefix sums
A linked list: cycle, middle, kth from the end Fast and slow pointers Fast and slow pointers
Reverse a list or part of it, O(1) memory In-place reversal Linked list reversal
Numbers 1 to n in an array of n, find missing or duplicate in O(1) space Cyclic sort Cyclic sort
Brackets, nested decoding, expression evaluation Stack Stack and monotonic stack
"If asked for next greater/smaller element" "Monotonic stack" Stack and monotonic stack
"If asked for sliding window max/min" "Monotonic queue" Stack and monotonic stack
Sorted or rotated input, "O(log n)", first or last position Binary search Binary search
"Smallest speed or capacity that works", "minimize the maximum" Binary search on the answer Binary search
[start, end] pairs: merge, overlap, rooms Sort, then merge or sweep Intervals
A tree, level by level BFS with a queue Tree BFS
A tree: depth, path sums, LCA, diameter, validate a BST DFS that returns values Tree DFS
A grid of land and water, regions, "can you reach" DFS or BFS Graph DFS
Fewest steps or minutes when every move costs the same BFS Graph BFS
"If asked for ordering/scheduling" (prerequisites) "Topological sort" Topological sort
"If asked for connectivity/grouping" "Union-Find, DFS" Union-find
Weighted edges, minimum total cost or time Dijkstra Shortest paths
"If asked for top/least K items", merge K sorted lists, running median Heaps Heaps
"If asked for all permutations/subsets" "Backtracking" Backtracking
A local choice you can prove is never worse Greedy Greedy
Many words, prefixes, autocomplete Trie Trie
"If asked to count bits or use XOR" "Bit manipulation" Bit manipulation
Rotate, spiral, change a matrix in place Matrix traversal Matrix traversal
"Implement a class" with O(1) get and put Combine structures Design a data structure
Count ways or best value, the same subproblems repeat Dynamic programming Dynamic programming
Nothing above fits "Map/Set for O(1) time & O(n) space" or "Sort input for O(nlogn) time and O(1) space" Hashing

The input size narrows it further: n up to 20 points to backtracking or bitmask DP, and n of 10^5 or more needs O(n log n) or better. Full table: Pick the target from the input size.

Hashing

Use it when:

  • You need "have I seen this before?" or a count in O(1).
  • You look for a complement, such as target - x.
  • You group items that share a property (anagrams, same letter pattern).
  • The input is not sorted and the brute force compares every pair.

Watch out: a hash map costs O(n) extra space. If the input is already sorted, two pointers does the job in O(1) space.

from collections import defaultdict


def two_sum(nums, target):
    seen = {}                                    # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:                   # check before you insert
            return [seen[target - x], i]
        seen[x] = i
    return []


def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        groups["".join(sorted(w))].append(w)     # a canonical key per group
    return list(groups.values())

O(n) time, O(n) space. Learn it: TIH: Hash table.

Problems, easy to hard:

Two pointers

Use it when:

  • The input is sorted (or you may sort it) and you need a pair or triplet that hits a target.
  • You remove, move or partition elements in place.
  • You compare from both ends, as in a palindrome check.

Watch out: for 3Sum, sort, fix one number, run two pointers on the rest, and skip duplicates at both levels.

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1                            # need a bigger sum
        else:
            right -= 1                           # need a smaller sum
    return []


def move_zeroes(nums):                           # read and write pointers
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1

O(n) per pass, O(1) extra space. 3Sum is O(n^2). Learn it: Hello Interview: Two pointers.

Problems, easy to hard:

Fast and slow pointers

Use it when:

  • A linked list asks for a cycle, the middle node, or a palindrome check.
  • A sequence where each value points to the next one (happy numbers, values used as indices).
  • You must use O(1) extra space.

Watch out: "kth node from the end" uses the same two pointers with a fixed gap of k, both moving one step at a time.

def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow                                  # second middle for even lengths


def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:                         # they met inside the cycle
            slow = head
            while slow is not fast:              # now move both one step at a time
                slow, fast = slow.next, fast.next
            return slow                          # the node where the cycle starts
    return None

O(n) time, O(1) space. Learn it: Hello Interview: Linked list.

Problems, easy to hard:

Sliding window

Use it when:

  • The answer is a contiguous subarray or substring.
  • You want the longest, shortest, count or maximum sum, often with "at most K" or "contains all of".
  • The window has a fixed size k.
  • You can update the window's state in O(1) when one element enters or leaves.

Watch out: negative numbers break "shrink while the sum is too big". Use prefix sums instead.

from collections import Counter


def longest_unique(s):                           # variable window
    count = Counter()
    left = best = 0
    for right, ch in enumerate(s):
        count[ch] += 1
        while count[ch] > 1:                     # window invalid: shrink from the left
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)       # window valid: record the answer
    return best


def max_sum_k(nums, k):                          # fixed window of size k
    window = best = sum(nums[:k])
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]  # add the new one, drop the old one
        best = max(best, window)
    return best

O(n) time: each index enters and leaves the window once. Learn it: Hello Interview: Fixed length and Variable length windows, or Aditya Verma's sliding window playlist.

Problems, easy to hard:

Prefix sums

Use it when:

  • You answer many range-sum queries on an array that does not change.
  • You count subarrays with sum k, divisible by k, or with equal 0s and 1s, and negatives are allowed.
  • You apply many range updates, then read once (a difference array).

Watch out: seed the hash map with {0: 1}. Without it you miss subarrays that start at index 0.

from collections import defaultdict


def subarray_sum(nums, k):                       # count subarrays that sum to k
    seen = defaultdict(int)
    seen[0] = 1                                  # the empty prefix
    total = count = 0
    for x in nums:
        total += x
        count += seen[total - k]                 # earlier prefixes that complete k
        seen[total] += 1
    return count


def prefix_sums(nums):
    pre = [0]
    for x in nums:
        pre.append(pre[-1] + x)
    return pre                                   # sum of nums[l..r] = pre[r + 1] - pre[l]

O(n) to build, O(1) per query. Learn it: Hello Interview: Prefix sum.

Problems, easy to hard:

Intervals

Use it when:

  • The input is a list of [start, end] pairs.
  • You merge, insert, intersect, or count overlapping intervals.
  • You need the minimum number of rooms, arrows or removals.

Watch out: ask whether [1, 2] and [2, 3] overlap (TIH: Interval). Sort by start to merge. Sort by end to keep the most non-overlapping intervals.

import heapq


def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])         # sort by start
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:    # overlaps the last one
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged


def min_rooms(intervals):
    ends = []                                    # min-heap of end times
    for start, end in sorted(intervals):
        if ends and ends[0] <= start:            # a room freed up: reuse it
            heapq.heapreplace(ends, end)
        else:
            heapq.heappush(ends, end)            # open a new room
    return len(ends)

O(n log n) for the sort. Learn it: Hello Interview: Intervals.

Problems, easy to hard:

Cyclic sort

Use it when:

  • The array holds n numbers in the range 1 to n (or 0 to n).
  • You must find the missing number, the duplicate, or the first missing positive.
  • O(1) extra space is required, so a set is not allowed.

Watch out: the other O(1)-space trick marks a value as seen by making nums[abs(x) - 1] negative. Know both.

def first_missing_positive(nums):
    n = len(nums)
    i = 0
    while i < n:
        target = nums[i] - 1                     # the index where nums[i] belongs
        if 0 <= target < n and nums[i] != nums[target]:
            nums[i], nums[target] = nums[target], nums[i]
        else:
            i += 1
    for i in range(n):
        if nums[i] != i + 1:                     # first index holding the wrong value
            return i + 1
    return n + 1

O(n) time, O(1) extra space. Learn it: Aditya Verma's swap sort (cyclic sort) playlist.

Problems, easy to hard:

Linked list reversal

Use it when:

  • You reverse a whole list, a section of it, or every k nodes.
  • You compare or reorder the two halves of a list.
  • You must use O(1) extra memory.

Watch out: use a dummy node in front of the head whenever the head can change.

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


def reverse(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next                           # 1. save the next node
        cur.next = prev                          # 2. flip the pointer
        prev, cur = cur, nxt                     # 3. move both forward
    return prev


def reverse_between(head, left, right):          # reverse positions left..right (1-indexed)
    dummy = ListNode(0, head)
    before = dummy
    for _ in range(left - 1):
        before = before.next
    prev, cur = None, before.next
    for _ in range(right - left + 1):
        nxt = cur.next
        cur.next = prev
        prev, cur = cur, nxt
    before.next.next = cur                       # old first node now points past the block
    before.next = prev                           # node before the block points to the new first
    return dummy.next

O(n) time, O(1) space. Learn it: TIH: Linked list or Striver's linked list playlist.

Problems, easy to hard:

Stack and monotonic stack

Use it when:

  • Stack: brackets must match, a structure is nested (3[a2[c]]), you evaluate an expression, or the most recent item decides what happens next. Sean Prashad: "If recursion is banned", use a stack.
  • Monotonic stack: you need the next greater or next smaller element, days until a warmer day, a stock span, or the largest rectangle.
  • Monotonic deque: you need the max or min of every sliding window.

Watch out: store indices on the stack, not values. You almost always need the distance between positions.

def is_valid(s):                                 # stack: matching
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack


def daily_temperatures(temps):                   # monotonic stack: next greater element
    answer = [0] * len(temps)
    stack = []                                   # indices, temperatures decreasing
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:    # t is the next warmer day for these
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

O(n) time: each index is pushed and popped once. Learn it: Hello Interview: Stack and Monotonic stack.

Problems, easy to hard:

Binary search

Use it when:

  • The input is sorted or rotated sorted, or the problem says "O(log n)".
  • You need the first or last position of a value, an insert position, or a peak.
  • On the answer: "minimize the maximum" or "the smallest speed, capacity or day count that works", and a yes/no check is monotonic: if x works, every larger x works too.

Watch out: use one template for every variant: find the first index where a condition becomes true, on a half-open range. Most bugs come from mixing templates. In Java and C++, write lo + (hi - lo) / 2 to avoid overflow.

def lower_bound(nums, target):                   # first index with nums[i] >= target
    lo, hi = 0, len(nums)                        # half-open range [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] >= target:                  # condition true: answer is mid or left of it
            hi = mid
        else:
            lo = mid + 1
    return lo


def min_eating_speed(piles, h):                  # binary search on the answer
    def can_finish(speed):
        return sum((p + speed - 1) // speed for p in piles) <= h

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_finish(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

O(log n) per search. On the answer: O(n log range). Learn it: the LeetCode Binary Search study plan (8 patterns, 42 questions) and zhijun_liao's binary search template post, which uses this same "first index where the condition holds" idea.

Problems, easy to hard:

Tree BFS

Use it when:

  • The problem says "level by level": level order, right side view, zigzag, averages per level, widest level.
  • You need the minimum depth, or to connect nodes on the same level.
  • You need all nodes at distance k (add parent links, then BFS outward).

The Tech Interview Handbook says: "When you are asked to traverse a tree by level, use breadth-first search."

from collections import deque


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


def level_order(root):
    if not root:
        return []
    levels, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):                  # exactly one level per pass
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        levels.append(level)
    return levels

O(n) time, O(width) space. Learn it: Hello Interview: BFS introduction.

Problems, easy to hard:

Tree DFS

Use it when:

  • You need depth, height, diameter, or whether the tree is balanced.
  • You track root-to-leaf paths and their sums, or find the lowest common ancestor.
  • A node's answer depends on its children's answers ("return two things from a subtree").
  • The tree is a BST and you validate it, find the kth smallest, or find an LCA. In-order traversal of a BST is sorted.

Watch out: very deep trees can hit Python's default recursion limit of about 1000 (TIH: Recursion). Say so, or use an explicit stack.

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


def diameter(root):
    best = 0

    def height(node):                            # returns a value to the parent...
        nonlocal best                            # ...and updates a global answer
        if not node:
            return 0
        left, right = height(node.left), height(node.right)
        best = max(best, left + right)
        return 1 + max(left, right)

    height(root)
    return best


def is_valid_bst(node, low=float("-inf"), high=float("inf")):
    if not node:
        return True
    if not low < node.val < high:                # pass the allowed range down
        return False
    return (is_valid_bst(node.left, low, node.val)
            and is_valid_bst(node.right, node.val, high))

O(n) time, O(h) space for the recursion. Learn it: Hello Interview: DFS introduction and TIH: Tree.

Problems, easy to hard:

Graph DFS

Use it when:

  • A grid of land and water asks for islands, regions or areas.
  • You check whether two nodes connect, count components, or copy a graph.
  • Regions touch the border (start the search from the border cells).

Watch out: build the adjacency list first, and add both directions for an undirected edge. The templates below use an explicit stack, so deep graphs cannot hit Python's recursion limit.

from collections import defaultdict


def count_components(n, edges):                  # graph given as an edge list
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)                       # undirected: both directions
    seen, count = set(), 0
    for start in range(n):
        if start in seen:
            continue
        count += 1
        seen.add(start)
        stack = [start]
        while stack:
            u = stack.pop()
            for v in graph[u]:
                if v not in seen:
                    seen.add(v)
                    stack.append(v)
    return count


def num_islands(grid):                           # graph given as a grid
    rows, cols = len(grid), len(grid[0])
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != "1":
                continue
            count += 1
            grid[r][c] = "0"                     # mark visited in place
            stack = [(r, c)]
            while stack:
                i, j = stack.pop()
                for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    ni, nj = i + di, j + dj
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == "1":
                        grid[ni][nj] = "0"
                        stack.append((ni, nj))
    return count

O(V + E) time, or O(rows * cols) for a grid. Learn it: Hello Interview: Graphs overview and the LeetCode Discuss post Graph For Beginners (wh0ami).

Problems, easy to hard:

Graph BFS

Use it when:

  • You need the minimum number of steps, moves or minutes, and every move costs the same.
  • The graph is a set of states: lock combinations, word ladders, a board game.
  • Something spreads from many sources at once (rot, distance to the nearest 0).

Watch out: mark a cell visited when you add it to the queue, not when you pop it. Otherwise the same cell enters the queue many times.

from collections import deque


def oranges_rotting(grid):                       # multi-source BFS, level by level
    rows, cols = len(grid), len(grid[0])
    q, fresh = deque(), 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                q.append((r, c))                 # every source starts in the queue
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while q and fresh:
        for _ in range(len(q)):                  # one minute = one level
            i, j = q.popleft()
            for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                ni, nj = i + di, j + dj
                if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == 1:
                    grid[ni][nj] = 2             # mark when you enqueue
                    fresh -= 1
                    q.append((ni, nj))
        minutes += 1
    return minutes if fresh == 0 else -1

O(V + E) time, O(V) space. For one source, start the queue with that one cell. Learn it: Hello Interview: BFS fundamentals.

Problems, easy to hard:

Topological sort

Use it when:

  • The problem has prerequisites, dependencies, a build order or a schedule.
  • You must say whether all tasks can finish (a cycle check in a directed graph).
  • You order letters from a sorted list of words in an unknown alphabet.

Watch out: if the order you build has fewer than n nodes, the graph has a cycle and no valid order exists.

from collections import defaultdict, deque


def find_order(n, prerequisites):                # Kahn's algorithm
    graph = defaultdict(list)
    indegree = [0] * n
    for course, pre in prerequisites:
        graph[pre].append(course)                # edge: pre must come before course
        indegree[course] += 1
    q = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:                 # all of v's prerequisites are done
                q.append(v)
    return order if len(order) == n else []      # shorter means a cycle

O(V + E) time and space. Learn it: Hello Interview: Topological sort or CP-Algorithms: Topological sort for the DFS version.

Problems, easy to hard:

Alien Dictionary (#269), a common Google and Meta question, is Premium on LeetCode. NeetCode's Blind 75 list hosts it free.

Union-find

Use it when:

  • Connectivity changes as edges arrive, and you ask "are these two in the same group?"
  • You merge groups (accounts, equal variables, friend circles).
  • One edge creates a cycle (a redundant connection).
  • You build a minimum spanning tree with Kruskal: sort edges by weight, union if not yet connected.

Watch out: use both path compression and union by size. Without them, find can degrade to O(n).

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                                   # already joined: this edge makes a cycle
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                               # attach the smaller tree under the larger
        self.size[ra] += self.size[rb]
        return True

Near O(1) amortized per operation, O(n) space. Learn it: CP-Algorithms: Disjoint set union and VisuAlgo: Union-find.

Problems, easy to hard:

Shortest paths

Use it when:

  • Edges have weights, and you want the minimum total cost, time or effort: Dijkstra (weights must not be negative).
  • The problem limits you to "at most k stops": run k rounds of Bellman-Ford, or BFS level by level.
  • Weights are only 0 or 1: 0-1 BFS with a deque.
  • You must connect all points at minimum cost: a minimum spanning tree (Kruskal with union-find, or Prim).

The Tech Interview Handbook rates Bellman-Ford, Floyd-Warshall, Prim and Kruskal as "Almost never" asked. Learn Dijkstra well first.

import heapq
from collections import defaultdict


def network_delay_time(times, n, k):             # Dijkstra from node k
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    dist = {}
    heap = [(0, k)]
    while heap:
        d, u = heapq.heappop(heap)
        if u in dist:
            continue                             # stale entry: u already has its final distance
        dist[u] = d
        for v, w in graph[u]:
            if v not in dist:
                heapq.heappush(heap, (d + w, v))
    return max(dist.values()) if len(dist) == n else -1

O((V + E) log V) time. Learn it: Hello Interview: Shortest path algorithms and the LeetCode Graph Theory study plan.

Problems, easy to hard:

Heaps

Use it when:

  • Top K: the k largest, smallest, most frequent or closest items. Keep a heap of size k.
  • K-way merge: you merge k sorted lists, or find the kth smallest across sorted rows.
  • Two heaps: a running median, or two pools such as free and busy servers.

Watch out: Python's heapq is a min-heap. For a max-heap, push negated values. Built-in max-heap functions exist only from Python 3.14 (heapq docs), so do not rely on them.

import heapq
from collections import Counter


def top_k_frequent(nums, k):                     # top K: keep a size-k min-heap
    heap = []
    for num, freq in Counter(nums).items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)                  # drop the least frequent
    return [num for _, num in heap]


def merge_k_sorted(lists):                       # k-way merge
    heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
    heapq.heapify(heap)
    merged = []
    while heap:
        val, i, j = heapq.heappop(heap)
        merged.append(val)
        if j + 1 < len(lists[i]):                # push the next item from the same list
            heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
    return merged


class MedianFinder:                              # two heaps
    def __init__(self):
        self.low, self.high = [], []             # low: max-heap (negated), high: min-heap

    def add(self, num):
        heapq.heappush(self.low, -num)
        heapq.heappush(self.high, -heapq.heappop(self.low))
        if len(self.high) > len(self.low):       # keep low the same size or one bigger
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def median(self):
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

Top K is O(n log k), k-way merge is O(N log k) for N total items, and each median insert is O(log n). Learn it: Hello Interview: Heap and TIH: Heap.

Problems, easy to hard:

Backtracking

Use it when:

  • The problem asks for "all" combinations, permutations, subsets, partitions or placements.
  • n is small, often 20 or less.
  • It is a constraint puzzle: N-Queens, Sudoku, word search.

Watch out: append a copy (path[:]), not path itself. Undo every change right after the recursive call. For permutations, replace start with a used array.

def subsets_with_dup(nums):
    nums.sort()                                  # duplicates sit next to each other
    result, path = [], []

    def backtrack(start):
        result.append(path[:])                   # record a copy
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue                         # skip a duplicate branch
            path.append(nums[i])                 # choose
            backtrack(i + 1)                     # explore
            path.pop()                           # un-choose

    backtrack(0)
    return result

Subsets cost O(n * 2^n) and permutations O(n * n!), with O(n) recursion depth. Learn it: Hello Interview: Backtracking or Striver's recursion and backtracking playlist.

Problems, easy to hard:

Greedy

Use it when:

  • You can argue a local choice is never worse than any other: the earliest end, the farthest reach, the smallest item that fits.
  • Sean Prashad: "If need to count/divide optimally", try "Greedy, Dynamic programming".

Watch out: if you cannot say why the choice is safe, test a small counterexample. If it fails, switch to dynamic programming.

def can_jump(nums):
    farthest = 0
    for i, step in enumerate(nums):
        if i > farthest:
            return False                         # index i cannot be reached
        farthest = max(farthest, i + step)
    return True


def erase_overlap_intervals(intervals):          # keep the most non-overlapping
    intervals.sort(key=lambda iv: iv[1])         # the earliest end leaves the most room
    kept, last_end = 0, float("-inf")
    for start, end in intervals:
        if start >= last_end:
            kept += 1
            last_end = end
    return len(intervals) - kept

Usually O(n log n) for the sort, then O(n). Learn it: Hello Interview: Greedy.

Problems, easy to hard:

Trie

Use it when:

  • You store many words and ask prefix questions, autocomplete, or "starts with".
  • You search a dictionary with wildcards.
  • You search for many words in a grid at once.
  • You want the maximum XOR of two numbers (a trie over bits).

Watch out: in Word Search II, delete words from the trie once found, or the same grid path gets explored again and again.

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True                         # end-of-word marker

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node:
                return None
            node = node[ch]
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and "$" in node

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

O(L) per operation, L = word length. Learn it: Hello Interview: Trie. Jugal's Meta plan sets a target: "Code a Trie class with insert/search/delete in ~20 minutes on paper" (post).

Problems, easy to hard:

Bit manipulation

Use it when:

  • "Every element appears twice except one."
  • You count set bits, check a power of two, or reverse bits.
  • You add without +, or treat subsets as bitmasks.

Watch out: Python integers never overflow. For 32-bit problems, mask with 0xFFFFFFFF and handle the sign yourself.

def single_number(nums):                         # pairs cancel: x ^ x == 0, x ^ 0 == x
    result = 0
    for x in nums:
        result ^= x
    return result


def count_set_bits(x):                           # x & (x - 1) clears the lowest set bit
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count

# Read bit k: (x >> k) & 1      Set bit k: x | (1 << k)      Clear bit k: x & ~(1 << k)
# Lowest set bit: x & -x        Power of two: x > 0 and x & (x - 1) == 0

O(n) or O(number of bits) time, O(1) space. Learn it: TIH: Binary.

Problems, easy to hard:

Matrix traversal

Use it when:

  • You rotate, transpose, or read a matrix in spiral or diagonal order.
  • You change a matrix in place (set zeroes, game of life).
  • You search a matrix sorted by rows and columns.

Watch out: for in-place updates, encode the old and new state in the same cell, or use the first row and column as markers, so you do not read values you already changed.

def spiral_order(matrix):
    result = []
    top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1):
            result.append(matrix[top][c])
        top += 1
        for r in range(top, bottom + 1):
            result.append(matrix[r][right])
        right -= 1
        if top <= bottom:
            for c in range(right, left - 1, -1):
                result.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:
            for r in range(bottom, top - 1, -1):
                result.append(matrix[r][left])
            left += 1
    return result


def rotate(matrix):                              # 90 degrees clockwise, in place
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]   # transpose
    for row in matrix:
        row.reverse()                            # then reverse each row

O(rows * cols) time, O(1) extra space for the in-place versions. Learn it: TIH: Matrix and Hello Interview: Spiral matrix.

Problems, easy to hard:

Design a data structure

Use it when:

  • The problem says "implement a class" with methods such as get, put, add or top.
  • Every operation must run in O(1) or O(log n).
  • It is a cache, iterator, browser history, snapshot or rate counter.

Combine structures to hit the target: a hash map plus a doubly linked list (LRU cache), a hash map plus an array (random pick in O(1)), a per-key list of (time, value) plus binary search (time-based lookups). Jugal's notes rate this a core pattern for Amazon, Meta and Airbnb (Company Wise DSA patterns).

class Node:
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None


class LRUCache:                                  # hash map + doubly linked list
    def __init__(self, capacity):
        self.capacity, self.map = capacity, {}
        self.head, self.tail = Node(), Node()    # dummies: head.next is the most recent
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)                       # touched: move to the front
        self._add_front(node)
        return node.val

    def put(self, key, value):
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.capacity:
            lru = self.tail.prev                 # least recently used sits at the back
            self._remove(lru)
            del self.map[lru.key]

O(1) per operation. If you use OrderedDict, expect the follow-up "now build it without OrderedDict".

Problems, easy to hard:

Dynamic programming

Use it when:

  • You count the ways, or find the minimum or maximum, and the same subproblems repeat.
  • Each step is a choice: take it or skip it, go right or go down.
  • The input is two strings, a grid, or items with a capacity.
  • A greedy choice fails on a small counterexample.

Solve every DP problem in the same 5 steps:

  1. Define the state in one sentence. "best(i) is the most money from houses i onward."
  2. Write the choices at that state as a recurrence.
  3. Write the base cases.
  4. Code it top-down with @cache. Get it correct first.
  5. Convert to bottom-up and keep only the rows you need, if the interviewer asks.

Jugal's 60-day roadmap teaches DP in layers: take or skip, unbounded, longest increasing subsequence, grids, strings, stocks, then partition DP. "By day 45 you should be able to recognize which DP family a problem belongs to within the first 60 seconds of reading it" (post).

from functools import cache


def rob(nums):                                   # 1D, take or skip, top-down
    @cache
    def best(i):                                 # most money from house i onward
        if i >= len(nums):
            return 0
        return max(best(i + 1), nums[i] + best(i + 2))

    return best(0)


def rob_bottom_up(nums):                         # same recurrence, O(1) space
    take, skip = 0, 0
    for x in nums:
        take, skip = skip + x, max(take, skip)
    return max(take, skip)


def can_partition(nums):                         # 0/1 knapsack: each item at most once
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [True] + [False] * target               # dp[t]: some subset sums to t
    for x in nums:
        for t in range(target, x - 1, -1):       # go DOWN so x is used once
            dp[t] = dp[t] or dp[t - x]
    return dp[target]


def coin_change(coins, amount):                  # unbounded knapsack: reuse allowed
    INF = float("inf")
    dp = [0] + [INF] * amount                    # dp[t]: fewest coins for t
    for coin in coins:
        for t in range(coin, amount + 1):        # go UP so a coin can repeat
            dp[t] = min(dp[t], dp[t - coin] + 1)
    return dp[amount] if dp[amount] != INF else -1


def longest_common_subsequence(a, b):            # two strings: prefixes a[:i] and b[:j]
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[-1][-1]

Learn it: the LeetCode Dynamic Programming study plan (10 patterns, 50 questions), Dynamic Programming Patterns (aatalyk) on LeetCode Discuss, and Aditya Verma's DP playlist or Striver's DP playlist if you want video.

First 10 problems, easy to hard:

Then drill by family, easy to hard within each row:

Family Cue Problems
1D, take or skip Answer at i depends on a few earlier positions Min Cost Climbing Stairs (#746, Easy), House Robber II (#213, Medium), Decode Ways (#91, Medium), Maximum Product Subarray (#152, Medium)
0/1 knapsack Pick a subset, each item at most once, to hit a target Target Sum (#494, Medium), Last Stone Weight II (#1049, Medium), Ones and Zeroes (#474, Medium)
Unbounded knapsack Items can repeat Coin Change II (#518, Medium), Perfect Squares (#279, Medium), Combination Sum IV (#377, Medium), Minimum Cost For Tickets (#983, Medium)
Longest increasing subsequence Longest chain where each item beats the last Largest Divisible Subset (#368, Medium), Longest String Chain (#1048, Medium), Russian Doll Envelopes (#354, Hard)
Two strings Common subsequence, edits, matching Interleaving String (#97, Medium), Distinct Subsequences (#115, Hard), Regular Expression Matching (#10, Hard)
Grids Move right or down, count paths or minimum cost Unique Paths II (#63, Medium), Minimum Path Sum (#64, Medium), Maximal Square (#221, Medium), Cherry Pickup (#741, Hard)
Palindromes and intervals The answer for [i, j] comes from smaller ranges inside it Palindromic Substrings (#647, Medium), Longest Palindromic Subsequence (#516, Medium), Minimum Cost to Cut a Stick (#1547, Hard), Burst Balloons (#312, Hard)
State machine (stocks) A few states per day: holding, not holding, cooldown Best Time to Buy and Sell Stock II (#122, Medium), Best Time to Buy and Sell Stock with Cooldown (#309, Medium), Best Time to Buy and Sell Stock with Transaction Fee (#714, Medium), Best Time to Buy and Sell Stock IV (#188, Hard)
On trees Each node returns a small tuple of states to its parent House Robber III (#337, Medium), Binary Tree Cameras (#968, Hard)
Bitmask n of 20 or less, and the state is "which items are used" Partition to K Equal Sum Subsets (#698, Medium), Shortest Path Visiting All Nodes (#847, Hard)

Google targets: do the last four rows. Jugal's Google plan covers "bitmask DP for small n" and calls tree DP "commonly asked by Google" (post).

Company pattern map

Jugal's map of the 4 patterns each company favors, from his own prep (post, with problems per company in his Notion page). It is his curation, not measured frequency. For tag frequency, use the company pages.

How to run the sprint (1 to 2 weeks, after you know all 25 patterns):

  1. Pick your company's row below. Interviewing at several? Start with the patterns that repeat across their rows.
  2. Do 2 to 3 timed problems per pattern from that company's section of the Notion page. Jugal: "the timer matters here" (post).
  3. Want a fixed schedule? Use the company days in the day-by-day plan, Master DSA with patterns.
  4. End with mocks, not new problems: 45 minutes, one problem, out loud (Mock interviews).
Company Patterns to sprint on Company page
Amazon Sliding window, Two pointers, Graph BFS, Design a data structure Amazon
Google Dynamic programming, graphs (DFS, BFS, Topological sort, Shortest paths), Backtracking, Binary search Google
Meta Sliding window, trees (BFS, DFS), Graph BFS, Design a data structure Meta
Netflix Intervals, Greedy, top K and two heaps (Heaps) Netflix
Uber Graphs (Shortest paths, Union-find), Greedy, top K and two heaps (Heaps) Uber
Airbnb Intervals, Graph BFS, Backtracking, Design a data structure Airbnb
Microsoft Trees (Tree DFS), Dynamic programming, XOR (Bit manipulation), Binary search Microsoft
Apple Binary search, Two pointers, monotonic stack (Stack), Matrix traversal Apple

Tip: Jugal's other posts weight some companies differently. His Meta and Amazon guide (Feb 2026) adds heaps and top K for Meta and intervals for Amazon, with named problems for each. His Netflix plan leans on graphs, DP, sliding window, strings and backtracking. If you target one of these three, sprint on both sets.

Where these patterns come from

  • Sean Prashad: LeetCode Patterns (repo): 179 problems tagged by pattern and by the companies that asked them, a Beginner and an Experienced roadmap, and the Helpful Tips heuristics quoted in the cue table. How to use it: filter by pattern when you need more problems for a weak pattern.
  • 14 Patterns to Ace Any Coding Interview Question (Fahim ul Haq, 2019): the article that named sliding window, two pointers, fast and slow pointers, merge intervals, cyclic sort, in-place reversal, tree BFS, tree DFS, two heaps, subsets, modified binary search, top K, k-way merge and topological sort. How to use it: read it once for its "how to identify" lines.
  • AlgoMaster: 15 LeetCode patterns (Ashish Pratap Singh, 2024): 15 patterns with starter problems for each. How to use it: a second set of starter problems when a pattern does not click.
  • Hello Interview: data structures and algorithms (freemium): visual lessons for 16 patterns. How to use it: read the overview before day 1 of a pattern.
  • Tech Interview Handbook by Yangshun Tay: topic priorities, techniques and corner cases. How to use it: copy the corner cases for each topic into your cheat sheet.
  • LeetCode study plans: Dynamic Programming (10 patterns), Binary Search (8 patterns), Graph Theory (traversal, union-find, topological sort, Dijkstra, MST). How to use it: 2 to 3 weeks on one plan when that topic is your weakest.
  • Jugal: Company Wise DSA patterns: 22 core patterns with representative problems, plus the company map above. How to use it: Part 3 as a pattern checklist, Part 1 to drill your target company.
  • Jugal: Master DSA with patterns: the same 22 patterns as a 60-day, day-by-day plan at 60 to 90 minutes a day, with review days and mocks at the end. How to use it: follow it if you want a fixed daily schedule instead of the 2-days-per-pattern loop above.
  • Michael's Guide to FAANG DSA (on Ascend): 15 patterns with linked sample problems for each, plus a 10-week roadmap (laid out on Problem lists). How to use it: a second set of problems when one pattern does not click.
  • Paid, not needed: Grokking the Coding Interview (DesignGurus) ($197, as of Oct 2026) and AlgoMonster. The free sources above cover the same patterns.

Pattern checklist

Tick a pattern when you can name it from a problem statement, write its template from memory, and have solved at least 5 of its problems.

  • Hashing
  • Two pointers
  • Fast and slow pointers
  • Sliding window
  • Prefix sums
  • Intervals
  • Cyclic sort
  • Linked list reversal
  • Stack and monotonic stack
  • Binary search
  • Tree BFS
  • Tree DFS
  • Graph DFS
  • Graph BFS
  • Topological sort
  • Union-find
  • Shortest paths
  • Heaps
  • Backtracking
  • Greedy
  • Trie
  • Bit manipulation
  • Matrix traversal
  • Design a data structure
  • Dynamic programming

Next: Problem lists