Space Complexity

Alright, here’s the 3-step quick-check formula I give my interview prep students for space complexity:

---

Step 1 – Identify extra data structures

• Look for lists, sets, dicts, heaps, stacks you created.
• Ignore the input itself — it’s not “extra space”.
• Ask: “Does this structure grow as n grows?”

---

Step 2 – Check recursion or call stack

• If recursion is used, max depth = O(depth) space.
• Example: DFS on a binary tree with height h → O(h) space.

---

Step 3 – Combine

• Add the biggest growing space usages.
• Drop constants and smaller terms (Big-O rule).

---

✅ Examples

Example 1 – Hash Map

def hasDuplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

• seen → can hold up to n numbers → O(n).
• No recursion.
• Final space: O(n).

---

Example 2 – Two Pointers

nums.sort()
l, r = 0, len(nums) - 1
while l < r:
    ...

• Extra variables l, r → constant size.
• Final space: O(1).

---

Example 3 – DFS on Tree

def dfs(node):
    if not node: return
    dfs(node.left)
    dfs(node.right)

• No extra DS, but recursion depth = tree height h.
• Final space: O(h).

---