💾

Space Complexity

Understand memory usage and how to trade space for time (and vice versa).

0 Problems45 min

Overview

Space complexity measures how much extra memory an algorithm uses as input grows. We distinguish between input space (the original data) and auxiliary space (extra memory your algorithm allocates). In interviews, optimizing space often means choosing between an O(n) hash map (fast) or an O(1) two-pointer approach (memory efficient).

Complexity Summary

Time Complexity

N/A

Space Complexity

This topic teaches how to measure space complexity

Key Patterns & Techniques

Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.

1

O(1) space

Concept

fixed variables only.

Pattern Example
Problem

let left=0, right=n-1; (two pointer)

Practice questions for this pattern
2

O(n) space

Concept

storing n items.

Pattern Example
Problem

const map = new Map(); // up to n entries

Practice questions for this pattern
3

O(log n) stack

Concept

recursive binary search call depth.

Pattern Example
Problem

binarySearch(arr, lo, hi)

Practice questions for this pattern
4

O(n) stack

Concept

recursive DFS on skewed tree.

Pattern Example
Problem

treeHeight(root.left)

Practice questions for this pattern
5

Trade-off

Concept

memoization uses O(n) space to reduce O(2ⁿ) time to O(n)

Practice questions for this pattern
6

In-place

Concept

modify input array to avoid extra space.

Pattern Example
Problem

reverse array with two pointers

Practice questions for this pattern
7

Auxiliary space

Concept

space beyond the input itself; what interviewers usually mean by "space complexity"

Practice questions for this pattern
DSA Practice Online - 150+ Coding Interview Questions | LeetCode Alternative | InstaMock - AI Mock Interview