Pattern Recognition Cheat Sheet

Free with account Updated Nov 19, 2026 · 4 min read
On this page

    You don't recognise a pattern by remembering the problem. You recognise it from three things you can read in the first minute: how big the input is, what shape it has, and what the question asks for. This page puts those signals in one place. Each row links to a pattern page with the template and its common bugs.

    Use it as a starting guess, not a rule. Many problems mix two patterns: LRU Cache is a hash map plus a linked list, and Minimum Window Substring is a sliding window plus counts.

    Step 1: the input size sets the budget

    Table: n up to 12 allows O(n!) for backtracking; up to 25 allows O(2ⁿ) for subsets or bitmask DP; up to 500 allows O(n³); up to 5,000 allows O(n²) for DP over pairs; up to 10⁶ needs O(n log n) or O(n)
    Table: n up to 12 allows O(n!) for backtracking; up to 25 allows O(2ⁿ) for subsets or bitmask DP; up to 500 allows O(n³); up to 5,000 allows O(n²) for DP over pairs; up to 10⁶ needs O(n log n) or O(n); around 10⁹ needs O(log n) or O(1). Rule of thumb: about 10⁸ simple steps per second.

    If the constraints aren't given, ask. "How large can n get?" is one of the most useful questions in the interview, because it tells you which ideas are even worth trying. See Big-O for Interviews for how to count steps.

    Step 2: the shape of the input

    Eight input shapes with arrows to patterns: sorted array to binary search or two pointers; subarray or substring to sliding window or prefix sums; ranges to sort and sweep or a heap of ends; tree to D
    Eight input shapes with arrows to patterns: sorted array to binary search or two pointers; subarray or substring to sliding window or prefix sums; ranges to sort and sweep or a heap of ends; tree to DFS or BFS; grid or graph to BFS for fewest steps or DFS for components; dependencies to topological sort; all ways with small n to backtracking; min, max or count ways with overlapping subproblems to dynamic programming.