Spot the pattern before you spot the bug.

Study a pattern in 60 seconds: when to reach for it, the complexity, the signature problems, and the exact tells that should fire when you read a prompt. Then drill it.

• Two Pointers

  Process a sorted array (or string) by walking two indices toward each other, or in the same direction, to skip O(n²) work.

  O(n) or O(n log n) with a sortO(1)
  Quick study

  When to use

  Reach for two pointers when the input is sorted (or can be sorted cheaply) and you need a pair / triplet / sub-array that satisfies a condition. Also great for in-place array partitioning.

  Tells

  • Input is already sorted or you're allowed to sort.
  • You need a pair / triplet that hits a target.
  • The brute force is O(n²) but the problem feels like O(n).

  Signature problems

  Two Sum II (sorted) · 3Sum · Container With Most Water · Remove Duplicates from Sorted Array · Trapping Rain Water (O(1) variant)

• Sliding Window

  Maintain a window of contiguous elements and update an aggregate in O(1) as the window slides forward, instead of recomputing per position.

  O(n)O(k) for the window state
  Quick study

  When to use

  Reach for sliding window when the question asks for the longest / shortest / max-sum / max-count contiguous sub-array or sub-string satisfying a constraint.

  Tells

  • Words 'contiguous', 'substring', 'sub-array'.
  • Asks for longest / shortest / max-sum under a constraint.
  • Brute force is O(n·k); the slide brings it to O(n).

  Signature problems

  Longest Substring Without Repeating Characters · Minimum Window Substring · Longest Substring with K Distinct Characters · Permutation in String · Max Sum Subarray of Size K

• Fast & Slow Pointers

  Two pointers advancing at different speeds (typically 1× and 2×) to detect cycles, find midpoints, or compare halves of a linked structure.

  O(n)O(1)
  Quick study

  When to use

  Reach for fast/slow when you need O(1) extra space on a linked list or array-as-graph and the question is cycle detection, midpoint, or kth-from-end.

  Tells

  • Linked list, no extra-space allowance.
  • Words 'cycle', 'middle', 'kth from end'.
  • Brute force would be a hash set; the elegant fix is two speeds.

  Signature problems

  Linked List Cycle (detect + find start) · Middle of a Linked List · Happy Number · Palindrome Linked List · Find the Duplicate Number (cycle on indices)

• Binary Search (modified)

  Halve the search space on each step. Use the modified variant on monotonic predicates ('first index where P() is true') — not just sorted arrays.

  O(log n) per queryO(1)
  Quick study

  When to use

  Reach for binary search whenever you can write a monotonic predicate (true / true / true / false / false). Works on rotated arrays, answer space, and 2D grids that have any monotonicity.

  Tells

  • Sorted input or a monotonic predicate.
  • Answer is a single value in a numeric range and you're asked for the smallest/largest.
  • Brute force is O(n) and required is O(log n).

  Signature problems

  Search in Rotated Sorted Array · Find First and Last Position · Median of Two Sorted Arrays · Capacity to Ship Packages within D Days · Find Peak Element

• Merge Intervals

  Sort intervals by start time, then sweep left-to-right merging or comparing overlaps with the previous interval.

  O(n log n) due to sortO(n)
  Quick study

  When to use

  Reach for merge intervals whenever the input is a set of [start, end] pairs and the question is about overlaps, free slots, max concurrent intervals, or merging adjacent ranges.

  Tells

  • Input shaped as [start, end] pairs.
  • Words 'overlap', 'merge', 'gaps', 'meeting rooms'.
  • First instinct is 'sort by start'.

  Signature problems

  Merge Intervals · Insert Interval · Meeting Rooms II (min rooms needed) · Non-overlapping Intervals · Interval List Intersections

• Cyclic Sort

  When the input is an array of n integers in a known range (often 1..n), place each element at its correct index in O(n) and O(1) extra space.

  O(n)O(1)
  Quick study

  When to use

  Reach for cyclic sort when the array contains n numbers in [0..n] or [1..n] and you need missing / duplicate / first missing positive in O(1) extra space.

  Tells

  • Input is n integers in a bounded range [0..n] or [1..n].
  • You're asked for missing / duplicate / smallest positive.
  • Brute force is a hash set; the elegant fix is in-place swaps.

  Signature problems

  Find All Numbers Disappeared in an Array · Find the Duplicate Number · First Missing Positive · Find All Duplicates in an Array · Set Mismatch

• Tree BFS (Level Order)

  Traverse a tree level by level using a queue. Use when the answer depends on level structure (depth, level sum, zig-zag, right-side view).

  O(n)O(w) where w = max width
  Quick study

  When to use

  Reach for tree BFS whenever the problem cares about depth, levels, or 'first thing reachable in N steps'. Also the right tool for shortest path on an unweighted graph.

  Tells

  • Words 'level', 'depth', 'minimum steps'.
  • You need to visit nodes by distance from the source.
  • Tree / unweighted graph + 'shortest' or 'closest'.

  Signature problems

  Binary Tree Level Order Traversal · Zigzag Level Order · Right Side View · Minimum Depth of Binary Tree · Word Ladder (shortest transformation)

• Tree DFS / Recursion

  Recurse down each branch fully, optionally carrying state. Use for path sums, subtree decisions, ancestors, and structural properties.

  O(n)O(h) recursion stack
  Quick study

  When to use

  Reach for tree DFS for any problem where the answer depends on a path or on a subtree's aggregate. Easier than BFS when state needs to flow down the recursion.

  Tells

  • Words 'path', 'root-to-leaf', 'subtree'.
  • You need to aggregate or filter along a path.
  • Natural to write as recursion (left, right, combine).

  Signature problems

  Path Sum / Path Sum II · Diameter of Binary Tree · Lowest Common Ancestor · Binary Tree Maximum Path Sum · Validate Binary Search Tree

• Topological Sort

  Order nodes in a DAG such that every edge u→v has u before v. Use Kahn's algorithm (in-degree + queue) or DFS post-order with cycle check.

  O(V + E)O(V + E)
  Quick study

  When to use

  Reach for topo-sort whenever the problem is 'do A, B, C in an order that respects dependencies'. Cycle = no valid order — many problems hide a cycle-check question.

  Tells

  • Word 'order' with dependencies / prerequisites.
  • Input shaped as edges or a precedence list.
  • Question asks 'is there a valid order' or 'all valid orders'.

  Signature problems

  Course Schedule · Course Schedule II · Alien Dictionary · Minimum Height Trees · Sequence Reconstruction

• Dynamic Programming

  Define a recurrence on a small state, memoise or build a table bottom-up. Apply when the problem has overlapping sub-problems and optimal substructure.

  Usually O(n·k) — depends on state dimensionsO(n·k), often reducible to O(k)
  Quick study

  When to use

  Reach for DP when the problem asks for an extremum (max/min/count of ways) over choices and the brute-force recursion has the same sub-problem repeating across branches.

  Tells

  • Words 'max/min', 'number of ways', 'optimal'.
  • Brute-force recursion repeats the same sub-state.
  • You can phrase the state as 'best answer ending at i' or 'best answer using first i items'.

  Signature problems

  Maximum Subarray (Kadane) · Longest Increasing Subsequence · House Robber · Coin Change · Edit Distance · Longest Common Subsequence

• Backtracking

  Enumerate combinatorial choices via DFS with explicit undo. Use for permutations / combinations / subsets / constraint-satisfaction (sudoku, n-queens).

  Exponential in the depth of the choice treeO(depth)
  Quick study

  When to use

  Reach for backtracking when you need ALL solutions to a combinatorial problem, or when the choice tree is small enough that exhaustive search with pruning is the right tool.

  Tells

  • Words 'all permutations / combinations / subsets'.
  • The problem feels like 'try X, recurse, undo'.
  • Constraint-satisfaction with a manageable branching factor.

  Signature problems

  Permutations · Subsets / Combination Sum · Word Search · Sudoku Solver · N-Queens

• Heap / Top-K Elements

  Maintain a fixed-size heap to get the top / bottom / k-most-frequent in O(n log k). Use for streaming, k-closest, k-largest, merge-K-sorted-lists.

  O(n log k)O(k)
  Quick study

  When to use

  Reach for a heap whenever you need the k smallest or largest, or you're merging k sorted streams, or you need to keep a running median.

  Tells

  • Words 'top k', 'kth largest / smallest'.
  • Merging multiple sorted streams.
  • Running statistic (median, frequency) over a stream.

  Signature problems

  Kth Largest Element in an Array · Top K Frequent Elements · K Closest Points to Origin · Merge K Sorted Lists · Find Median from Data Stream

• Greedy

  Make the locally optimal choice at each step and trust it to land the global optimum. Works when the problem has the greedy-choice property and optimal substructure.

  O(n log n) (sort dominates)O(1)
  Quick study

  When to use

  Reach for greedy when you can convince yourself (often by an exchange argument) that picking the best-looking option now never paints you into a corner. Sort + sweep is the usual shape.

  Tells

  • Words 'maximise / minimise' with a clear ordering hint (earliest end time, largest first).
  • Sort, then sweep linearly making one decision per element.
  • DP would work but the state collapses to 'just take the best now'.

  Signature problems

  Jump Game · Gas Station · Task Scheduler · Minimum Number of Arrows to Burst Balloons · Non-overlapping Intervals · Activity Selection

• Union-Find (DSU)

  Disjoint-set forest with path compression + union-by-rank. Near-O(1) amortised per operation. Use for dynamic connectivity and grouping under merges.

  O(α(n)) per op (effectively O(1))O(n)
  Quick study

  When to use

  Reach for union-find whenever the question is 'are these two things in the same group?' or 'how many groups remain?' as edges arrive one at a time.

  Tells

  • Words 'connected', 'in the same group', 'merge'.
  • Edges or pairs arrive incrementally; need running group count.
  • Detect a cycle being added to an undirected graph.

  Signature problems

  Number of Connected Components in an Undirected Graph · Redundant Connection · Accounts Merge · Friend Circles / Number of Provinces · Number of Islands II (online)

• Trie (Prefix Tree)

  A tree of characters where every root-to-node path spells a prefix. Cheap prefix queries, dictionary search, and the speed-up behind Word Search II.

  O(L) per insert / query (L = word length)O(N·L) for N words
  Quick study

  When to use

  Reach for a trie when you need fast prefix / startsWith queries, or when many words share prefixes and you're doing repeated dictionary lookups.

  Tells

  • Words 'prefix' / 'starts with'.
  • Multi-word dictionary search inside a larger problem.
  • Autocomplete or typeahead.

  Signature problems

  Implement Trie (Prefix Tree) · Word Search II · Design Add and Search Words Data Structure · Replace Words · Longest Word in Dictionary

• Prefix Sum

  Precompute cumulative sums so any range query is O(1). Extends to 2D rectangles and combines beautifully with a hashmap for 'subarrays with sum K' problems.

  O(n) preprocess, O(1) per queryO(n) (or O(m·n) in 2D)
  Quick study

  When to use

  Reach for prefix sum whenever you need many range-sum queries over a static array, or whenever 'subarray sum equals X' or 'subarray sum divisible by k' shows up.

  Tells

  • Many range-sum queries over a static array.
  • 'Number of subarrays whose sum is X' (combine with hashmap).
  • 2D grid + many rectangle-sum questions.

  Signature problems

  Subarray Sum Equals K · Range Sum Query - Immutable · Range Sum Query 2D - Immutable · Continuous Subarray Sum · Find Pivot Index

• Bit Manipulation

  Use XOR, AND, OR, shifts and bitmasks to solve in O(1) extra space what otherwise needs a hashmap. The reflex tool when 'every element appears twice except one' shows up.

  O(n) typicallyO(1) extra
  Quick study

  When to use

  Reach for bit manipulation when XOR self-cancels (find a single element), when n is tiny enough to be a bitmask (n ≤ ~20), or when you need power-of-two / parity checks.

  Tells

  • 'Every element appears twice except one' → XOR.
  • Constant extra space requirement + integer input.
  • Subset enumeration with small n (≤ 20).

  Signature problems

  Single Number · Counting Bits · Number of 1 Bits · Sum of Two Integers (no + / -) · Subsets via bitmask · Missing Number (XOR variant)

• Monotonic Stack

  A stack whose values stay strictly increasing (or decreasing). On each push, pop violators — the popped element's answer is the current index. O(n) total.

  O(n)O(n)
  Quick study

  When to use

  Reach for a monotonic stack when you need, for each index, the next (or previous) element satisfying an inequality — 'next greater', 'previous smaller', 'largest rectangle'.

  Tells

  • 'Next greater' / 'previous smaller' element.
  • Histogram-style largest-rectangle problems.
  • You need O(n) where brute force is O(n²) nested compares.

  Signature problems

  Daily Temperatures · Next Greater Element I / II · Largest Rectangle in Histogram · Trapping Rain Water (stack variant) · Remove K Digits

• Monotonic Deque

  A double-ended queue whose values stay monotonically decreasing (or increasing). Keeps the max (or min) of a sliding window in amortised O(1) per step.

  O(n)O(k)
  Quick study

  When to use

  Reach for a monotonic deque when the problem is sliding-window AND you need the running max / min of the window. A heap would be O(n log k); the deque is O(n).

  Tells

  • Sliding window + max / min of the window in O(1) per step.
  • 'Largest value in the last k seconds'.
  • You reached for a heap; deque is the asymptotic win.

  Signature problems

  Sliding Window Maximum · Shortest Subarray with Sum at Least K · Constrained Subsequence Sum · Jump Game VI

• Hash Map / Frequency Count

  Trade space for time: a map of key → count (or key → index) collapses an O(n²) scan to O(n). The right answer more often than candidates admit.

  O(n)O(n)
  Quick study

  When to use

  Reach for a hashmap when you need O(1) 'have I seen X?', complement lookups (Two Sum), anagram grouping, or any frequency-driven decision.

  Tells

  • 'Have we seen this value before?'
  • 'Find a pair whose sum / XOR equals target'.
  • 'Group items by a computed key' (anagram signature, etc.).

  Signature problems

  Two Sum · Group Anagrams · Longest Consecutive Sequence · Valid Anagram · Top K Frequent Elements (count phase)

• Graph BFS

  BFS on a general graph (often a grid). Distinct from tree BFS because graphs have cycles — you must carry a visited set. The right tool for shortest path on an unweighted graph.

  O(V + E)O(V)
  Quick study

  When to use

  Reach for graph BFS when the answer is 'minimum number of steps' on an unweighted graph, or when you need multi-source BFS (start the queue with every source at distance 0).

  Tells

  • Unweighted graph + 'minimum steps' / 'shortest path'.
  • Grid + 'minimum distance from any source'.
  • Multiple sources — multi-source BFS in one pass.

  Signature problems

  Word Ladder · Rotting Oranges (multi-source) · Open the Lock · 01 Matrix · Shortest Path in Binary Matrix

• Graph DFS

  DFS on a general graph with a visited set. Use for reachability, counting connected components, path enumeration, and cycle detection in a directed graph (3-colouring).

  O(V + E)O(V)
  Quick study

  When to use

  Reach for graph DFS when the question is 'is X reachable from Y', 'how many components', or 'does this directed graph contain a cycle' — when path matters more than distance.

  Tells

  • Graph + 'reachable' / 'all reachable from'.
  • Count connected components.
  • Cycle detection in a directed graph via 3-colour DFS.

  Signature problems

  Clone Graph · Surrounded Regions · Pacific Atlantic Water Flow · Number of Provinces · Course Schedule (cycle detection via DFS colouring)

• Matrix / Grid Traversal

  BFS or DFS on a 2D grid where neighbours are the 4 (or 8) adjacent cells. Distinct framing from general graphs — islands, flood fill, region counting.

  O(m·n)O(m·n) for visited
  Quick study

  When to use

  Reach for matrix traversal when the input is a 2D grid and the answer is a property of connected regions: count of islands, largest area, flood fill, surrounded regions.

  Tells

  • Input is a 2D grid of characters or ints.
  • Words 'island', 'region', 'flood'.
  • 4- or 8-directional neighbour walks.

  Signature problems

  Number of Islands · Flood Fill · Max Area of Island · Surrounded Regions · Number of Closed Islands

• Dijkstra (Shortest Path)

  Best-first BFS using a min-heap of (distance, node). The standard shortest-path algorithm for weighted graphs with non-negative edges.

  O((V + E) log V) with a binary heapO(V)
  Quick study

  When to use

  Reach for Dijkstra when edges have non-negative weights and you need shortest path (single-source). For negative weights use Bellman-Ford; for unweighted use plain BFS.

  Tells

  • Weighted edges + non-negative weights + shortest path.
  • 'Minimum cost / effort to reach destination'.
  • Grid where each cell has a cost to enter.

  Signature problems

  Network Delay Time · Path with Maximum Probability · Path with Minimum Effort · Swim in Rising Water · Cheapest Flights Within K Stops (modified)