Space complexity measures extra memory beyond the input. An in-place loop uses O(1) auxiliary space; building a frequency table uses O(k) for k distinct keys.
Auxiliary vs total
- Auxiliary space — extra allocations (hash map, recursion stack)
- Total space — includes input storage (often not counted in interview auxiliary answer)
Recursion stack
DFS recursion depth h uses O(h) stack frames—deep skewed trees can overflow stack; iterative BFS uses explicit queue instead.
Frequency map space
#include
#include
#include
int main() {
std::vector a = {1, 2, 1, 3, 2, 1};
std::unordered_map freq;
for (int x : a) freq[x]++;
std::cout << "distinct keys = " << freq.size() << " (O(k) extra)\n";
return 0;
} Important interview questions and answers
- Q: Two-sum with hash map space?
A: O(n) for storing seen values in worst case. - Q: In-place sorting?
A: Some algorithms O(1) auxiliary; merge sort needs O(n) temp array.
Self-check
- Define auxiliary space complexity.
- DFS on tree of height h uses what stack space?
Tip: State auxiliary space separately from input size when asked in interviews.
Interview prep
- Auxiliary space?
Extra memory beyond input—hash table, recursion stack, DP table.
- Two-sum space?
O(n) for hash map of seen values.