Space complexity

Extra memory your algorithm needs — including the call stack you don't see.

Big idea

Space complexity measures how much extra memory an algorithm uses as n grows. Count the data structures you create and the recursion stack — and remember that trading memory for time is often the best deal available.

Auxiliary space

We usually count auxiliary space: memory beyond the input itself. The input is there anyway; what did your algorithm add?

def reverse_copy(nums):
    return nums[::-1]          # new list of n items: O(n) extra

def reverse_in_place(nums):
    i, j = 0, len(nums) - 1
    while i < j:
        nums[i], nums[j] = nums[j], nums[i]
        i, j = i + 1, j - 1    # two integers: O(1) extra

Both reverse the list in O(n) time. The second uses O(1) space — "in place". When a problem says "without extra space" or "modify the array in place", it's asking for that.

Common costs

You create…	Extra space
A few counters or pointers	O(1)
A copy of the input, a hash set of seen items, a result list	O(n)
An n × n grid (e.g. a 2D DP table)	O(n²)
A DP table with rows for one string and columns for another	O(n × m)
A fixed-size count array for 26 letters	O(1) — the size doesn't grow with n

The last row trips people up: an array of 26 counters is constant space, because its size is fixed no matter how long the string is.

The hidden cost: the call stack

Every recursive call that hasn't returned yet holds a stack frame — its parameters and local variables. The space used is the maximum depth of the recursion, not the total number of calls.

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

No lists, but n frames are alive at the deepest point: O(n) space. With n = 100,000, Python hits its default recursion limit (about 1,000) long before that — a loop would use O(1).

Loading diagram

The stack at its deepest for sum_to(3): every frame waits for the one above it

For a balanced binary tree, recursive traversal has depth log n, so O(log n) stack space. For a tree that's really a long chain, the depth is n.

Watch it

Trading space for time

The classic trade: spend O(n) memory to save a factor of n in time.

Problem	Without extra memory	With a hash set or map
Any duplicates?	Compare every pair: O(n²) time, O(1) space	One pass with a set: O(n) time, O(n) space
Two numbers summing to a target	O(n²)	O(n) with a map of seen values

Memoization in dynamic programming is the same deal: store each sub-answer once (memory) so you never recompute it (time).

Say both numbers in an interview: "O(n) time and O(n) space; if memory were tight I could sort and use two pointers for O(n log n) time and O(1) extra space."

Quick check

A recursive function calls itself on n − 1 down to 0 and creates no data structures. What is its space complexity?

You count letters in a string of length n using an array of 26 integers. How much extra space is that?

Which of these uses O(1) auxiliary space?