What is space complexity? How do auxiliary space and input space differ?

Space complexity

Space complexity measures extra memory an algorithm uses as input size n grows. Separate input space (the data you were given) from auxiliary space (allocations your algorithm adds).

• O(1) auxiliary: In-place swap, two pointers—only a few variables.
• O(n) auxiliary: Hash map of seen elements, output array copy.
• Recursive stack: DFS depth h can cost O(h) call frames—skewed tree → O(n).
• In-place sort caveat: Quick sort O(log n) stack on average; merge sort needs O(n) extra array.

// Two Sum hash map: O(n) time, O(n) extra space for map
// Reverse array in-place: O(1) extra space