DSA Interview Prep · Lesson

Space Complexity and Trade-offs

Measure auxiliary space for call stacks and auxiliary data structures, and recognise time-space trade-offs in memoisation and in-place algorithms.

Space Complexity and Trade-offs is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

What Does Space Complexity Measure?

Space complexity measures the extra memory beyond the input, called auxiliary space. A few variables is O(1); a result array or hash map is O(n). See the code.

# O(1) auxiliary space
def sum_array(nums):
    total = 0       # one integer variable
    for n in nums:
        total += n  # constant extra space
    return total

# O(n) auxiliary space
def copy_array(nums):
    return list(nums)  # allocates n slots

print(sum_array([1, 2, 3, 4]))  # 10
print(copy_array([1, 2, 3, 4]))  # [1, 2, 3, 4]

Call Stack Space in Recursion

Each recursive call adds a stack frame, so depth sets the space. Linear recursion is O(n); balanced tree DFS is O(log n). An iterative version can control this better.

import sys

def recursive_sum(n):
    if n == 0: return 0
    return n + recursive_sum(n - 1)
# Space: O(n) stack frames

def iterative_sum(n):
    total = 0
    while n > 0:
        total += n
        n -= 1
    return total
# Space: O(1)

print(recursive_sum(100))   # 5050
print(iterative_sum(100))   # 5050

Merge Sort Space: O(n)

Merge sort needs O(n) extra space for its temporary arrays. That is the price of a stable O(n log n) sort — heap sort saves space but is not stable. See the code.

import tracemalloc

tracemalloc.start()

def merge_sort(arr):
    if len(arr) <= 1: return arr
    m = len(arr) // 2
    l = merge_sort(arr[:m])    # new list
    r = merge_sort(arr[m:])    # new list
    out, i, j = [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]: out.append(l[i]); i+=1
        else:             out.append(r[j]); j+=1
    return out + l[i:] + r[j:]

data = list(range(1000, 0, -1))
merge_sort(data)
_, peak = tracemalloc.get_traced_memory()
print(f'Peak memory: {peak} bytes')  # proportional to n

In-Place Algorithms: O(1) Space

An in-place algorithm changes the input directly with no extra proportional storage — like reversing an array with two pointers. That keeps space at O(1). See the code.

def reverse_inplace(arr):
    l, r = 0, len(arr) - 1
    while l < r:
        arr[l], arr[r] = arr[r], arr[l]  # swap
        l += 1
        r -= 1
    # Space: O(1) -- only two pointer variables

def rotate_right(arr, k):
    '''Rotate array right by k positions in-place.'''
    n = len(arr)
    k %= n
    arr.reverse()          # O(1) space
    arr[:k] = arr[:k][::-1]
    arr[k:]  = arr[k:][::-1]

a = [1, 2, 3, 4, 5]
rotate_right(a, 2)
print(a)  # [4, 5, 1, 2, 3]

Time-Space Trade-off: Two-Sum

The time-space trade-off is everywhere. Two-sum is O(n^2) time with O(1) space, or O(n) time with O(n) space via a hash map. Mention both and ask what matters more.

# O(n^2) time, O(1) space
def two_sum_slow(nums, target):
    for i in range(len(nums)):          # O(n)
        for j in range(i+1, len(nums)): # O(n)
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

# O(n) time, O(n) space
def two_sum_fast(nums, target):
    seen = {}                    # O(n) space
    for i, n in enumerate(nums):
        comp = target - n
        if comp in seen:         # O(1) lookup
            return [seen[comp], i]
        seen[n] = i
    return []

print(two_sum_fast([2, 7, 11, 15], 9))  # [0, 1]

Memoisation vs Tabulation Space

Top-down memoization costs O(n) memo plus O(n) stack; bottom-up tabulation skips the stack. Keeping only the last few rows shrinks it to O(1) — space-optimized DP.

# Fibonacci: O(n) space with full 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]

# O(1) space: keep only last two values
def fib_optimal(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print(fib_table(10))    # 55
print(fib_optimal(10))  # 55

Hash Map Space: O(n)

A hash map is the usual O(n) space cost in solutions: a seen-set for visited, a frequency map for counting. Always report it — "O(n) time, O(n) space" is the full answer.

def contains_duplicate(nums):
    # O(n) time, O(n) space
    seen = set()
    for n in nums:
        if n in seen: return True
        seen.add(n)
    return False

def group_anagrams(words):
    # O(n*m) time, O(n) space  (m = avg word length)
    from collections import defaultdict
    groups = defaultdict(list)
    for w in words:
        groups[tuple(sorted(w))].append(w)
    return list(groups.values())

print(contains_duplicate([1,2,3,1]))  # True
print(group_anagrams(['eat','tea','tan','ate','nat','bat']))

Space Analysis for Graph Algorithms

Graphs cost real space: an adjacency list is O(V + E), a BFS visited set and queue are O(V), and DFS recursion is O(V) deep. Report graph space in V and E.

from collections import deque

def bfs(graph, start):
    # Space: O(V) for visited set + O(V) for queue
    visited = set()      # O(V)
    queue = deque([start])  # O(V) max
    order = []
    while queue:
        node = queue.popleft()
        if node in visited: continue
        visited.add(node)
        order.append(node)
        for nb in graph.get(node, []):
            queue.append(nb)
    return order

g = {0:[1,2], 1:[3], 2:[3], 3:[]}
print(bfs(g, 0))  # [0, 1, 2, 3]

String and Array Allocation Pitfalls

Hidden allocations sneak in O(n) space: slicing makes a new list, and + on strings in a loop is O(n^2). sorted() copies, but lst.sort() stays in place. See the code.

# Hidden allocations:
nums = [1, 2, 3, 4, 5]

# Creates a NEW list -- O(n) space
slice_copy = nums[1:4]  # [2, 3, 4]

# Creates a NEW sorted list -- O(n) space
sorted_copy = sorted(nums)  # nums unchanged

# Sorts IN PLACE -- O(1) extra space
nums.sort()

print(slice_copy)   # [2, 3, 4]
print(sorted_copy)  # [1, 2, 3, 4, 5]
print(nums)         # [1, 2, 3, 4, 5]

Recognising Space Trade-offs in Interviews

State your space complexity up front. If the interviewer wants less, common moves are bottom-up DP over a memo, or an in-place sort over a hash map. See the code.

# Problem: find if array has duplicates
# Option 1: O(1) time-per-check, O(n) space
def has_dup_hash(nums):
    return len(nums) != len(set(nums))

# Option 2: O(n log n) time, O(1) extra space
def has_dup_sort(nums):
    nums_copy = sorted(nums)  # O(n) space -- still!
    for i in range(1, len(nums_copy)):
        if nums_copy[i] == nums_copy[i-1]:
            return True
    return False

# Option 3: truly O(1) extra -- sort in-place
def has_dup_inplace(nums):
    nums.sort()               # modifies original
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]: return True
    return False

Total Complexity Statement Template

Always give the complete statement — time and space: "O(n) time, O(1) extra space." Mention trade-offs when they exist. That is what sets senior candidates apart.

# Complete complexity example: Merge Intervals
def merge_intervals(intervals):
    # Time: O(n log n) for sort + O(n) for merge = O(n log n)
    # Space: O(n) for output (could be n/2 to n intervals)
    intervals.sort(key=lambda x: x[0])  # O(n log n)
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]

Quick Check

Quick check — let us see how the space-complexity ideas landed. You are ready for this. ✅

Lesson Recap

Recap: auxiliary space is counted apart from input, recursion uses O(depth) stack space, and the time-space trade-off drives most algorithm design choices.

Frequently asked questions

Is the “Space Complexity and Trade-offs” lesson free?

Yes — the full text of “Space Complexity and Trade-offs” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.

What will I learn in “Space Complexity and Trade-offs”?

Measure auxiliary space for call stacks and auxiliary data structures, and recognise time-space trade-offs in memoisation and in-place algorithms. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start DSA Interview Prep?

No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Space Complexity and Trade-offs” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this DSA Interview Prep lesson?

Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

← Back to DSA Interview Prep