EasyHigh Frequency15 min
Space Complexity
Analyze memory usage and learn the space-time trade-off in algorithm design.
Space complexity is the extra memory your algorithm uses beyond the input — O(1) means in-place, O(n) means you store n extra values.
Space Complexity
Space Usage by Algorithm
Operation
Time
Note
Two pointers (iterative)
O(1)
Only pointer variables
Binary search (iterative)
O(1)
Just lo/hi/mid variables
Binary search (recursive)
O(log n)
Call stack depth = log n
DFS on balanced tree
O(log n)
Stack = height of tree
DFS on skewed tree
O(n)
Stack = n for degenerate tree
Memoization (top-down DP)
O(n)
Cache stores n subproblems
2D DP table
O(m×n)
Can often optimize to O(n)
HashMap / HashSet
O(n)
Stores n key-value pairs