Time complexity tells you how fast a solution runs. Space complexity tells you how much memory it needs while running.

Both matter. A solution can be fast but memory-heavy. Another solution can use almost no extra memory but take too long. Strong DSA problem-solving means knowing the tradeoff and choosing deliberately.

Space complexity is the habit of asking: what extra memory did my algorithm create, and how does that memory grow as the input grows?

1. Concept

What is space complexity?

Space complexity describes how the memory usage of an algorithm grows as the input size grows.

In DSA, we usually focus on auxiliary space, which means extra memory used by the algorithm beyond the input itself. If the input array already exists, we do not count the array as extra space unless the algorithm creates a copy of it.

For example:

function printAll(nums) {
  for (const num of nums) {
    console.log(num);
  }
}

This function loops through the input array, but it does not create another array, map, set, or recursive call stack. Its extra space is O(1).

Now compare it with:

function copyAll(nums) {
  const copy = [];

  for (const num of nums) {
    copy.push(num);
  }

  return copy;
}

This creates a new array that can grow to the same size as the input. Its extra space is O(n).

Why it exists

Memory is finite. If an algorithm creates too many objects, arrays, hash maps, or recursive calls, it can run out of memory even if the logic is correct.

In interviews, space complexity also shows whether you understand your own solution. If you use a hash map to improve time complexity, you should be able to say exactly what memory cost you paid for that speed.

Where it fits

Space complexity analysis belongs right next to time complexity:

/**
 * Time: O(n)
 * Space: O(n)
 */

Never state only time. Every complete DSA solution should include both.

2. Real-world Intuition

Imagine you are sorting documents on a desk.

Approach 1: You sort the documents directly on the same desk. You move papers around, swap their positions, and finish with the original stack sorted. You did not need another desk. This is like O(1) extra space.

Approach 2: You bring in a second empty desk and copy each document to the new desk in sorted order. This may be easier to organize, but now you need space for another full set of documents. This is like O(n) extra space.

Neither approach is automatically better. If the first desk is small and the second desk is available, copying may be fine. If space is limited, sorting in place may be required.

That is exactly how space complexity works in algorithms. Extra memory is a resource. Sometimes spending it makes the solution faster or simpler. Sometimes the problem explicitly asks you not to spend it.

3. Syntax / Implementation

Common space complexity patterns

// O(1) space — only a few variables
function sum(nums) {
  let total = 0;

  for (const num of nums) {
    total += num;
  }

  return total;
}

The variable total uses one memory slot regardless of whether nums has 10 elements or 10 million. Extra space is O(1).

// O(n) space — output array grows with input
function doubleValues(nums) {
  const doubled = [];

  for (const num of nums) {
    doubled.push(num * 2);
  }

  return doubled;
}

The doubled array grows as nums grows. Extra space is O(n).

// O(n) space — set can store every element
function hasDuplicate(nums) {
  const seen = new Set();

  for (const num of nums) {
    if (seen.has(num)) return true;
    seen.add(num);
  }

  return false;
}

In the worst case, every number is unique, so the set stores all n numbers. Extra space is O(n).

// O(n) space — recursion stack grows n calls deep
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

Even though this function does not create an array, it creates recursive calls. Those calls live on the call stack. At depth n, stack space is O(n).

What counts as extra space?

Count these:

• Arrays you create
• Objects, maps, and sets you create
• Queues, stacks, heaps, and linked lists you create
• Recursive call stack space
• Copies of strings or arrays made by built-in methods

Usually do not count these:

• The original input
• A fixed number of variables
• Loop counters
• Constant-size helper arrays

Example:

function countLetters(str) {
  const frequency = new Array(26).fill(0);

  for (const char of str) {
    const index = char.charCodeAt(0) - 97;
    frequency[index]++;
  }

  return frequency;
}

If the input only contains lowercase English letters, frequency always has length 26. It does not grow with n. Extra space is O(1), not O(n).

Space complexity table

4. Dry Run

Let us analyze a real piece of code step by step.

Problem: Given an array, return a new array containing only the even numbers.

function filterEvens(nums) {
  const evens = [];

  for (const num of nums) {
    if (num % 2 === 0) {
      evens.push(num);
    }
  }

  return evens;
}

Dry run with nums = [1, 2, 4, 7, 8]:

evens = []

num = 1 → odd, do nothing
evens = []

num = 2 → even, push 2
evens = [2]

num = 4 → even, push 4
evens = [2, 4]

num = 7 → odd, do nothing
evens = [2, 4]

num = 8 → even, push 8
evens = [2, 4, 8]

Space complexity analysis:

• evens is an extra array
• In the best case, if no numbers are even, it stays empty
• In the worst case, if all numbers are even, it stores n elements
• Space complexity uses the worst case unless stated otherwise
• Extra space: O(n)

Now compare that with counting evens:

function countEvens(nums) {
  let count = 0;

  for (const num of nums) {
    if (num % 2 === 0) {
      count++;
    }
  }

  return count;
}

Here count is one variable. It does not grow with input size. Extra space is O(1).

The difference is the output requirement. Returning all even values requires memory for those values. Returning only a count does not.

5. Best Practice Example

Problem: Reverse an array in place.

/**
 * Reverse Array In Place
 * Approach: Two pointers
 * Time: O(n) | Space: O(1)
 *
 * We swap elements from both ends until the pointers meet.
 */
function reverseArray(nums) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    [nums[left], nums[right]] = [nums[right], nums[left]];
    left++;
    right--;
  }

  return nums;
}

console.log(reverseArray([1, 2, 3, 4]));    // [4, 3, 2, 1]
console.log(reverseArray([1, 2, 3, 4, 5])); // [5, 4, 3, 2, 1]
console.log(reverseArray([]));              // []

Why this is good:

• It modifies the original array instead of creating a reversed copy
• It uses only two pointer variables
• It handles empty arrays and single-element arrays naturally
• Time is O(n) because each element is visited at most once
• Space is O(1) because no extra structure grows with n

This is the standard shape of an in-place solution: use pointers, swap or overwrite values, and keep memory constant.

6. Bad Practice Example

Problem: Same reverse array problem.

function reverseArray(nums) {
  const reversed = [];

  for (let i = nums.length - 1; i >= 0; i--) {
    reversed.push(nums[i]);
  }

  return reversed;
}

What is wrong:

1. It does not reverse in place: If the requirement says "in place", returning a new array violates the problem.

2. O(n) extra space: The reversed array stores every element from nums.

3. Different behavior: The original input array remains unchanged. That may be incorrect depending on the problem statement.

4. Missed simple pattern: Two pointers solve this with O(1) space.

This is not always a bad algorithm. If the problem asks for a new reversed array, this approach is fine. It becomes bad when the required memory constraint is O(1) or when the interviewer asks for an in-place solution.

7. Time Complexity

Space complexity does not replace time complexity. You analyze both.

Consider two ways to check whether an array contains duplicates.

/**
 * Brute force
 * Time: O(n^2) | Space: O(1)
 */
function hasDuplicateBruteForce(nums) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] === nums[j]) return true;
    }
  }

  return false;
}

This saves memory but spends a lot of time.

/**
 * Hash set
 * Time: O(n) | Space: O(n)
 */
function hasDuplicate(nums) {
  const seen = new Set();

  for (const num of nums) {
    if (seen.has(num)) return true;
    seen.add(num);
  }

  return false;
}

This spends memory to save time.

That tradeoff is common:

Less memory, slower:
  Time: O(n^2) | Space: O(1)

More memory, faster:
  Time: O(n)   | Space: O(n)

In most DSA problems with large input sizes, improving time from O(n^2) to O(n) is worth the O(n) memory cost. But if the problem explicitly asks for O(1) space, you must respect that constraint.

8. Space Complexity

Let us go deeper on the most common sources of memory usage.

Extra data structures

const seen = new Set();       // up to O(n)
const frequency = new Map();  // up to O(n)
const result = [];            // up to O(n)
const matrix = [];            // could be O(n^2)

Ask one question for each structure: how large can this become in the worst case?

If a set can store every input element, it is O(n). If a matrix stores every pair of elements, it is O(n^2).

Recursion stack

/**
 * Time: O(n)
 * Space: O(n)
 */
function sumRecursive(nums, index = 0) {
  if (index === nums.length) return 0;
  return nums[index] + sumRecursive(nums, index + 1);
}

There are n active calls before the recursion starts returning. That is O(n) stack space.

Now compare:

/**
 * Time: O(log n)
 * Space: O(log n)
 */
function binarySearch(nums, target, left = 0, right = nums.length - 1) {
  if (left > right) return -1;

  const mid = Math.floor((left + right) / 2);

  if (nums[mid] === target) return mid;
  if (nums[mid] < target) {
    return binarySearch(nums, target, mid + 1, right);
  }
  return binarySearch(nums, target, left, mid - 1);
}

Each call cuts the search space in half, so the maximum recursion depth is O(log n).

Output space

Sometimes the output itself is large.

function allPairs(nums) {
  const pairs = [];

  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      pairs.push([nums[i], nums[j]]);
    }
  }

  return pairs;
}

The number of pairs is roughly n(n - 1) / 2, so the output array uses O(n^2) space.

In interviews, clarify whether output space should be counted. Many analyses separate auxiliary space from output space:

// Auxiliary space: O(1)
// Output space: O(n^2)

9. Common Mistakes

Mistake 1: Forgetting recursion stack space

function printDown(n) {
  if (n === 0) return;
  printDown(n - 1);
}

This looks like O(1) space because no array is created. But the call stack grows n levels deep. Space is O(n).

How to avoid it: Every time you see recursion, ask: what is the maximum call depth?

Mistake 2: Assuming a fixed-size array is O(n)

const counts = new Array(26).fill(0);

If the size is always 26, it is O(1), not O(n). Big O depends on growth with input size.

How to avoid it: Ask whether the structure grows when n grows. If it stays fixed, it is constant space.

Mistake 3: Ignoring built-in copies

const sorted = [...nums].sort((a, b) => a - b);
const substring = str.slice(left, right);
const reversed = nums.reverse();

Some operations mutate in place. Some create copies. Some are easy to misread. A copied array or string slice can add O(n) or O(k) memory.

How to avoid it: Know whether the method mutates or returns a new structure before using it in a complexity-sensitive solution.

Mistake 4: Calling every variable O(1) without thinking

A few variables are O(1). But a variable can reference a structure that grows:

const result = nums.map(num => num * 2);

result is one variable name, but it points to an array of n elements. Space is O(n).

How to avoid it: Count the memory behind the variable, not the number of variable names.

Mistake 5: Optimizing memory before correctness and time

Beginners sometimes avoid hash maps because they want O(1) space, then accidentally write an O(n^2) solution that times out. Memory matters, but not at the cost of failing the main constraint.

How to avoid it: Read the constraints. If n is large, time complexity usually matters first. Then discuss whether memory can be reduced.

10. Practice Problems

Each of these problems helps you practice memory analysis and time-space tradeoffs.

• Easy: "Reverse String" — solve it in place with two pointers and explain why the extra space is O(1). Pattern: two pointers.

• Easy: "Contains Duplicate" — compare brute force O(1) space with hash set O(n) space. Pattern: hash set.

• Medium: "Product of Array Except Self" — solve without division and understand when the output array is not counted as extra space. Pattern: prefix/suffix products.

• Medium: "Set Matrix Zeroes" — first solve with O(m + n) space, then optimize to O(1) using the first row and first column as markers. Pattern: matrix marking.

• Hard: "Trapping Rain Water" — compare prefix/suffix arrays O(n) space with two pointers O(1) space. Pattern: two pointers / precomputation.

11. Summary

Space complexity measures how extra memory grows with input size. It includes arrays, maps, sets, queues, stacks, recursion depth, and sometimes output storage depending on how the problem asks you to analyze it.

What to remember:

• Space complexity usually means auxiliary space: memory beyond the input
• A fixed number of variables is O(1)
• A structure that can store n elements is O(n)
• Recursion uses stack space
• In-place algorithms often use O(1) extra space
• Faster algorithms often spend more memory, especially when using hash maps or sets
• Always state both time and space complexity

When to use space complexity analysis: after every solution, and especially when the problem says "in place", "constant space", or "without extra memory."

Why it matters: Memory is a real constraint, and space analysis proves you understand the cost of your approach beyond just whether it returns the right answer.

Next Topic ->