CONCEPT · Novice
Space complexity
also memory · MLE
How much extra memory the solution allocates. Typical limits are 256 MB — a few 2e5 arrays of 64-bit ints are fine; an n×n table at n = 2e5 is not.
Intuition
An array of 1e7 ints is about 40 MB. An array indexed by 1e9 is a crash, not a table.
When to reach for it
- Allocating DP tables
- Choosing adjacency matrices vs adjacency lists
- Whether to keep all queries or process online
Usual pits
- vector<vector<int>>(n, vector<int>(n)) at n = 5000 is 100 MB of ints plus overhead
- Recursion depth of n = 2e5 without raising the stack