DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Space Complexity

What Is Space Complexity?

When you evaluate an algorithm, runtime is not the only thing that matters. Memory matters too.

Imagine you are building a feature for a mobile app. Your algorithm solves the problem correctly and runs quickly. But it creates a copy of every array it touches, and users with low-end phones run out of memory and crash. The algorithm was fast — but it was unusable.

Space complexity measures how much memory an algorithm uses as its input size grows. Just like time complexity, it is expressed in Big-O notation and focuses on growth rate, not exact byte counts.

Understanding space complexity lets you make informed decisions about memory usage and recognize when an algorithm is too expensive to run in constrained environments — embedded systems, mobile devices, or systems handling millions of concurrent requests.

Two Types of Space

When analyzing space complexity, there are two components to consider:

Input Space — the memory used to store the input itself. An array of n integers takes O(n) space just to exist. This is usually not counted toward the algorithm's space complexity because it is required regardless of the approach.

Auxiliary Space — the extra memory the algorithm uses beyond the input. Temporary variables, new arrays, hash maps, recursion call stacks — anything the algorithm creates or allocates while running.

Most interviews and textbooks refer to auxiliary space when they say "space complexity." The question being asked is: how much additional memory does this algorithm need?

Why Space Complexity Matters

Consider two algorithms that both compute the same result:

›Algorithm A uses O(n) extra space — it creates a new array to store results
›Algorithm B uses O(1) extra space — it modifies the input in place

For 10 elements, the difference is negligible. For 100 million elements, Algorithm A allocates hundreds of megabytes of additional memory. In a system serving thousands of users simultaneously, that memory pressure becomes a real engineering problem.

Space complexity also affects cache performance. Algorithms that use less memory access data that fits in CPU cache more often, which dramatically improves real-world speed — even when both algorithms have the same time complexity.

The Common Space Complexities

Complexity	Name	Example
O(1)	Constant	In-place reversal, two-pointer technique
O(log n)	Logarithmic	Recursive binary search call stack
O(n)	Linear	Storing a copy, prefix sum array, hash map
O(n²)	Quadratic	2D matrix, adjacency matrix for a graph

O(1) — Constant Space

An algorithm uses O(1) auxiliary space when it uses the same amount of extra memory regardless of input size. A few variables, a temporary swap — nothing that grows with n.

The classic example: reversing an array in place using two pointers. No extra array is created. Only two integer pointer variables are used regardless of how large the array is.

Java

Try it out

public class ConstantSpace {

    // Reverse array in-place — only uses two pointer variables
    // Extra space: O(1) — two integers (left, right) regardless of array size
    public static void reverseInPlace(int[] arr) {
        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            // Swap elements at left and right
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;

            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};

        System.out.print("Before: ");
        for (int num : numbers) System.out.print(num + " ");
        System.out.println();

        reverseInPlace(numbers);

        System.out.print("After:  ");
        for (int num : numbers) System.out.print(num + " ");
        System.out.println();
    }
}

Output:
Before: 1 2 3 4 5
After:  5 4 3 2 1

Dry Run: In-Place Reversal of [1, 2, 3, 4, 5]

Initial: [1, 2, 3, 4, 5]   left=0, right=4
Extra memory used: temp (1 variable) — always O(1)

Step 1: left=0, right=4
  swap arr[0]=1 and arr[4]=5
  → [5, 2, 3, 4, 1]   left=1, right=3

Step 2: left=1, right=3
  swap arr[1]=2 and arr[3]=4
  → [5, 4, 3, 2, 1]   left=2, right=2

Step 3: left=2, right=2
  left >= right → stop

Result: [5, 4, 3, 2, 1]
Memory used beyond input: 3 variables (left, right, temp) — constant regardless of n

Even if the array had one million elements, this algorithm would still use only 3 extra variables. That is O(1) space.

O(n) — Linear Space

An algorithm uses O(n) auxiliary space when the extra memory it allocates grows proportionally with the input size. Creating a new array of size n, building a hash map of n entries, or storing n results — all of these are O(n).

The example below computes a prefix sum array. For each index i, it stores the sum of all elements from index 0 to i. This requires creating a new array of the same size as the input.

Java

Try it out

public class LinearSpace {

    // Build a prefix sum array — creates a new array of size n
    // Extra space: O(n) — the prefix array grows with input size
    public static int[] buildPrefixSum(int[] arr) {
        int n = arr.length;
        int[] prefix = new int[n]; // Extra array of size n

        prefix[0] = arr[0];

        for (int i = 1; i < n; i++) {
            // Each prefix[i] = sum of all elements from index 0 to i
            prefix[i] = prefix[i - 1] + arr[i];
        }

        return prefix;
    }

    public static void main(String[] args) {
        int[] numbers = {3, 1, 4, 1, 5, 9, 2};

        int[] prefix = buildPrefixSum(numbers);

        System.out.print("Input:  ");
        for (int num : numbers) System.out.print(num + " ");
        System.out.println();

        System.out.print("Prefix: ");
        for (int num : prefix) System.out.print(num + " ");
        System.out.println();

        // Now any range sum query is O(1)
        // Sum from index 2 to 5 = prefix[5] - prefix[1]
        System.out.println("Sum from index 2 to 5: " + (prefix[5] - prefix[1]));
    }
}

Output:
Input:  3 1 4 1 5 9 2
Prefix: 3 4 8 9 14 23 25
Sum from index 2 to 5: 19

Dry Run: Building Prefix Sum for [3, 1, 4, 1, 5, 9, 2]

Input:  [3,  1,  4,  1,  5,  9,  2]
Index:   0   1   2   3   4   5   6

prefix[0] = arr[0]          = 3
prefix[1] = prefix[0] + 1  = 3  + 1  = 4
prefix[2] = prefix[1] + 4  = 4  + 4  = 8
prefix[3] = prefix[2] + 1  = 8  + 1  = 9
prefix[4] = prefix[3] + 5  = 9  + 5  = 14
prefix[5] = prefix[4] + 9  = 14 + 9  = 23
prefix[6] = prefix[5] + 2  = 23 + 2  = 25

Prefix: [3, 4, 8, 9, 14, 23, 25]

Range sum query (index 2 to 5):
  prefix[5] - prefix[1] = 23 - 4 = 19
  Verify: arr[2]+arr[3]+arr[4]+arr[5] = 4+1+5+9 = 19 ✓

Extra memory used: prefix array of size n → O(n) space

This is the classic time-space tradeoff. By spending O(n) extra space to build the prefix array once, every future range sum query runs in O(1) instead of O(n).

O(log n) — Logarithmic Space from Recursion

Recursive algorithms consume stack space. Every time a function calls itself, a new stack frame is added to the call stack — storing local variables, parameters, and the return address. When the recursion ends, frames are removed.

The depth of recursion determines the space used. Recursive binary search halves the search space at each call, so it recurses at most log₂(n) levels deep — using O(log n) stack space.

Java

Try it out

public class LogarithmicSpace {

    // Recursive binary search — call stack depth is O(log n)
    // Extra space: O(log n) — one stack frame per recursive call
    public static int binarySearch(int[] arr, int left, int right, int target) {
        // Base case — search space exhausted
        if (left > right) {
            return -1;
        }

        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            // Recurse on right half — one more stack frame added
            return binarySearch(arr, mid + 1, right, target);
        } else {
            // Recurse on left half — one more stack frame added
            return binarySearch(arr, left, mid - 1, target);
        }
    }

    public static void main(String[] args) {
        int[] sorted = {5, 12, 18, 25, 34, 47, 56, 68, 79, 91};
        int target = 47;

        int result = binarySearch(sorted, 0, sorted.length - 1, target);

        if (result != -1) {
            System.out.println(target + " found at index: " + result);
        } else {
            System.out.println(target + " not found");
        }
    }
}

Output:
47 found at index: 5

Dry Run: Recursive Call Stack for Binary Search

Array: [5, 12, 18, 25, 34, 47, 56, 68, 79, 91]
Target: 47

Call 1: binarySearch(arr, 0, 9, 47)   ← Stack depth 1
  mid=4, arr[4]=34, 34 < 47 → recurse right

  Call 2: binarySearch(arr, 5, 9, 47) ← Stack depth 2
    mid=7, arr[7]=68, 68 > 47 → recurse left

    Call 3: binarySearch(arr, 5, 6, 47) ← Stack depth 3
      mid=5, arr[5]=47, found! → return 5

    Call 3 returns 5
  Call 2 returns 5
Call 1 returns 5

Maximum stack depth: 3 frames = log₂(10) ≈ 3.3
For n=1,000,000: maximum stack depth = log₂(1,000,000) ≈ 20 frames

Space used: O(log n) — each frame stores (arr, left, right, target, mid)

This is an important distinction from iterative binary search, which uses O(1) space. Recursion always carries a hidden space cost through the call stack.

O(n²) — Quadratic Space

An algorithm uses O(n²) auxiliary space when it allocates a two-dimensional structure whose dimensions both scale with input size. The most common examples are 2D matrices and adjacency matrices for graphs.

Java

Try it out

public class QuadraticSpace {

    // Build a multiplication table — 2D matrix of size n×n
    // Extra space: O(n²) — one cell for every pair (i, j)
    public static int[][] buildMultiplicationTable(int n) {
        int[][] table = new int[n][n]; // n×n matrix

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                table[i][j] = (i + 1) * (j + 1);
            }
        }

        return table;
    }

    public static void main(String[] args) {
        int n = 4;
        int[][] table = buildMultiplicationTable(n);

        System.out.println("Multiplication table (" + n + "x" + n + "):");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.printf("%4d", table[i][j]);
            }
            System.out.println();
        }
    }
}

Output:
Multiplication table (4x4):
   1   2   3   4
   2   4   6   8
   3   6   9  12
   4   8  12  16

For n=4, the matrix holds 16 values. For n=1000, it holds one million values. Space grows as n² — that is O(n²).

Understanding Recursion and Stack Space

Recursion is one of the most common sources of hidden space complexity. Every recursive call adds a frame to the call stack, and that frame stays in memory until the call returns.

The space consumed depends entirely on the maximum recursion depth — how deep the call stack gets before any frame starts unwinding.

Recursive Algorithm         Max Stack Depth    Space Complexity
Binary Search (recursive)   log₂(n) levels     O(log n)
Linear scan (recursive)     n levels           O(n)
Merge Sort                  log₂(n) levels     O(log n) stack + O(n) merge arrays = O(n)
Fibonacci (naive recursive) n levels           O(n)

This is why converting recursion to iteration often reduces space complexity. Iterative binary search uses O(1) space. Recursive binary search uses O(log n). Both have the same time complexity.

Python has a default recursion depth limit of 1000 calls. For deep recursion on large inputs, this limit can cause a RecursionError. Java and C++ have stack size limits that cause StackOverflowError or undefined behavior when exceeded.

Time-Space Tradeoff

One of the most fundamental concepts in algorithm design: you can often trade memory for speed.

Spending extra space to store precomputed results, indexes, or auxiliary data structures can dramatically reduce time complexity. The question is always whether the memory cost is acceptable.

Approach	Time	Space	When to use
Recompute every time	Fast per element	O(1) extra	Memory is very tight
Precompute and cache	O(1) per query	O(n) extra	Many repeated queries
Hash map lookup	O(1) average	O(n) extra	Need fast key-based access
In-place algorithm	O(n) or O(n log n)	O(1) extra	Memory is constrained
Auxiliary array	O(n)	O(n) extra	Simplicity matters more

The prefix sum array from the O(n) section is the clearest example. Without it, every range sum query costs O(n). With it, every query costs O(1) — but you pay O(n) space upfront.

Caching, memoization, hash maps, lookup tables — all of these are time-space tradeoffs. Dynamic Programming, which you will study later, is essentially the discipline of systematically applying this tradeoff to recursive problems.

How to Calculate Space Complexity

When analyzing an algorithm's space usage, follow these steps:

Step 1 — Identify all variables and data structures created.

Count integers, booleans, arrays, hash maps, trees, and recursive stack frames. Ignore the input itself unless you are counting total space.

Step 2 — Determine how each scales with n.

A single integer is O(1). An array of size n is O(n). A 2D array of size n×n is O(n²). A recursive call stack of depth log n is O(log n).

Step 3 — Take the dominant term.

Just like time complexity, drop constants and lower-order terms. If you allocate an array of size n and use 5 integer variables, the space complexity is O(n) + O(1) = O(n).

Practical Examples

int x = 5;                         → O(1)   one variable

int[] arr = new int[n];            → O(n)   array grows with n

int[][] matrix = new int[n][n];    → O(n²)  2D array

HashMap<Integer, Integer> map      → O(n)   up to n entries
  with n entries

recursive(n) calls recursive(n-1)  → O(n)   n frames on call stack
  n levels deep

recursive(n) calls recursive(n/2)  → O(log n)  log n frames on call stack
  log n levels deep

Comparing Space Complexities at Scale

n (input size)	O(1)	O(log n)	O(n)	O(n²)
10	1 unit	3 units	10 units	100 units
1,000	1 unit	10 units	1,000 units	1,000,000 units
100,000	1 unit	17 units	100,000 units	10,000,000,000 units
1,000,000	1 unit	20 units	1,000,000 units	10^12 units

O(n²) space for large inputs is often completely impractical. A graph with one million nodes represented as an adjacency matrix would require one trillion entries — far beyond available memory on any real machine. This is why adjacency lists (O(n + edges)) are preferred over adjacency matrices (O(n²)) for sparse graphs.

Common Mistakes Beginners Make

Forgetting recursion uses stack space. Recursive functions look simple and clean, but each call consumes stack memory. A recursive solution that appears to use O(1) variables may actually use O(n) or O(log n) space through its call stack.

Counting input space as auxiliary space. If a function receives an array of size n, that array was already allocated by the caller. The function's auxiliary space is only what it creates additionally. Read carefully — some problems ask for total space, others for auxiliary space only.

Assuming in-place means zero extra space. In-place means the input is modified rather than copied. But even in-place algorithms can use auxiliary space for temporary variables or recursion. "In-place" describes memory strategy, not always O(1) space.

Not accounting for the output array. If a function returns a new array of size n, that array is O(n) space. If the interviewer asks for the space complexity including output, it changes the answer.

Ignoring space in Dynamic Programming. DP solutions often use O(n) or O(n²) space for memoization tables. Space-optimized DP (rolling arrays) can reduce this significantly, but the optimization requires understanding which previous states are actually needed.

Interview Questions

Q: What is the difference between time complexity and space complexity?

Time complexity measures how the number of operations grows with input size. Space complexity measures how the memory usage grows. Both are expressed in Big-O notation. A good algorithm balances both — but in practice, the acceptable tradeoff depends on the system's constraints.

Q: What is auxiliary space, and why is it measured separately from input space?

Auxiliary space is the extra memory an algorithm uses beyond storing its input. It is measured separately because the input must exist regardless of the algorithm chosen — what distinguishes algorithms is how much additional memory they require. Interviewers almost always mean auxiliary space when asking about space complexity.

Q: Why does recursion use O(n) or O(log n) space even when no data structures are created?

Every recursive call adds a stack frame to the call stack. This frame stores the function's local variables, parameters, and return address. Frames accumulate until the base case is reached, consuming memory proportional to the maximum recursion depth. Linear recursion (depth n) uses O(n) stack space. Halving recursion (depth log n) uses O(log n).

Q: A function creates one integer variable and makes n recursive calls. What is its space complexity?

O(n). The single integer variable is O(1), but the n recursive calls each add a stack frame. The maximum stack depth is n, so the call stack consumes O(n) space. The dominant term is O(n).

Q: How would you reduce space complexity from O(n) to O(1) in a simple algorithm?

By processing the input directly instead of creating auxiliary data structures. For example, instead of building a frequency array to count occurrences, you can use two nested loops (increasing time complexity but reducing space). The key is identifying which stored data is actually necessary versus which can be recomputed.

FAQs

Does lower space complexity always mean better code?

Not always. Lower space complexity sometimes means higher time complexity (or more complex code). The right balance depends on your constraints. A system with abundant RAM and tight latency requirements should favor time. An embedded system with 64KB of memory has no choice but to prioritize space.

Does creating a variable inside a loop increase space complexity?

No — if the variable is reused each iteration. Creating int temp inside a loop that runs n times still uses O(1) space, because only one instance of temp exists at any moment. Space complexity measures memory used simultaneously, not total memory ever allocated.

What is the space complexity of sorting algorithms?

It varies by algorithm. Bubble Sort, Selection Sort, and Insertion Sort use O(1) auxiliary space — they sort in place. Merge Sort uses O(n) auxiliary space for the merge step. Quick Sort uses O(log n) average auxiliary space for the recursion stack. This is one reason Quick Sort is preferred despite having the same O(n log n) average time as Merge Sort.

How does garbage collection affect space complexity analysis?

In Big-O analysis, we typically assume memory is freed as soon as it is no longer needed. Garbage-collected languages (Java, Python, JavaScript) may hold memory longer in practice, but for complexity analysis purposes, we count the maximum memory in use at any single point during execution.

Quick Quiz

Question 1: An algorithm creates one temporary variable and reverses an array in place. What is its auxiliary space complexity?

›A) O(n)
›B) O(n²)
›C) O(log n)
›D) O(1)

Answer: D) O(1). Only a constant number of extra variables are used regardless of how large the array is. Modifying the input in place does not count as auxiliary space.

Question 2: A recursive function calls itself n times before hitting the base case. What is the space complexity from the call stack alone?

›A) O(1)
›B) O(log n)
›C) O(n)
›D) O(n²)

Answer: C) O(n). Each recursive call adds one stack frame. If the function recurses n levels deep, the call stack holds n frames simultaneously at maximum depth — consuming O(n) space.

Question 3: Which of the following uses O(n²) auxiliary space?

›A) Reversing an array in place
›B) Building a prefix sum array of size n
›C) Building an n×n adjacency matrix
›D) Recursive binary search

Answer: C) Building an n×n adjacency matrix. An n×n matrix holds n² values — space that grows quadratically with n. The others use O(1), O(n), and O(log n) respectively.

Question 4: You use O(n) extra space to speed up an algorithm from O(n²) to O(n). This is an example of:

›A) Space complexity reduction
›B) Time-space tradeoff
›C) Auxiliary space elimination
›D) In-place optimization

Answer: B) Time-space tradeoff. Spending memory to gain speed (or vice versa) is the classic time-space tradeoff. Prefix sums, memoization, hash maps, and caching are all real-world examples of this pattern.

Summary

Space complexity measures how much auxiliary memory an algorithm uses as input size grows. Like time complexity, it is expressed in Big-O notation and focuses on growth rate, not exact byte counts.

The key ideas to carry forward:

›Auxiliary space is what the algorithm creates — input space does not count
›O(1) space means a fixed number of variables regardless of input size
›O(n) space means memory grows proportionally with input — arrays, hash maps, results
›O(log n) space is common from recursive algorithms that halve their input each call
›O(n²) space comes from 2D structures whose dimensions both scale with n
›Recursion always carries hidden stack space proportional to its maximum depth
›Time-space tradeoff is a deliberate engineering decision — more memory can mean less time

In the next topic, you will explore Asymptotic Notation — learning how Big-O, Big-Omega, and Big-Theta each describe a different aspect of algorithmic behavior.

←

PreviousTime Complexity (Big-O)

NextAsymptotic Notation

→