Skip to content
Tutorials Center
My learning

Topics

Lesson 218 of 225 ยท Practice and Review

Problem Patterns Cheat Sheet

Match problem signals to the right technique. A Python cheat sheet with runnable templates for two pointers, windows, BFS, DP, heaps, backtracking and more.

Most algorithm problems are not new. They are one of about twenty patterns wearing a different costume. Experienced programmers do not invent a solution from nothing; they read the problem, notice a signal ("sorted array", "shortest path", "number of ways"), and reach for the technique that signal usually means. This lesson is that skill in one place: a table of signals, a rule for reading the input size, and a short, tested Python template for each major pattern.

Use it as a map, not a replacement for the full lessons. Each pattern links to the lesson that explains why it works. If a template here looks unfamiliar, go there first, then come back and run the example.

Step 1: read the constraints

The size of the input tells you how much work is allowed before you write a line of code. As a rough rule for Python, you can afford about ten million simple operations per second of runtime, so:

Input size n Target complexity What it suggests
up to about 10 O(n!) permutations, brute-force backtracking
up to about 20 to 25 O(2^n) subsets, bitmask DP, meet in the middle
up to about 500 O(n^3) Floyd-Warshall, interval DP
up to about 5,000 O(n^2) 2D DP, all pairs
up to about 100,000 to 1,000,000 O(n log n) or O(n) sorting, heaps, binary search, hashing, windows
up to 10^9 or more O(log n) or O(1) binary search, math

If the obvious solution is O(n^2) and n is 100,000, the problem is asking you to find a pattern that removes a loop.

Step 2: match the signal

Signal in the problem First thing to try Lesson
Sorted array; find a pair or triple with a target sum Two pointers Two pointers
Longest/shortest contiguous subarray or substring with a condition Sliding window Sliding window
Sum of a range, many range queries, "subarray sums to k" Prefix sums, plus a hash map Prefix sums
Count, find duplicates, "does the complement exist" Hash map or set Hashing patterns
Sorted data, or a yes/no condition that flips once Binary search Binary search
"Minimize the maximum" or "smallest value that works" Binary search on the answer On the answer
Next greater/smaller element, histogram, nearest to the left Monotonic stack Monotonic stack
Top k, k-th largest, merge sorted streams, repeated min/max Heap Heaps
Minimum steps in a grid or unweighted graph BFS BFS
Weighted shortest path, non-negative weights Dijkstra Dijkstra
Connected groups, merging sets over time Union-find or DFS Union-find
Prerequisites, ordering with dependencies Topological sort Topological sort
Generate all subsets, permutations, arrangements Backtracking Backtracking
"Number of ways", "min/max cost", choose-or-skip, overlapping subproblems Dynamic programming DP
A local best choice is provably safe; intervals, scheduling Greedy Greedy
Prefix lookups, autocomplete, dictionary of words Trie Tries
Tree question Recursion that returns a value from each subtree Tree problems
Linked list cycle, middle, k-th from end Slow and fast pointers Linked list techniques
Powers of two, parity, finding the single odd item Bit manipulation Bit manipulation

When two rows seem to fit, prefer the one that matches the input's shape (sorted, a tree, a graph) before the one that matches the question's wording. A sorted array and a "sum" together mean two pointers, even if hashing would also work.

Templates

Every template below runs as is. They are deliberately small: the point is the shape of the code, which you adapt rather than memorise.

Two pointers and sliding window

Two pointers walk a sorted array from both ends and use the sorted order to decide which end to move. A sliding window keeps a range [start, i] that always satisfies a condition, moving start forward whenever the condition breaks:

Python Template: two pointers and a window

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both run in O(n) because each pointer only moves forward.

Prefix sums with a hash map

If prefix[j] - prefix[i] == k, then the elements between i and j sum to k. So while scanning, count how many earlier prefixes equal current_prefix - k:

Python Template: subarrays that sum to k

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The brute force is O(n^3) here (O(n^2) with running sums); the hash-map version is O(n). Negative numbers are why a plain sliding window cannot do this job, and why the prefix trick is worth knowing.

Binary search on the answer

When "is x big enough?" is a yes/no question that flips from no to yes as x grows, binary search the value of x and write a feasible(x) check. This template finds the smallest truck capacity that delivers all packages, in order, within a number of days:

Python Template: binary search on the answer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop runs O(log(sum)) times and each check is O(n).

BFS for fewest steps

BFS explores a graph in rings: all cells one step away, then two, and so on, so the first time it reaches the goal is a shortest path. A queue holds the frontier and a visited set prevents loops:

Python Template: BFS on a grid

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Mark cells as seen when you enqueue them, not when you dequeue, or the same cell can enter the queue many times.

Backtracking: choose, explore, undo

Backtracking builds a solution one decision at a time, and undoes the decision to try the next option. The template always has the same three lines: choose, recurse, unchoose. Here it finds every group of distinct numbers that adds up to a target:

Python Template: backtracking

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Heaps: top k and merging

A heap gives you the smallest (or largest) element repeatedly in O(log n). For top-k, keep a heap of size k; for merging sorted lists, keep one front element from each list:

Python Template: heap for top-k and merging

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Monotonic stack

A stack that stays sorted lets each element be pushed and popped once, turning "look for the next bigger value" from O(n^2) into O(n):

Python Template: monotonic stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Union-find and topological sort

Union-find answers "are these two connected?" while edges arrive. Topological sort orders tasks so every prerequisite comes first and detects impossible (cyclic) schedules:

Python Template: union-find and Kahn's algorithm

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Dynamic programming

When a problem asks for "the number of ways" or "the best value" and the same sub-problem keeps appearing, define the answer for a smaller input, write the recurrence, and cache it. Top-down with functools.cache is the quickest to write; the bottom-up table avoids recursion:

Python Template: dynamic programming

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two versions give the same answers; this is also why DP problems get a quick sanity check: solve them twice.

A quick decision flow

TEXT
Is the input sorted, or can it be sorted cheaply?  -> two pointers, binary search
Is it a contiguous range question?                 -> window, prefix sums
Is it a graph, grid or tree?                       -> BFS (fewest steps), DFS (explore all), Dijkstra (weights)
Do I need "all" solutions?                         -> backtracking
Do I need "how many" or "best" with repeated parts?-> DP
Do I repeatedly need the min or max?               -> heap
Do I need fast lookup by key?                      -> hash map or set
Is a locally best choice provably safe?            -> greedy (prove it first)

Common mistakes

  • Forcing a pattern. If the template needs three workarounds to fit, you probably picked the wrong row of the table.
  • Skipping the brute force. Writing the slow version first gives you a reference to test the clever version against.
  • Ignoring edge cases: empty input, one element, all equal values, negative numbers, and "no answer exists".
  • Using a sliding window with negative numbers when the condition is not monotonic. Use prefix sums instead.
  • Mutating shared state in recursion (appending current instead of current.copy() in backtracking).
  • Applying greedy without a proof. If you cannot argue why the local choice is safe, test it against DP or brute force.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A problem gives an array of 100,000 integers and asks for the number of subarrays with sum k, where values can be negative. Which approach fits?

    Negative values break the monotonic behavior needed for a sliding window or two pointers. Counting earlier prefix sums equal to prefix - k handles them in O(n).
  2. 2. What signal usually points to binary search on the answer?

    When feasibility is monotonic in some numeric parameter, you can binary search that parameter and test each candidate with a simple check.
  3. 3. n is about 20 and you must consider every way to choose some of the items. Which complexity is acceptable?

    2^20 is about a million subsets, which is fine. 20! is far too large, so subsets (backtracking or bitmasks) are the intended tool.
  4. 4. Why do you mark a cell as visited when you add it to the BFS queue, not when you remove it?

    A cell reachable from several neighbours would otherwise be enqueued multiple times, which wastes time and can blow up the queue.
  5. 5. In the backtracking template, why do we append current.copy() to the results?

    current is changed on every choose and unchoose step. Storing the same object means all results would end up showing its final (usually empty) state.

Summary

  • First read the constraints to choose a target complexity, then match signals in the statement to a technique.
  • Sorted input and pair sums mean two pointers; contiguous ranges mean windows or prefix sums; yes/no monotonic checks mean binary search on the answer.
  • Fewest steps in an unweighted graph is BFS; ordering with dependencies is topological sort; all solutions is backtracking; counting or optimising with overlap is DP.
  • Heaps handle top-k and merging; a monotonic stack handles "next greater" questions; union-find handles connectivity as edges arrive.
  • Always write or imagine the brute force first, and test edge cases: empty, single, duplicates, negatives, no answer.
  • Patterns are starting points. Prove or test the choice, then check the complexity against the limits.

Next: Choosing the Right Data Structure