Core Concept Mastery • DSA Module
Space Complexity measures how much extra memory (RAM) your algorithm needs to do its job, as a function of the input size. Just like Time Complexity counts steps, Space Complexity counts how much memory you use on top of the input itself.
Imagine sorting a deck of cards on a table. The cards themselves are the Input Space — you cannot change that. The empty spots on the table where you temporarily place cards while sorting? That is Auxiliary Space — the EXTRA memory your algorithm uses. We want to minimize this extra space.
Step 1: Ignore the input itself — focus on what NEW memory your code allocates.
Step 2: Count variables, arrays, objects, and recursive call stack frames.
Step 3: Express the total extra memory as a function of n (the input size).
3 variables → O(1) (constant, doesn't grow with n)
new array of size n → O(n) (grows with input)
2D grid of n×n → O(n²) (grows as square of input)
Extra memory used:
Click "Allocate" to startExtra memory used (result[]):
Click "Allocate" to start1function findSum(arr) {2let total = 0; // 1 variable3for (let i = 0; i < arr.length; i++) {4total += arr[i]; // reusing the same variable5}6return total;7}8// Whether arr has 10 or 10 million items,9// we only created 1 extra variable (total).10// Auxiliary Space = O(1) — Constant!
1function doubleAll(arr) {2let result = []; // brand new array3for (let i = 0; i < arr.length; i++) {4result.push(arr[i] * 2); // result grows with input!5}6return result;7}8// If arr has 1000 items, result also has 1000 items.9// Extra memory grows WITH the input size.10// Auxiliary Space = O(n)
1// SLOW but memory-friendly: O(n²) time, O(1) space2function hasDuplicateSlow(arr) {3for (let i = 0; i < arr.length; i++) {4for (let j = i + 1; j < arr.length; j++) {5if (arr[i] === arr[j]) return true;6}7}8return false;9}1011// FAST but uses more memory: O(n) time, O(n) space12function hasDuplicateFast(arr) {13const seen = new Set(); // extra memory!14for (let item of arr) {15if (seen.has(item)) return true;16seen.add(item);17}18return false;19}20// We traded O(n) space for a massive speed boost.
No Extra Memory
Time: O(n²)
Space: O(1)
Slow but lean
With a HashSet
Time: O(n)
Space: O(n)
Fast but uses more memory
In most real-world apps, speed wins. Use extra memory when you can afford it.
Let's make this super simple.
What counts as "space"?
Every variable, every array, every object your code creates takes up memory. Space complexity asks: "How much EXTRA stuff did you create while solving the problem?"
Two types of space:
1. Input Space: The data you were given. You cannot control this. If someone gives you a list of 1 million names, that is 1 million slots of memory no matter what.
2. Auxiliary Space: The EXTRA memory YOUR code uses while processing. This is what we optimize!
Total Space = Input Space + Auxiliary Space
When people say "space complexity," they usually mean Auxiliary Space.
The Backpack Analogy
Think of it like packing for a trip:
Why O(1) space is the goal:
If your code only creates a few variables (like a counter or a sum), no matter how big the input is, that is O(1) space — constant. You used the same tiny amount of scratch paper whether the input was 10 items or 10 million.
When O(n) space is unavoidable:
Sometimes you need to create a new array or a hash map to solve the problem efficiently. This costs O(n) space, but it might save you from O(n²) time. This is the famous Space-Time Tradeoff — use more memory to go faster.
Memory is not infinite. Your phone has 4-8 GB of RAM. If your app creates a huge copy of every dataset it touches, it will crash. In server environments, excessive memory means higher cloud bills. Knowing space complexity helps you write lean, efficient code.
"You create a new array of size n inside your function. What is the auxiliary space?"
O(n) — because the extra array grows proportionally to the input size.