Space Complexity + Section Quiz

Time is only half the story. The other half — how much extra memory your solution uses — decides between two equally fast solutions and shows up in every interview: "can you do it with O(1) space?"

What counts as space

Space complexity measures the extra memory the algorithm allocates, beyond the input it was given:

The input itself doesn't count (it already existed).
Loose variables (i, total, best) cost O(1) — they don't grow with n.
A copy of the array, a hash map that may hold all the elements, a result list the size of the input: O(n).
An n × n matrix: O(n²).

def soma(nums):           # space O(1):
    total = 0             # one variable, whatever n is
    for x in nums:
        total += x
    return total

def dobrados(nums):       # space O(n):
    resultado = []        # grows along with the input
    for x in nums:
        resultado.append(x * 2)
    return resultado

The time × space trade-off

This is one of the most important ideas in the entire course: you can often buy time by paying with memory.

Remember the example from lesson 1? Detecting duplicates in O(n²) uses O(1) space; the O(n) version uses a set that may hold all the elements — O(n) space. There's no free lunch: the fast version pays with memory.

Solution	Time	Space
Compare every pair	O(n²) 🐢	O(1) 💚
Set of seen items	O(n) 🚀	O(n) 💸

On LeetCode this trade is almost always worth it (memory limits are generous), and it's exactly what the hash map pattern does — the first lesson of the Array section.

Hidden space: the recursion stack

When a function calls itself, each pending call takes up memory on the call stack. A recursion that goes n levels deep uses O(n) space even without creating any list! Keep this idea in mind — it comes back strongly in the Trees and Dynamic Programming sections.

Section quiz — Fundamentals

This quiz wraps up the section. If you get 7 or more right, you're ready for the Array section. Any doubt, the three lessons are right here — rereading is part of the method.

🧠 Section quiz: Big-O

0/8

1. What does an algorithm's Big-O describe?

2. Why is O(2n + 100) simplified to O(n)?

3. for i in range(n): for j in range(i + 1, n): compare(i, j) What's the Big-O?

4. Sorting the array and then making a single pass over it costs, in total:

5. Searching for a value with `x in my_list` (a list of n items, unsorted) costs:

6. A solution uses only the variables `i`, `best`, and `current`, whatever the size of the array. The extra space is:

7. An O(n)-time solution uses a hash map that may hold all n elements. Another is O(n²) time with O(1) space. For n = 100,000 on LeetCode, which to choose and why?

8. A recursive function calls itself n times deep (each call waits for the next). Even without creating lists, the space is:

Section summary

You now have the vocabulary the whole course uses:

Big-O = the shape of the growth, worst case, no constants.
Sequence adds, nesting multiplies, halving becomes log.
Built-in operations have a hidden cost (list in = O(n), sort = O(n log n)).
Extra space counts — and trading memory for time (hash map) is the most profitable trade on LeetCode.

Now for real: the Array section, where these fundamentals turn into solving patterns.

All lessons in this section