Reference
Coding patterns
Interview problems tend to reuse a handful of patterns. Knowing the typical cost of each lets you estimate a solution before you write it.
These are typical complexities, not guarantees. The real cost depends on the problem, on how you implement the pattern, and on any extra work such as sorting the input first. Always check the bound against your own code.
| Coding pattern | Typical time complexity | Typical auxiliary space | Typical problems and caveats |
|---|---|---|---|
| Two pointers | O(n) | O(1) | Pair sum on a sorted array, removing duplicates in place, palindrome check. If the input is not sorted and the pattern needs it, add O(n log n) for the sort. |
| Sliding window | O(n) | O(1) or O(n) | Longest substring or subarray under a constraint. Space is O(1) for a running sum or count, and grows when the window stores its contents, such as a character map or a deque for the window maximum. |
| Prefix sums | O(n) preprocessing; O(1) per range sum | O(n) | Many range-sum queries on a fixed array. Updates to the array force a rebuild, or a Fenwick or segment tree instead. |
| Hash map frequency counting | Expected O(n) total | O(n) | Anagrams, duplicates, two-sum. Relies on expected O(1) hash operations; heavy collisions can make a single operation O(n). |
| Monotonic stack | O(n) total | O(n) | Next greater element, daily temperatures, largest rectangle in a histogram. Each item is pushed and popped at most once. |
| Backtracking and subsets | O(2n) output generation | Depends on implementation | Recursion depth alone is O(n). Storing every subset needs O(n·2n) space, and copying each subset into the result adds a factor of n to the time. |
| Permutations | O(n·n!) to generate all permutations | Depends on output and implementation | There are n! permutations of length n. Recursion depth is O(n); storing all of them takes O(n·n!). |
| Dynamic programming | Number of states × transitions per state | Depends on memoization or tabulation | Knapsack with n items and capacity W has n·W states with two transitions each, so O(n·W) time. Tabulation often lets you keep only the previous row, cutting space to O(W). Memoization also uses recursion stack space. |
Topics on this page
Each one has its own page with an explanation, code, and the mistakes people make.
- Two pointers
O(n)
- Sliding window
O(n)
- Prefix sums
O(n) to build; O(1) per range sum
- Hash map frequency counting
Expected O(n) total
- Backtracking and subsets
O(2ⁿ) subsets; O(n · 2ⁿ) including copying each one
- Permutations
O(n · n!) to generate all
- Dynamic programming
Number of states × transitions per state