Mutable vs Immutable in Python: The Property Behind Your Interview Bugs

You wrote path.append(node) in your backtracking solution. You traced through the recursion in your head. You felt good. You hit run. The output was a list of empty lists. Not wrong values. Not an exception. Empty lists. Every single one.

Or you built a string inside a loop, got "accepted," and then watched an interviewer write "performance concerns" in their notes on code that technically did work.

Both bugs trace to the same property you've probably skimmed over a dozen times: mutability. You know it exists. You just haven't fully felt it in your bones yet.

What Mutable vs Immutable Means

An object is mutable if its contents can change after creation. Immutable means they can't.

That's the definition. Everything else is fallout.

A Python list is mutable. lst[0] = 99 changes the list in place. The variable still points to the same object in memory. The object is different. A Python string is immutable. s.upper() doesn't touch s. It creates a brand new string object and returns it. The original just sits there unchanged, blissfully unaware anything happened.

lst = [1, 2, 3]
lst[0] = 99
print(lst)      # [99, 2, 3] - same object, different contents

s = "hello"
s2 = s.upper()
print(s)        # "hello" - untouched
print(s2)       # "HELLO" - new object

The distinction controls what happens when you pass objects to functions, store them as dictionary keys, share them across threads, or try to save a snapshot inside a recursive call.

Know Your Language's Rules

Every language makes its own choices. Know them before the interview clock starts.

Python: immutable types are int, float, bool, str, tuple, frozenset, bytes. Mutable: list, dict, set, bytearray, and class instances by default.

Java: String is immutable. StringBuilder is mutable. Boxed primitives (Integer, Long) are immutable. Most objects you create are mutable unless you design them otherwise.

JavaScript: all primitives (string, number, boolean, null, undefined, symbol, bigint) are immutable. Objects and arrays are mutable. This is also the specific trap that const sets for anyone not paying attention.

const arr = [1, 2, 3];
arr.push(4);        // fine - arr still points to the same object
arr = [5, 6, 7];    // TypeError - the variable binding is const, not the contents

const stops you from pointing the variable somewhere else. It says nothing about what you can do to the thing it points to. New JavaScript developers learn this the hard way, usually at the worst possible time.

Why Python Strings Are Immutable

Three practical reasons.

Strings need to be reliable dictionary keys. Mutable keys would silently break hash maps. A hash map indexes entries by hash value. If a key could change after insertion, its hash would change and the map would lose the entry with no error. TypeError: unhashable type: 'list' is Python telling you: this thing can change, so you can't hash it, so you can't use it as a key. Strings are immutable, hash is stable, they work as keys.

They can also be interned. Languages maintain a pool of common strings and reuse the same object for identical literals. Python does this automatically for short strings. Java interns all string literals in the string pool. Interning only works if the object can never be modified. You can't share one copy if someone might change it out from under everyone else.

And they're safe across threads without locks. No thread can corrupt data it can never modify. This matters more for runtime design than for day-to-day coding, but it's why the language designers made the call.

The O(n²) Trap You Don't See Coming

The most common performance bug caused by immutability: string concatenation in a loop.

# This looks O(n). It runs in O(n²).
result = ""
for char in characters:
    result += char

Every += creates a brand new string object by copying all the existing content into it. First iteration: copy 0 characters. Second: copy 1. Third: copy 2. Total work: 0 + 1 + 2 + ... + (n-1). That's O(n²). You wrote a loop and accidentally built a triangle of work.

The fix: collect into a list, then join once at the end.

parts = []
for char in characters:
    parts.append(char)
result = "".join(parts)  # O(n) total

list.append() is amortized O(1). str.join() makes one pass and allocates exactly the right amount of memory up front. This pattern covers reversals, permutations, path encoding, serialization. Any time you're building a string character by character, the list accumulator is the move.

Java equivalent, which you should use explicitly rather than hoping the compiler bails you out:

StringBuilder sb = new StringBuilder();
for (char c : chars) {
    sb.append(c);
}
String result = sb.toString();

Modern Java compilers sometimes optimize String += in loops into StringBuilder automatically. "Sometimes" is not a thing you want to rely on when an interviewer is writing notes.

Save `path[:]`, Not `path`

Now for the bug that produces the list of empty lists.

Backtracking works by appending to path, recursing, then popping when you backtrack. At leaf nodes, you save the current path into result. The bug: you save a reference to the mutable list object, not a copy of its contents at that moment.

def backtrack(candidates, start, target, path, result):
    if target == 0:
        result.append(path)         # BUG: saves the list object, not a snapshot
        return
    for i in range(start, len(candidates)):
        path.append(candidates[i])
        backtrack(candidates, i, target - candidates[i], path, result)
        path.pop()

result = []
backtrack([2, 3, 6, 7], 0, 7, [], result)
print(result)   # [[], [], []] - every entry is the same empty list

By the time the recursion finishes, path has been fully unwound back to empty. Every entry you saved into result points to that same object. So every entry shows the current state of path, which is empty. The diagram below shows what's actually happening in memory.

Memory diagram showing multiple result entries pointing to the same mutable path object vs each pointing to their own copy

Save a copy of the contents, not a reference to the container.

result.append(path[:])      # saves a snapshot
result.append(list(path))   # identical

path[:] creates a new list object with the same contents at that exact moment. Subsequent recursive calls modify path, but the saved snapshots are untouched.

The copy costs O(k) where k is the current path length. For a problem generating O(2^n) leaf nodes with paths up to length n, the total copy cost is O(n · 2^n). That's already the lower bound for listing all subsets. You aren't adding asymptotic work by copying.

When Shallow Copies Aren't Enough

A shallow copy creates a new container but fills it with the same references. If those references point to mutable objects, the copy and the original share them.

original = [[1, 2], [3, 4]]
shallow = original[:]   # new list, same inner lists

shallow[0].append(99)
print(original)         # [[1, 2, 99], [3, 4]] - the inner list is shared

A deep copy recursively duplicates everything.

import copy
deep = copy.deepcopy(original)
deep[0].append(99)
print(original)         # [[1, 2], [3, 4]] - fully independent

For most backtracking problems, shallow is fine. Paths hold integers. Integers are immutable. path[:] on a list of ints gives you fully independent data. When your data contains nested mutable objects, reach for copy.deepcopy(). You'll know when you need it because the shallow copy will produce the same kind of surprise as the path bug.

You Can't Hash a List. Here's the Pattern.

Only immutable objects can be dictionary keys or set members. This surfaces when memoizing a recursive function whose parameter is a collection.

memo = {}
memo[[1, 2, 3]] = True   # TypeError: unhashable type: 'list'

memo[tuple([1, 2, 3])] = True   # works
memo[(1, 2, 3)] = True          # same thing

Convert to tuple when memoizing with a list parameter. Convert to frozenset when memoizing with a set. This is standard for bitmask DP, subset enumeration, and any problem where the state is a collection of visited nodes or chosen items.

The Cost Trade-Off

Immutability has a direct cost: every modification creates a new object. For small objects it's negligible. For objects being built over many iterations, it compounds. String concatenation is the example everyone learns the hard way, usually during a contest submission or a debrief they didn't expect.

The flip side is that immutable objects are safe to share. Pass one to five different functions and none of them need their own defensive copy. That saves allocation time and memory. Shared immutable data is free. Shared mutable data is a coordination problem.

Use mutable objects for accumulators you're building. Snapshot them with a copy when you need to preserve a version.

Quick Reference

Type	Python examples	Dict key?	In-place mod?
Immutable	`str`, `int`, `tuple`, `frozenset`	Yes	No
Mutable	`list`, `dict`, `set`	No	Yes

Key rules:

Immutable objects can't change after creation. Mutable objects can.
String concatenation in a loop is O(n²). Use a list accumulator and join once.
In backtracking, save path[:] not path when recording results.
Only immutable objects can be dict keys. Convert lists to tuples, sets to frozensets.
Shallow copies work when the container holds primitives. Deep copies for nested mutable objects.

If you want rubric-based feedback on whether you're catching mutability bugs at the right points in your solution, SpaceComplexity runs voice-based mock interviews with structured scoring. It'll tell you if you saved a reference where you needed a copy.

For more on the performance side, see string concatenation in a loop. For the backtracking snapshot bug with its full proof, see pass by value vs reference in Python.