Problem-Solving Patterns

About 35 patterns cover the large majority of interview problems. Each lesson shows how to spot the pattern, why it works, one reusable template and a practice ladder.

What you will learn

• Recognise the pattern from the wording and the constraints of a problem
• Reuse one template per pattern instead of memorising hundreds of solutions
• Explain why each pattern is correct and what it costs
• Avoid the classic off-by-one, overflow and edge-case traps
• Climb from easy to hard problems in every pattern with a curated ladder

Arrays & Strings

The most common interview category. Five patterns turn most O(n²) brute forces into O(n).

• Hash Maps & Sets: Trade memory for time: "have I seen this?", counting, and grouping in O(1).
• Two Pointers: Two indexes moving toward each other or in the same direction to avoid nested loops.
• Sliding Window: Grow the window, shrink when it breaks the rule — for subarrays and substrings.
• Prefix Sums & Difference Arrays: Answer range-sum questions in O(1) and count subarrays with a hash map.
• Intervals: Sort by start, then merge, insert or sweep — meeting rooms and overlaps.

Searching & Sorting

Binary search is far more than finding a number in a sorted array, and an array of 1 to n can sort itself.

• Binary Search: One bug-free template: find the first position where a condition becomes true.
• Binary Search on the Answer: When the answer is a number and "can I do it with X?" is monotonic.
• Sorting as a Tool: Custom comparators, counting sort and quickselect for the k-th element.
• Cyclic Sort: Values 1 to n each have a home index: find missing and duplicate numbers in O(n) time and O(1) space, and count minimum swaps.

Linked Lists

Two techniques solve almost every linked-list question.

• Fast & Slow Pointers: Cycles, middles and the k-th from the end with two runners at different speeds.
• In-Place Reversal & Dummy Nodes: Reverse, merge and reorder lists without losing a pointer.

Stacks & Queues

Last-in-first-out for matching and parsing; monotonic stacks for "next greater".

• Stack Patterns: Matching brackets, evaluating expressions and simulating undo.
• Monotonic Stack & Queue: Next greater element, histograms and sliding-window maximum in O(n).

Heaps

When you need the smallest or largest quickly, again and again.

• Heaps: Top-K, K-Way Merge, Two Heaps: Keep only k items, merge sorted streams, and track a running median.

Trees

Think in subtrees: most tree problems are three lines of recursion.

• Tree DFS: Think in Subtrees: Return values up, pass constraints down — depth, paths, diameter and LCA.
• Tree BFS: Level by Level: Level-order traversal and every "per level" question.
• Binary Search Trees: In-order is sorted: validation, k-th smallest and searching with bounds.

Graphs

Grids are graphs too. Four patterns cover nearly every graph interview question.

• Graphs & Grids: BFS and DFS: Islands, flood fill, shortest steps in a grid and multi-source BFS.
• Topological Sort: Order tasks with dependencies and detect cycles (Kahn's algorithm).
• Union-Find: Group things that are connected, fast — with path compression.
• Shortest Paths: BFS for unweighted, Dijkstra for weighted, 0-1 BFS for in between.

Backtracking

Choose, explore, un-choose — one template for subsets, permutations and puzzles.

• Backtracking: Subsets, combinations, permutations and constraint puzzles with one template.

Dynamic Programming

DP is recursion plus memory. Learn to find the state and the rest follows.

• DP Without Fear: From brute-force recursion to memoisation to a table, in four mechanical steps.
• 1D DP: Climbing stairs, house robber, maximum subarray and longest increasing subsequence.
• Knapsack Family: Take it or leave it: subset sum, coin change and their variants.
• Grid DP: Paths and costs on a grid, and how to save memory with one row.
• String DP: Two strings, two indexes: LCS, edit distance and palindromes.
• Tree & Interval DP: DP on subtrees (house robber III, cameras) and on ranges (burst balloons, cutting sticks).
• State-Machine & Bitmask DP: Stock problems as a few states per day, and subsets of a small set as the state.

Greedy & Special Topics

When a local choice is safe, plus two data structures that appear often enough to learn.

• Greedy: Make the best local choice — and how to convince yourself it is safe.
• Tries: Prefix trees for autocomplete, word search and prefix counting.
• Bit Manipulation: XOR tricks, masks and counting bits — the handful that interviews use.

Design, Matrices & Advanced Topics

The remaining interview favourites: design-a-data-structure, matrix simulation, maths, string matching and range queries.

• Designing Data Structures: LRU and LFU caches, O(1) random sets, time-based maps and iterators — combine two structures.
• Matrix & Simulation: Spiral order, rotation, in-place markers and the Game of Life — index bookkeeping without bugs.
• Math for Interviews: GCD, primes and the sieve, fast power, modular arithmetic, overflow, and random sampling.
• String Matching: KMP & Rolling Hash: Find a pattern in O(n + m) with the failure table, and compare substrings in O(1) with hashing.
• Range Queries: Fenwick & Segment Trees: Prefix sums that survive updates: O(log n) update and query, and counting inversions.

Problem-Solving Patterns cheat sheet