Time vs Space Complexity

Precomputing an index is the classic example. If you need to look up the positions of many words, scanning the list once to build a lookup table turns each later query into a constant-time operation. The space you spend is one entry per distinct key, and the time you save is a full scan per query.

words = ["alpha", "beta", "gamma", "alpha", "delta", "beta"]

index = {}
for position, word in enumerate(words):
    index.setdefault(word, []).append(position)

print(index["alpha"], index["beta"])
print(len(words), len(index))

The output shows the shape of the trade-off: the two keys that appeared twice have two positions each, and the six words collapsed into three distinct keys. Building the index cost one linear pass. After that, asking for the positions of alpha is a dictionary lookup, roughly constant time, instead of a scan of the whole list.

The cost is honest and worth naming. The index occupies memory proportional to the number of distinct keys, so a million distinct words means a million entries with their list overhead. It also has to be kept in step with the underlying list: if words are inserted or deleted, every stored position after that point shifts, and the index becomes wrong. That maintenance cost is what stops people from indexing everything.

The general rule: extra space is worth buying when it is proportional to the data you must query repeatedly, when the queries outnumber the updates, and when the resulting speedup is asymptotic rather than a constant. Build the index once, reuse it many times, and keep it small enough to fit the memory budget.

Transforming in place is O(1) extra space: you overwrite the element you are looking at and keep the result inside the same list. Building a new copy is O(n) extra space, because the new list holds n elements alongside the original.

def squared_in_place(values):
    for i in range(len(values)):
        values[i] = values[i] * values[i]
    return values

data = [1, 2, 3]
print(squared_in_place(data))
print(data)

Both printed lines show 1, 4, 9, and that is the point: after the call the original list itself holds the squares, so nothing extra was allocated beyond the loop counter. Compare that with a version that builds a second list through a comprehension, which would allocate three more cells for a three-element input and n more cells for an n-element input.

The trade-off is not only about memory. In place usually wins on cache locality, because you are writing to positions you have already read, while a fresh list means allocating, populating a new region of memory, and then later reading it back. In place is also harder to get wrong when the caller still holds a reference to the original, because the original is visibly changed rather than silently shadowed.

The interview-worthy point is when each choice wins. In place is the right answer when the caller has handed you ownership of the data or when the data set is large enough that the copy would matter. A new copy is the right answer when the original must survive intact, when the transformation is not really element-wise, or when in-place rewriting would force extra passes to avoid clobbering values you still need.

Start by asking whether the trade-off is asymptotic or cosmetic. Swapping a linear scan for a hash lookup changes the growth rate, and that is usually worth it when the data set can grow without bound. Precomputing a smaller constant is a different thing, and it needs measurements rather than reasoning.

Then price the memory. Extra space competes with everything else on the machine: the heap you are using, the connection pool, the cache. A cache that speeds up lookups by a large factor but evicts constantly may deliver no benefit at all, because a miss costs more than the scan you replaced. Size the structure against the real working set, not against the theoretical maximum.

Next, price the correctness and maintenance risk. A cached or precomputed structure is a second copy of the truth, and every write path must keep it in step. That is where space-for-time trades turn into bugs: a stale index that reads faster but returns the wrong answer is far worse than a slower correct query. Ask whether the invalidation is centralised, and if it is not, whether you can make it so.

Finally, measure under realistic conditions. Benchmark the realistic mix of reads and writes, with realistic key distributions, on hardware close to production, and compare end-to-end latency rather than microseconds in isolation. The decision rule I would defend in a review is simple: take the trade only when the measured win is significant, the memory is bounded and observable, and the invalidation story is airtight. Otherwise keep the simple linear version and revisit when a profiler tells you the cost is real.