💾 Space Complexity: Memory Efficiency

While Time Complexity is about speed, Space Complexity is about memory. In environments with limited RAM (like mobile devices or embedded systems), optimizing space is just as critical as optimizing time.

💡 The Logic (ELI5)

Think of your algorithm as a chef:

O(1): The chef needs only one cutting board, regardless of how many guests are coming.
O(n): The chef needs one plate for every single guest. If 100 people come, you need 100 plates.
O(log n): The chef keeps a small stack of notes that grows very slowly even as the number of orders increases.

🔍 The Deep Dive

What counts as Space?

Space complexity includes two parts:

Auxiliary Space: Extra space used by the algorithm (temporary variables, data structures).
Input Space: Space used by the input itself (usually ignored when we talk about Auxiliary space).

The Stack Trace (Hidden Space)

Many developers forget about the Recursion Stack. Every time a function calls itself, it consumes space on the call stack. A recursive function with a depth of $n$ takes O(n) space, even if it doesn't create any new data structures!

Complexity	Common Cause
O(1)	Primitive variables, fixed-size buffers
O(log n)	Balanced trees, divide and conquer stacks
O(n)	Storing input in a Set/Map, recursive stack depth $n$
O(n²)	Storing a 2D matrix ($n \times n$)

🛠️ Code Forge: Space Examples


javascript Standard
/**
 * O(1) - Constant Space
 * We only use a single variable 'sum', regardless of array size.
 */
function sumArray(arr) {
  let sum = 0; // O(1) space
  for (let num of arr) {
    sum += num;
  }
  return sum;
}

/**
 * O(n) - Linear Space
 * We create a new Map that grows with the size of the input.
 */
function getFrequency(arr) {
  const counts = new Map(); // O(n) space
  for (let item of arr) {
    counts.set(item, (counts.get(item) || 0) + 1);
  }
  return counts;
}

/**
 * O(n) - Recursion Stack Space
 * Even though no new arrays are created, the stack depth is 'n'.
 */
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1); // Max stack depth is 'n'
}

🎯 Interview Pulse

The Time-Space Tradeoff

This is a recurring theme in interviews. You can often make an algorithm faster by using more space (e.g., using a HashMap to reduce $O(n^2)$ to $O(n)$).

Optimization Checklist

Do we need a copy? Can we modify the input "In-Place" to save $O(n)$ space?
Iterative vs Recursive? Can we convert a recursive solution to an iterative one to save stack space?
Bit Manipulation? Can we use bits to represent boolean states instead of a full array?