Space Complexity and a Complexity Cheat Sheet

Space complexity is the extra memory an algorithm uses as the input grows. By convention:

The input itself doesn't count.
The output doesn't count unless the question asks about it.
Everything else counts: new collections, copies, and the recursion stack.

Counting extra space

OptionalInt is a container that holds either one int or nothing, so a method can report "no answer" without returning null.

Java

import java.util.Arrays;
import java.util.HashSet;
import java.util.OptionalInt;
import java.util.Set;

public class Main {
    // O(1) extra space: a few variables, whatever the input length
    static OptionalInt maxValue(int[] nums) {
        if (nums.length == 0) return OptionalInt.empty();
        int best = nums[0];
        for (int x : nums) best = Math.max(best, x);
        return OptionalInt.of(best);
    }

    // O(n) extra space: the new array grows with the input
    static int[] doubled(int[] nums) {
        int[] out = new int[nums.length];
        for (int i = 0; i < nums.length; i++) out[i] = nums[i] * 2;
        return out;
    }

    // O(n) extra space for the set, even though the output is a single boolean
    static boolean hasDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) {
            if (!seen.add(x)) return true; // add returns false when x is already present
        }
        return false;
    }

    // O(1) extra space of our own: sorts the caller's array in place
    static boolean hasDuplicateSorted(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i + 1 < nums.length; i++) {
            if (nums[i] == nums[i + 1]) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(maxValue(new int[]{3, 9, 4}) + " " + Arrays.toString(doubled(new int[]{3, 9, 4})));
        System.out.println(hasDuplicate(new int[]{1, 2, 1}) + " " + hasDuplicateSorted(new int[]{1, 2, 1}));
    }
}

Output

OptionalInt[9] [6, 18, 8]
true true

The two duplicate checks show the usual trade-off: the HashSet version is O(n) time and O(n) space, and the sorting version is O(n log n) time and O(1) space.

In Java, the method signature is a good hint:

Signature	Usually means
`void f(int[] v)` that changes `v`	works in place, `O(1)` extra
`int[] f(int[] v)` or `List<Integer> f(int[] v)` that returns a new collection	builds a new collection, `O(n)`
a local `HashMap`, `HashSet`, or `ArrayList` sized by the input	`O(n)`
`v.clone()` or `Arrays.copyOf(v, n)`	`O(n)` for the copy

Library sorts have working memory of their own. Arrays.sort(int[]) rearranges the array in place, but its implementation may use a temporary buffer, and the Javadoc does not promise O(1) extra space. List.sort and Arrays.sort(T[]) use a merge-based stable sort that may allocate a temporary array proportional to n. The programs here count only the memory the code itself allocates.

The recursion stack

Every recursive call keeps a stack frame alive until it returns. A recursion that goes d levels deep uses O(d) space, even if it allocates nothing on the heap.

Java

import java.util.stream.LongStream;

public class Main {
    static long depthSum(int n) {
        return n == 0 ? 0 : n + depthSum(n - 1); // n frames deep: O(n) space
    }

    static long loopSum(int n) {
        return LongStream.rangeClosed(1, n).sum(); // O(1) space
    }

    public static void main(String[] args) {
        System.out.println(depthSum(1000) + " " + loopSum(1000));
    }
}

Output

500500 500500

Recursion over	Depth	Stack space
a list of length `n`	`n`	`O(n)`
a balanced binary tree with `n` nodes	`log n`	`O(log n)`
a skewed tree (every node has only one child)	`n`	`O(n)`
binary search	`log n`	`O(log n)`

Each Java thread has a fixed stack size, set by the JVM (commonly 1 MB, adjustable with the -Xss option). A recursion that goes too deep throws StackOverflowError. The depth that fits depends on the frame size, so a few thousand levels is safe and a few hundred thousand is not. When the depth can reach n for large inputs, rewrite the recursion as a loop with an explicit ArrayDeque stack.

Cheat sheet: code shapes and their complexity

Each example below is a common code shape, with its time and space complexity.

O(1): a fixed amount of work

Java

import java.util.OptionalInt;

public class Main {
    static OptionalInt middle(int[] nums) {
        if (nums.length == 0) return OptionalInt.empty();
        return OptionalInt.of(nums[nums.length / 2]); // one index, whatever the length
    }

    public static void main(String[] args) {
        System.out.println(middle(new int[]{4, 8, 15, 16, 23}));
    }
}

Output

OptionalInt[15]

Time O(1), space O(1).

O(log n): halve the problem each step

Java

public class Main {
    static int countDigits(long n) {
        int digits = 1;
        while (n >= 10) {
            n /= 10; // divides by 10 each step: log₁₀ n steps
            digits++;
        }
        return digits;
    }

    public static void main(String[] args) {
        System.out.println(countDigits(7) + " " + countDigits(1_000_000));
    }
}

Output

1 7

Time O(log n), space O(1). Any loop that multiplies or divides its variable by a constant is logarithmic.

O(n): one pass, maybe with a set

Java

import java.util.HashSet;
import java.util.OptionalInt;
import java.util.Set;

public class Main {
    static OptionalInt firstRepeat(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) {
            if (!seen.add(x)) return OptionalInt.of(x);
        }
        return OptionalInt.empty();
    }

    public static void main(String[] args) {
        System.out.println(firstRepeat(new int[]{3, 1, 4, 1, 5}));
    }
}

Output

OptionalInt[1]

Time O(n), space O(n) for the set.

O(n log n): sort, then scan

Java

import java.util.Arrays;
import java.util.OptionalInt;

public class Main {
    static OptionalInt minGap(int[] nums) {
        if (nums.length < 2) return OptionalInt.empty();
        int[] sorted = nums.clone();
        Arrays.sort(sorted);                       // O(n log n)
        int best = Integer.MAX_VALUE;
        for (int i = 1; i < sorted.length; i++) {  // O(n)
            best = Math.min(best, sorted[i] - sorted[i - 1]);
        }
        return OptionalInt.of(best);
    }

    public static void main(String[] args) {
        System.out.println(minGap(new int[]{10, 3, 7, 1, 8}));
    }
}

Output

OptionalInt[1]

Time O(n log n), space O(n) for the sorted copy.

O(n log k): a heap of size k

Java

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    static List<Integer> topK(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap: the smallest of the kept values is on top
        for (int x : nums) {
            heap.offer(x);          // O(log k)
            if (heap.size() > k) {
                heap.poll();        // O(log k)
            }
        }
        List<Integer> out = new ArrayList<>(heap); // heap order is not sorted order
        out.sort((a, b) -> Integer.compare(b, a));
        return out;
    }

    public static void main(String[] args) {
        System.out.println(topK(new int[]{5, 1, 9, 3, 7}, 2));
    }
}

Output

[9, 7]

Time O(n log k), space O(k).

O(n²): every pair

Java

public class Main {
    static int countInversions(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] > nums[j]) count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(countInversions(new int[]{3, 1, 2}));
    }
}

Output

Time O(n²), space O(1).

O(n·m): two different inputs

Java

import java.util.List;

public class Main {
    static int common(List<Integer> a, List<Integer> b) {
        int count = 0;
        for (int x : a) {
            if (b.contains(x)) count++; // contains is O(m), run n times
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(common(List.of(1, 2, 3), List.of(2, 3, 4, 5)));
    }
}

Output

Time O(n·m), space O(1). Loading b into a HashSet first makes it O(n + m) time and O(m) space.

O(2ⁿ): every subset

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        List<List<Integer>> out = new ArrayList<>();
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) subset.add(nums[i]);
            }
            out.add(subset);
        }
        return out;
    }

    public static void main(String[] args) {
        System.out.println(subsets(new int[]{1, 2, 3}));
    }
}

Output

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Time O(n · 2ⁿ), since there are 2ⁿ subsets and each takes up to n steps to build. Space O(n · 2ⁿ) for the output.

O(V + E): visit a graph once

Java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

public class Main {
    static int reachable(List<List<Integer>> adj, int start) {
        boolean[] visited = new boolean[adj.size()];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        int count = 0;
        while (!stack.isEmpty()) {
            int v = stack.pop();
            if (!visited[v]) {
                visited[v] = true;
                count++;
                for (int next : adj.get(v)) stack.push(next); // each edge is pushed once
            }
        }
        return count;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = List.of(List.of(1, 2), List.of(2), List.of(0), List.of(0));
        System.out.println(reachable(adj, 0));
    }
}

Output

Time O(V + E), space O(V + E) in the worst case for the stack.

Summary

Code shape	Time	Extra space
index, arithmetic, `HashMap.get`	`O(1)`	`O(1)`
halving or dividing loop, binary search	`O(log n)`	`O(1)`
one pass	`O(n)`	`O(1)`
one pass with a set or map	`O(n)`	`O(n)`
sort, then scan	`O(n log n)`	`O(1)` to `O(n)`
heap of size `k` over `n` items	`O(n log k)`	`O(k)`
two nested loops over the same input	`O(n²)`	`O(1)`
loop over `a` with a `contains` on `b`	`O(n·m)`	`O(1)`
recursion into two branches of size `n - 1`	`O(2ⁿ)`	`O(n)` stack
graph BFS or DFS	`O(V + E)`	`O(V)`
balanced tree search, insert, delete	`O(log n)`	`O(1)` or `O(log n)` stack

Common algorithms

Algorithm	Time	Extra space
linear search	`O(n)`	`O(1)`
binary search	`O(log n)`	`O(1)`
merge-based sort (`List.sort`, `Arrays.sort(T[])`)	`O(n log n)`	`O(n)`
dual-pivot quicksort (`Arrays.sort(int[])`)	`O(n log n)`	`O(log n)` for recursion, plus any temporary buffer the JDK uses
heap sort	`O(n log n)`	`O(1)`
counting sort for values from `0` to `k - 1`	`O(n + k)`	`O(k)`
BFS, DFS	`O(V + E)`	`O(V)`
Dijkstra with a binary heap	`O((V + E) log V)`	`O(V)`
topological sort (Kahn)	`O(V + E)`	`O(V)`
union-find, per operation	about `O(1)` (inverse Ackermann)	`O(V)`
trie insert / search, word of length `L`	`O(L)`	`O(L)` per insert
Kadane's maximum subarray	`O(n)`	`O(1)`
prefix sums: build / query	`O(n)` / `O(1)`	`O(n)`

Java collection costs

Operation	Type	Time
`get(i)`, `set(i, x)`, `add(x)`, `remove(size - 1)`	`ArrayList`	`O(1)` (`add` is amortized)
`add(i, x)`, `remove(i)`, `contains`	`ArrayList`	`O(n)`
swap with the last element, then `remove(size - 1)`	`ArrayList`	`O(1)` (doesn't keep order)
`addFirst`, `addLast`, `pollFirst`, `pollLast`, `push`, `pop`	`ArrayDeque`	`O(1)`
`put`, `get`, `remove`, `containsKey`, `add`, `contains`	`HashMap` / `HashSet`	`O(1)` expected
`put`, `get`, `remove`, `ceilingKey`, `floorKey`, `firstKey`	`TreeMap` / `TreeSet`	`O(log n)`
`offer`, `poll`	`PriorityQueue`	`O(log n)`
`peek`	`PriorityQueue`	`O(1)`
`remove(Object)`, `contains`	`PriorityQueue`	`O(n)`
`new PriorityQueue<>(collection)`	`PriorityQueue`	`O(n)`
`Arrays.sort`, `List.sort`	array / list	`O(n log n)`
`Arrays.binarySearch`	sorted array	`O(log n)`
`s.contains(pat)`, `s.indexOf(pat)`	`String`	`O(n·m)` worst case, `m` = pattern length
`s.length()`, `s.charAt(i)`	`String`	`O(1)`
`s.substring(a, b)`	`String`	`O(b - a)` (copies the characters)

Using the input size to pick a target

A typical judge runs about 10⁸ simple operations per second. The constraints in a problem statement tell you roughly which complexity is expected:

`n` up to	Target complexity	Typical techniques
10 to 12	`O(n!)`	all permutations
20 to 25	`O(2ⁿ)`	all subsets, bitmask brute force
500	`O(n³)`	triple loops, Floyd–Warshall
5,000	`O(n²)`	all pairs, 2D dynamic programming
10⁵ to 10⁶	`O(n log n)` or `O(n)`	sorting, heaps, hashing, two pointers
10⁹ and more	`O(log n)` or `O(1)`	binary search, math

Time versus space

Many optimal solutions in this course spend memory to save time:

Brute force	Optimal	Extra memory
search the array again for each element, `O(n²)`	remember values in a `HashSet`, `O(n)`	`O(n)`
re-add a range for every query, `O(n)` per query	store prefix sums, `O(1)` per query	`O(n)`
rescan for the minimum after every pop	store the running minimum with each element	`O(n)`

When you present a solution, state both its time and its space complexity. If memory is tight, say what you would change, for example sorting in place instead of using a set.