Time vs Space Complexity

Almost every optimisation in this tutorial is the same move: use more memory so you do less work. Knowing what you are spending is how you tell a good trade from a bad one.

Two different costs

Time complexity counts operations as the input grows. Space complexity counts extra memory, not counting the input itself.

The input does not count because you were given it. What counts is what you allocate on top.

// O(1) space — one accumulator, however big the input.
function sum(items) {
  let total = 0
  for (const n of items) total += n
  return total
}

// O(n) space — a new array as large as the input.
function doubled(items) {
  return items.map((n) => n * 2)
}

// O(n) space, and the reason we accept it.
function firstDuplicate(items) {
  const seen = new Set()
  for (const n of items) {
    if (seen.has(n)) return n
    seen.add(n)
  }
  return null
}

console.log(sum([1, 2, 3]))              // 6
console.log(doubled([1, 2, 3]))          // [2, 4, 6]
console.log(firstDuplicate([1, 2, 1]))   // 1

firstDuplicate could be written with no extra memory using nested loops - but that is O(n²) time. The Set costs O(n) memory and buys O(n) time. On any real input that is a good trade.

When it is not a good trade

Memory is not free, and it is not always available:

• The input is enormous - building a Set of a billion items will not fit.
• You are in a constrained environment - a worker, a device, a tight container limit.
• The problem explicitly asks for constant space, which interviews often do.

When space is capped, the two-pointer and sliding-window techniques later in this tutorial are how you get speed without allocating.

Saying it precisely

"This runs in O(n) time and O(n) space" is a complete answer. "This is fast" is not, and in an interview it is the point where you get asked to be specific.

The trade is usually one way

Almost every speed-up you will make in an interview buys time with memory. A hash map that turns an O(n²) scan into an O(n) pass costs O(n) space. Memoising a recursion costs one entry per distinct call. That direction is normal and expected.

Going the other way - spending time to save memory - is rarer, and you should say out loud when you are doing it. Reversing an array in place instead of building a copy, or recomputing a value rather than caching it, is worth it only when memory is the actual constraint.

What counts as space

Space complexity means extra space, not the input. An algorithm that sorts a 10,000-element array in place is O(1) space even though the array is large - you did not allocate anything that grows with n.

Recursion is the exception people miss: each pending call keeps a stack frame, so a recursion n levels deep is O(n) space even with no arrays involved. That is why a recursive traversal of a degenerate tree can overflow the stack where a loop would not.

• Ask time and space separately - an interviewer who asks for one often wants both.
• Ignore the input itself; count only what you allocate.
• Count recursion depth as space.
• State the trade you chose and why, rather than hoping it goes unnoticed.