TypeScript Space Complexity

Big O for Memory

Big O can describe memory the same way it describes time: how much extra space does the algorithm need as the input grows?

We count only the extra space — the variables and arrays the algorithm creates — not the input itself. This extra space is called auxiliary space.

O(1) space: a fixed number of variables, no matter the input. O(n) space: something new is stored per input element, like a copy or a Map of seen values.

O(1) Space

An algorithm that keeps only a few plain variables uses constant space. The array can hold ten elements or ten million — the algorithm itself still owns just its counters.

Summing, finding the maximum, and linear search are all O(n) time but O(1) space: they read a lot and remember almost nothing.

Sum with one variable

The whole algorithm remembers exactly one number, sum. Its memory use does not grow with the array: O(1) space.

Write a TypeScript program that sums the number array 3, 1, 4, 1, 5, 9, 2, 6 using a single extra variable and prints the sum, to show an O(n) time but O(1) space algorithm.

> Output: TypeScript file and captured output

Prompt

Write a TypeScript program that sums the number array 3, 1, 4, 1, 5, 9, 2, 6 using a single extra variable and prints the sum, to show an O(n) time but O(1) space algorithm.

Output: TypeScript file and captured output

const nums = [3, 1, 4, 1, 5, 9, 2, 6]

// One extra variable, no matter how long the array is.
let sum = 0
for (const n of nums) {
  sum += n
}

console.log("sum:", sum)

O(n) Space

As soon as the algorithm builds something with one entry per input element — a new array, a Map — its space is O(n): double the input, double the memory.

That is not bad by itself. It is simply a cost you should notice, because it can be traded.

Build a new array

The output array gets one element for every input element. 5 in, 5 out — memory grows in step with the input: O(n) space.

Write a TypeScript program that builds a new array with every element of the array 1, 2, 3, 4, 5 doubled, pushing into an empty array, then prints the input array and the output array.

> Output: TypeScript file and captured output

Prompt

Write a TypeScript program that builds a new array with every element of the array 1, 2, 3, 4, 5 doubled, pushing into an empty array, then prints the input array and the output array.

Output: TypeScript file and captured output

const nums = [1, 2, 3, 4, 5]

// A new array with one element per input element.
const doubled: number[] = []
for (const n of nums) {
  doubled.push(n * 2)
}

console.log("input: ", nums)
console.log("output:", doubled)

Trading Space for Time

Often you can spend memory to save time. The classic example is Two Sum: find two numbers in an array that add up to a target.

The direct way checks every pair — O(n²) time, O(1) space. The fast way walks the array once and remembers every number it has seen in a Map. For each number it asks: "have I already seen target - n?" — O(n) time, O(n) space.

This trade is usually worth it: memory can be added to a machine, time cannot.

Two Sum with two loops

Every pair is checked until a match appears — up to 15 checks for 6 elements, and the count grows with the square of the input. No extra memory is used.

Write a TypeScript program that finds two numbers adding up to 9 in the array 2, 11, 15, 1, 8, 7 by checking every pair with two nested loops, counting the checks. Print every match with the number of checks so far, and at the end print the total number of checks.

> Output: TypeScript file and captured output

Prompt

Write a TypeScript program that finds two numbers adding up to 9 in the array 2, 11, 15, 1, 8, 7 by checking every pair with two nested loops, counting the checks. Print every match with the number of checks so far, and at the end print the total number of checks.

Output: TypeScript file and captured output

const nums = [2, 11, 15, 1, 8, 7]
const target = 9
let checks = 0

for (let i = 0; i < nums.length; i++) {
  for (let j = i + 1; j < nums.length; j++) {
    checks++
    if (nums[i] + nums[j] === target) {
      console.log("found:", nums[i], "+", nums[j], "after", checks, "checks")
    }
  }
}

console.log("total checks:", checks)

Two Sum with a Map

One pass, 6 checks. Each number is looked up with seen.has() and stored with seen.set() — constant-time work per element. The Map is the O(n) memory that buys the O(n) time.

Write a TypeScript program that finds two numbers adding up to 9 in the array 2, 11, 15, 1, 8, 7 in one pass: keep a Map of seen numbers, and for each number check whether target minus the number was already seen. Print every match, and at the end print that each element was checked once.

> Output: TypeScript file and captured output

Prompt

Write a TypeScript program that finds two numbers adding up to 9 in the array 2, 11, 15, 1, 8, 7 in one pass: keep a Map of seen numbers, and for each number check whether target minus the number was already seen. Print every match, and at the end print that each element was checked once.

Output: TypeScript file and captured output

const nums = [2, 11, 15, 1, 8, 7]
const target = 9

// One entry per element seen so far: the O(n) memory.
const seen = new Map<number, boolean>()

for (const n of nums) {
  if (seen.has(target - n)) {
    console.log("found:", target - n, "+", n)
  }
  seen.set(n, true)
}

console.log("checked", nums.length, "elements once")