---
title: "Algorithm patterns: all 52, and which one a problem needs"
url: https://algopath.pro/patterns
language: en
summary: "Most interview problems are one of a small number of shapes wearing a new story. Each page below names the shape, the words in a problem that point at it, and the neighbour it gets confused with."
---

# Algorithm patterns: all 52, and which one a problem needs

## Arrays

- [In-place array transform](https://algopath.pro/patterns/in-place-array) - O(n)
  A write index trails the read index over one buffer. You copy back only what you keep, so a second array is never allocated.

## Hashing

- [Hash set / map](https://algopath.pro/patterns/hash-set-map) - O(n)
  A hash structure turns a lookup into a single step. A set answers whether a value was seen, a map answers how many times.

## Two pointers

- [Two pointers (opposite ends)](https://algopath.pro/patterns/two-pointers-opposite) - O(n)
  Two indices start at the ends of a sorted array and walk toward each other. Each step moves whichever side is holding the answer back.
- [Two pointers (same direction)](https://algopath.pro/patterns/two-pointers-same-direction) - O(n)
  A read pointer scans ahead while a write pointer trails behind it. The write pointer moves only when a value is worth keeping.

## Sliding window

- [Sliding window (fixed size)](https://algopath.pro/patterns/sliding-window-fixed) - O(n)
  A window of exactly k elements rolls one step at a time. Add the value coming in, drop the one going out, reuse the rest.
- [Sliding window (variable)](https://algopath.pro/patterns/sliding-window-variable) - O(n)
  Grow the window from the right, and shrink it from the left when the condition breaks. Neither end ever moves backwards.

## Prefix sums

- [Prefix sums](https://algopath.pro/patterns/prefix-sums) - O(n) build / O(1) query
  Store a running total of everything that comes before each index. A range sum then costs one subtraction instead of a loop.
- [Difference array](https://algopath.pro/patterns/difference-array) - O(n)
  Record the change at each index instead of the value. A range update costs two writes, and one final pass rebuilds everything.

## Searching

- [Linear search](https://algopath.pro/patterns/linear-search) - O(n)
  Walk the collection from one end and stop at the first item that matches. No order, no structure and no setup are needed.
- [Binary search (array)](https://algopath.pro/patterns/binary-search-array) - O(log n)
  Look at the middle of a sorted range and throw away the half that cannot hold the answer. Repeat until one item is left.
- [Binary search on a rotated array](https://algopath.pro/patterns/binary-search-rotated) - O(log n)
  A sorted array that was cut and swapped still has one sorted half at every step. Find that half, then pick a side to keep.
- [Binary search on the answer](https://algopath.pro/patterns/binary-search-on-answer) - O(n log(range))
  The thing you search here is the range of every possible answer. A yes-or-no test decides which half of it to throw away.

## Sorting

- [Elementary sorts (selection, bubble, insertion)](https://algopath.pro/patterns/elementary-sort) - O(n^2)
  Selection, bubble and insertion sort all compare neighbours and swap them. All three cost O(n squared) on a shuffled array.
- [Fast sort (merge / quick)](https://algopath.pro/patterns/fast-sort) - O(n log n)
  Cut the array in two, sort each part, then put them back together. Merge sort cuts by position, quick sort cuts by value.
- [Non-comparison sort (counting / radix)](https://algopath.pro/patterns/non-comparison-sort) - O(n)
  Counting and radix sort never compare two values. They read the key itself, which beats n log n when the range is small.
- [Sort with a custom comparator](https://algopath.pro/patterns/sort-comparators) - O(n log n)
  A comparator answers exactly one question: which of these two items comes first. The sort algorithm handles everything else.

## Intervals

- [Intervals: merge & insert](https://algopath.pro/patterns/intervals-merge) - O(n log n)
  Sort the intervals by start, then walk them once. Two neighbours merge whenever the next start is not past the current end.
- [Sweep line (event counting)](https://algopath.pro/patterns/sweep-line) - O(n log n)
  Turn each interval into a start event and an end event. Then sort all the events by position and walk them with a counter.

## Linked lists

- [Linked list reversal](https://algopath.pro/patterns/linked-list-reversal) - O(n)
  Walk the list once, and at every node flip its next pointer to the node behind it. Three local variables are all you need.
- [Fast & slow pointers](https://algopath.pro/patterns/fast-slow-pointers) - O(n)
  One pointer moves a single step at a time while the other moves two steps. The gap between them exposes cycles and midpoints.
- [Linked list merge & reorder](https://algopath.pro/patterns/linked-list-merge) - O(n + m)
  Build the answer on a dummy node and take from the front of each list. That dummy removes every empty-list special case.

## Stacks and queues

- [Stack (LIFO)](https://algopath.pro/patterns/stack) - O(n)
  A stack always hands back the most recent item first. That makes it the tool for anything that has to close in reverse order.
- [Monotonic stack](https://algopath.pro/patterns/monotonic-stack) - O(n)
  Keep the stack's values increasing from bottom to top. Pop everything the new value beats, and each pop just found its answer.
- [Monotonic deque (sliding window max/min)](https://algopath.pro/patterns/monotonic-deque) - O(n)
  A deque kept in order, so its front is always the window's maximum. Beaten values leave the back, expired ones the front.

## Recursion

- [Recursion](https://algopath.pro/patterns/recursion) - O(n)
  A function that calls itself on a smaller version of the same problem. A base case stops it, and the calls unwind back up.
- [Recursion with memoization](https://algopath.pro/patterns/memoization) - O(states)
  Recursion that writes down every answer it computes. When the same argument comes back, the stored value is handed back.

## Backtracking

- [Backtracking](https://algopath.pro/patterns/backtracking) - O(2^n)/O(n!)
  Make a choice, recurse, and then take the choice back. That undo is what lets a single array hold every candidate in turn.

## Trees

- [Tree traversal](https://algopath.pro/patterns/tree-traversal) - O(n)
  Visit every node of the tree exactly once. Where exactly you place the visit is what decides what the traversal computes.
- [Binary search tree](https://algopath.pro/patterns/bst) - O(log n) avg
  A search tree keeps all the smaller values to the left and the larger ones to the right. Every lookup drops one whole side.
- [Lowest common ancestor](https://algopath.pro/patterns/tree-lca) - O(n)
  The lowest common ancestor is the deepest node that has both targets below it. One post-order pass over the tree finds it.
- [Tree serialize / deserialize](https://algopath.pro/patterns/tree-serialize) - O(n)
  Write a tree out as one flat string, then rebuild it exactly. The markers for the missing children are what make it work.

## Heaps and top-k

- [Binary heap / priority queue](https://algopath.pro/patterns/binary-heap) - O(log n) per op
  A heap keeps the smallest value at the very top and puts nothing else in order at all. Pushing and popping each cost log n.

## Graphs

- [Graph BFS / DFS](https://algopath.pro/patterns/graph-bfs-dfs) - O(V+E)
  Walk a graph from a start node, marking everything you have seen. A queue gives the fewest hops, while a stack goes deep.
- [Connected components](https://algopath.pro/patterns/graph-components) - O(V+E)
  Start a new walk at every node you have not seen yet. Every walk that actually starts marks out one more connected group.
- [Topological sort (Kahn's algorithm)](https://algopath.pro/patterns/topological-sort) - O(V+E)
  Order the tasks so that every one of them comes after everything it depends on. Keep taking whichever node owes nothing.
- [Union-find (disjoint set)](https://algopath.pro/patterns/union-find) - near O(1) per op
  Every element points at a parent, and walking up reaches a root that names its group. Two elements match when their roots match.
- [Dijkstra's algorithm](https://algopath.pro/patterns/dijkstra) - O(E log V)
  Settle the closest node not yet settled, then relax all of its edges. A heap keeps that node always one single read away.
- [Eulerian path (Hierholzer's algorithm)](https://algopath.pro/patterns/eulerian-path) - O(E)
  Walk a graph using every one of its edges exactly once. Push a node the moment it gets stuck, then read the answer backwards.
- [Bipartite check (two-coloring)](https://algopath.pro/patterns/bipartite) - O(V+E)
  Colour any one node, then colour each of its neighbours in the other colour. A conflict proves the graph is not bipartite.

## Greedy

- [Greedy (exchange argument)](https://algopath.pro/patterns/greedy) - O(n log n)
  Take the best-looking choice right now and never revisit it. It works only when a proof says the local choice is always safe.

## Dynamic programming

- [Dynamic programming (1-D)](https://algopath.pro/patterns/dynamic-programming) - O(states)
  Answer a small version of the problem, store the result, then build the next one from that. Every state is computed once.
- [DP on subsequences (LIS / LCS / edit distance)](https://algopath.pro/patterns/dp-subsequence) - O(n^2)/O(nm)
  The state here is a pair of positions, one in each of the two sequences. Every cell asks whether those two items match up.
- [DP on intervals](https://algopath.pro/patterns/dp-interval) - O(n^3)
  The state is a range, and the transition picks the last move made inside it. The shorter ranges are always filled first.
- [DP on trees](https://algopath.pro/patterns/dp-on-trees) - O(n)
  Every node's answer is built out of the answers given by its own children. A single post-order pass computes all of them.

## Strings and dynamic programming

- [DP on strings (word break)](https://algopath.pro/patterns/dp-strings) - O(n^2)
  Cut the string at every position and ask whether that piece is valid. A table of reachable positions kills the repeats off.

## Strings

- [Trie (prefix tree)](https://algopath.pro/patterns/trie) - O(len) per op
  Words that share a prefix also share exactly the same path down from the root. A lookup costs only the length of that word.

## Bit manipulation

- [Bit manipulation](https://algopath.pro/patterns/bit-manipulation) - O(1)/O(n)
  Treat a whole number as a row of switches. Masks, shifts and XOR let you read or flip any one of those switches directly.

## Math and number theory

- [Math and number theory (GCD, sieve, modular)](https://algopath.pro/patterns/math-number-theory) - varies
  Number theory turns a loop over every single value into plain arithmetic. GCD, modular rules and a sieve replace brute force.

## Matrix

- [Matrix traversal (spiral / diagonal)](https://algopath.pro/patterns/matrix-traversal) - O(mn)
  Walk a grid in an order that the plain nested loops do not give you. Bounds or a direction rule decide the cell after this one.
- [Matrix search (sorted grid)](https://algopath.pro/patterns/matrix-search) - O(m+n)
  In a grid sorted both ways, one corner can only move in a single direction. Each comparison drops a whole row or column.
- [Matrix word search (grid DFS/backtracking)](https://algopath.pro/patterns/matrix-word-search) - O(mn*4^L)
  Search a grid by stepping into a neighbour and then stepping back out again. The cell stays marked while you are inside it.

## Advanced

- [Fenwick tree / segment tree](https://algopath.pro/patterns/fenwick-segment-tree) - O(log n) per op
  A tree built over the ranges answers a query and accepts an update, both in log n. Prefix sums cannot do the second one.