Space Complexity Explained — With Examples for Every Interview Pattern

Space complexity is where interviewers catch candidates who've memorised time bounds without understanding them. "O(1) space, no allocations" is a favourite answer for recursive solutions — and a favourite catch when the interviewer asks "what about the call stack?" This post is the worked-example reference: what counts, what doesn't, and the recursion-stack trap that turns a confident O(1) answer into a stumbling O(n).

What space complexity actually measures

Bytes your algorithm uses besides the input, expressed as a function of input size n.

Three questions define the number, and interviewers grade you on getting each right:

1. Does the input count? By interview convention, no. If the input is a list of n integers, it takes O(n) memory to exist, but that doesn't count as your algorithm's space complexity. Exception: if the interviewer asks about "total memory used", separate it — "the input is O(n), my auxiliary state is O(k)".
2. Does the output count? Sometimes. If you're returning 2ⁿ subsets, the output is O(n · 2ⁿ) — and yes, it counts. Interviewers accept "O(n · 2ⁿ) output + O(n) auxiliary" as the clean answer; often what they're looking for.
3. Does the recursion stack count? Yes. This is the classic gotcha. A recursive DFS on a linked list of n nodes uses O(n) space in the call stack, even if it "doesn't allocate anything".

Two words worth learning:

• Auxiliary space: memory allocated by the algorithm beyond input and output. This is the number interviewers usually want.
• Total space: input + output + auxiliary. Rarely the answer, occasionally asked.

The recursion-stack trap

Recursive code often looks O(1) space until you remember the call stack.

def reverse_list_recursive(head):
    if not head or not head.next:
        return head
    new_head = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

Zero allocations, zero explicit data structures. Auxiliary space: O(n) — one stack frame per node on the recursion path, all the way down before any of them return.

The iterative equivalent:

def reverse_list_iterative(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

Same algorithm, three named pointers, no recursion. Auxiliary space: O(1).

Both are O(n) time and produce the same output. On a linked list of a million nodes, the recursive version stack-overflows in Python (default limit ~1000) and burns real memory in every other language.

The rule. If a function calls itself and the maximum recursion depth is proportional to n, that's O(n) auxiliary space — not O(1) — regardless of what the function body allocates.

Space complexity, pattern by pattern

Sliding window

def longest_substring_without_repeats(s):
    seen = set()
    left = 0
    best = 0
    for right, ch in enumerate(s):
        while ch in seen:
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

Auxiliary space: O(k) where k is the size of the character alphabet — at most 128 for ASCII, at most a few thousand for full Unicode. Some interviewers accept O(1) because k is bounded; others want the O(k) answer. Both are defensible; the O(k) version is more careful. See the sliding-window pattern post.

Two-pointer

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Two named indices, no auxiliary structures. O(1) auxiliary.

Caveat: if the problem requires sorting first (LC 15 3Sum), the sort's own auxiliary space kicks in — O(1) for in-place heapsort, O(n) for merge sort or for Timsort's merge buffer (Python's list.sort()). The interview-safe answer for a two-pointer solution that requires sorting is O(n) auxiliary if you're honest about Timsort's worst case, or O(1) if you sort with heapsort explicitly. See the two-pointer pattern post.

Binary search — iterative vs recursive

Same problem, two auxiliary bounds:

def binary_search_iterative(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
# Auxiliary: O(1)

def binary_search_recursive(nums, target, low, high):
    if low > high:
        return -1
    mid = low + (high - low) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        return binary_search_recursive(nums, target, mid + 1, high)
    else:
        return binary_search_recursive(nums, target, low, mid - 1)
# Auxiliary: O(log n) — recursion depth

Interviewers who care about O(1) space specifically ask for iterative. The binary-search template post uses the iterative form throughout for exactly this reason.

Sort — in-place vs allocated

nums.sort()  # Python — Timsort, O(n log n) time, O(n) auxiliary

Timsort's O(n) auxiliary is easy to overlook because there's no visible allocation in the caller's code. If the interviewer asks for in-place sorting with O(1) auxiliary, that's heapsort — O(n log n) time, O(1) space. Interviewers rarely require it, but knowing the option exists is a credit-earning aside.

Other bounds worth memorising:

• Merge sort (canonical): O(n log n) time, O(n) auxiliary (the merge buffer).
• Quicksort: O(n log n) time average, O(n²) worst; O(log n) auxiliary average, O(n) worst (recursion depth on bad pivots).
• Heapsort: O(n log n) time, O(1) auxiliary. The only comparison-sort with true O(1) space.

DFS — recursive

def dfs(node, visited):
    if node in visited:
        return
    visited.add(node)
    for neighbour in node.neighbours:
        dfs(neighbour, visited)

Two contributions:

1. visited set: O(V).
2. Recursion stack: O(depth). Balanced binary tree: O(log n). Skewed tree or long chain: O(n).

Total: O(V) worst case — the visited set dominates, but the recursion stack is a real second contribution.

BFS

from collections import deque

def bfs(start):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbour in node.neighbours:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

Auxiliary space: O(V) — visited set plus queue, both bounded by V. On a perfectly balanced binary tree at depth d, the queue's peak size is O(2ᵈ) — the widest level dominates.

This is the key trade-off named in the BFS vs DFS post: BFS's space is the tree's width; DFS's space is its depth. On a wide-but-shallow tree, DFS wins the space fight. On a narrow-but-deep tree, BFS wins.

Backtracking

def subsets(nums):
    result = []

    def backtrack(start, current):
        result.append(current[:])
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    backtrack(0, [])
    return result

Two space contributions to name separately:

• Auxiliary during the search: O(n) — recursion depth n, plus current list of size ≤ n.
• Output: O(n · 2ⁿ) — 2ⁿ subsets of average length n/2.

The interview-clean answer is "O(n · 2ⁿ) including output, O(n) auxiliary". Naming the split is the credit-earning move. See the backtracking template post.

Dynamic programming — memoisation

from functools import cache

@cache
def coin_change(amount):
    if amount == 0:
        return 0
    if amount < 0:
        return float('inf')
    return min(coin_change(amount - c) for c in coins) + 1

Auxiliary space: O(amount) for the memo, plus O(amount) for the recursion depth in the worst case. Total O(amount), but the split matters — an iterative bottom-up rewrite removes the recursion-stack half.

For classic 2D DP (LCS, edit distance), states are O(n · m), which is auxiliary space O(n · m).

DP with rolling array

The most common space optimisation. If the recurrence only reads the last k rows, keep only those k rows.

# Fibonacci with the full DP table
def fib_table(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
# Auxiliary: O(n)

# Fibonacci with rolling values
def fib_rolling(n):
    if n < 2:
        return n
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b
# Auxiliary: O(1)

Same algorithm, same time complexity, same output. The rolling version discards dp[0..i-2] because the recurrence only reads the two most recent values.

The generalisation: if the recurrence only depends on the last k rows, keep only those k rows — O(k · width) instead of O(n · width). Edit distance drops from O(n · m) to O(m) space. LCS the same. Knapsack O(n · W) drops to O(W). This is one of the most common follow-up questions after an interviewer accepts the initial DP solution.

Frequency counters and bounded universes

from collections import Counter
counts = Counter(s)   # O(unique chars in s)

For lowercase-English-letter inputs, this is O(26) = O(1). Interviewers accept both "O(1)" (bounded alphabet) and "O(k) where k is the alphabet size"; the second is the more careful answer and the one that generalises to Unicode.

Space optimisations worth recognising

• Two pointers over one auxiliary array. Many problems that look like they need an auxiliary array can be done in-place with a two-pointer scan. LC 26 (Remove Duplicates), LC 88 (Merge Sorted Array).
• Rolling variables over DP tables. If only the last k rows matter, keep k variables (or a length-k array). Fibonacci, edit distance, knapsack.
• In-place modification of input. LC 200 (Number of Islands) overwrites '1' → '0' for visited cells — trades input mutation for O(1) auxiliary. Ask the interviewer whether mutation is allowed.
• Iterative over recursive. Removes the O(depth) call-stack cost. See the binary-search example above; every recursive DFS has an iterative form that saves the same amount.
• Bit manipulation over sets. For n ≤ 32 or n ≤ 64, a single integer as a bitset replaces an O(n) set with a constant. LC 78 (Subsets) can enumerate all subsets via for mask in range(1 << n).

Each optimisation trades one axis for another. Rolling arrays trade "keeping history" for space. In-place modification trades input immutability for space. Iterative-over-recursive trades one style of code for space. None of them are pure wins; interviewers know this and will sometimes ask for the trade-off explicitly.

How to argue space complexity in an interview

Three-line script that beats hand-waving:

1. Name every allocation. "The visited set holds up to V nodes. The queue holds up to V nodes."
2. Sum, drop constants and dominated terms. "So the total auxiliary is O(V) + O(V) = O(V)."
3. Call out whether recursion counts. "This is iterative, so no call-stack contribution. If we did it recursively, we'd add O(depth) = O(log n) for a balanced input, O(n) worst case."

If the interviewer asks about the output, split it out: "The output is O(n · 2ⁿ), auxiliary is O(n)." Naming the split earns credit. Bundling everything into a single "O(n · 2ⁿ)" number is technically correct but shows less care.

Common bugs in space-complexity claims

• "Iterative, so O(1) space." Not if you allocate an auxiliary array. dp = [0] * n is O(n) auxiliary regardless of loop style.
• "Recursive, so O(log n) space." Only if the recursion depth is O(log n). DFS on a long chain is O(n) recursion depth.
• "Nothing allocated, so O(1) space." If you're returning a list of results, the output is O(result size). Auxiliary and output are separate; interviewers keep them separate; you should too.
• "No hash map, so O(1) space." A Counter or set is O(distinct-values) auxiliary. Even a bounded-alphabet counter is O(k) — only O(1) if k is a fixed constant, and that fact deserves naming out loud.
• "O(1) space because the input is O(n) and I only use a few pointers." Correct number, wrong reasoning. The input doesn't count against auxiliary; the "few pointers" is why the answer is O(1), not the input size.

Cross-references

• The Big-O cheat sheet covers time and space bounds for every common data structure and algorithm in one page — including the "Space complexity essentials" section that this post expands with examples.
• The Time complexity of common operations post covers the per-language time bounds; the corresponding space cost of each operation (str.slice(a, b) allocates O(b − a), list.copy() allocates O(n)) follows the same shape.
• The Python interview cheat sheet covers the idioms that produce or avoid the allocations above — ''.join(pieces) for O(n) instead of O(n²), collections.deque for O(1) queue ops, sys.setrecursionlimit for when iterative isn't an option.

Every pattern post's space claim is grounded in the model this post explains:

• The sliding-window pattern claims O(k) auxiliary — the window's frequency counter.
• The two-pointer pattern claims O(1) — no auxiliary structure, plus optional O(log n) for a preceding sort.
• The binary-search template claims O(1) iteratively, O(log n) recursively — same algorithm, different call-stack cost.
• The monotonic-stack pattern claims O(n) — the stack itself, worst-case size n.
• The backtracking template claims O(depth) auxiliary + O(count × solution size) output.
• The BFS vs DFS decision post hinges on the width-vs-depth trade-off — each traversal wins the space fight on different graph shapes.

The pattern posts assume you can reason about space at the level this post explains. If any of the examples above surprised you, re-read the pattern post it belongs to — the confusion is probably in the invariant, not the space arithmetic.