When space complexity matters
“Interviewers ask about space complexity. When does it actually matter, and how do you reason about it?”
What this tests
- Whether the candidate accounts for all memory: auxiliary structures, recursion stack, and output.
- Whether they know the standard space reductions (rolling DP arrays, in-place two pointers, iterative traversal).
- Judgement about time/space tradeoffs rather than treating space as free.
Strong answer
Space complexity counts auxiliary memory beyond the input: explicit structures (hash maps, DP tables), the recursion stack, and sometimes the output itself if it is large. A strong candidate lists all three; the recursion stack is the one people forget — recursive DFS on a tree is O(h), and on a degenerate tree h = n.
It matters in three situations. Memory limits: a 10^5 × 10^5 DP table is 10^{10} cells — impossible — so you need a 1D rolling array or a different state. Streams: if data is unbounded you must keep O(k) or O(1) state (top-k with a heap, reservoir sampling). Explicit requirements: "in place" or "O(1) extra space" forces two pointers, index marking, or bit tricks instead of a hash set.
The standard reductions: a 2D DP that only reads the previous row becomes two rows (Grid DP, Longest Common Subsequence); a hash set used for "seen" can become a sort plus adjacent comparison when reordering is allowed; recursion becomes an explicit loop; and a full array of prefix sums becomes a running sum when only the current prefix is needed. They also weigh the tradeoff honestly: an O(n) hash map that turns O(n^2) into O(n) is almost always worth it.
Green flags · Red flags
- Counts recursion stack as space.
- Knows the rolling-array trick and can say which DP transitions allow it.
- Knows in-place patterns: two pointers, negating values as visited marks, cycle detection instead of a set.
- Frames space as a tradeoff and gives a case where spending memory is clearly right.
- Reports
O(1)space for a recursive solution. - Says space "never matters in practice".
- Cannot reduce a 2D DP to 1D when the transition only uses the previous row.
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.
n+1 integers in 1..n with O(1) space and no modification.O(min(m, n)) space?