Scoping, References & Mutation

Scoping & names

Python has 3 namespaces visible inside a nested function: Local (this function), Enclosing (outer function), Module (top-level). Plus Built-in (len, max, etc.). Reads walk up the chain (LEGB); writes are Local by default.

# READ — closure: inner sees outer's variables automatically (LEGB)
def outer():
    x = "outer"
    def inner():
        print(x)         # "outer" — found in Enclosing scope
    inner()


# WRITE — default rule: assignment makes the name Local, shadowing outer
def outer():
    x = "outer"
    def inner():
        x = "inner"      # creates a NEW local x; outer's x untouched
    inner()
    print(x)             # "outer"


# nonlocal — bind to Enclosing function's variable, allow writes
def outer():
    x = "outer"
    def inner():
        nonlocal x
        x = "inner"      # modifies outer's x
    inner()
    print(x)             # "inner"


# global — bind to Module namespace, allow writes (and creation)
y = "module"
def f():
    global y
    y = "modified"
f()
print(y)                 # "modified"


# Mutation does NOT trigger the local-write rule (no name reassignment)
def outer():
    lst = [1, 2]
    def inner():
        lst.append(3)    # mutating the list object; binding unchanged
    inner()
    print(lst)           # [1, 2, 3]    — no nonlocal needed


# += FOOTGUN — compiler treats augmented assignment as reassignment
def outer():
    x = 0
    def inner():
        x += 1           # UnboundLocalError without `nonlocal x`
    inner()
# Same trap with lst += [...]; use lst.append/lst.extend if you want
# mutation-without-rebind.

Summary:

• Read = walks LEGB chain automatically.
• Write = Local by default. nonlocal targets Enclosing. global targets Module.
• Mutation (.method(), [i] = x, [k] = v) ≠ reassignment. No scoping issue.
• Reassignment (=, +=, -=, ...) triggers Local-by-default rule.
• Immutable types (int, str, tuple, bool, None) only support reassignment — always need nonlocal/global from inner.
• Inner's locals are NOT visible to outer. There's no keyword to expose them. Pass data out via return, mutation of captured mutable, or nonlocal rebind.

Pass-by-reference & backtracking

Python uses pass by object reference: when you pass any object as an argument, the parameter inside the function refers to the same underlying object — no copy is made. Mutations in the callee are visible to the caller.

def f(lst):
    lst.append(99)            # mutates the SAME list

x = [1, 2, 3]
f(x)
print(x)                      # [1, 2, 3, 99]

For immutable types (int, str, tuple, etc.): pass-by-reference is still happening, but you can't observe it — any "modification" creates a new object and rebinds the parameter, leaving the caller's variable untouched.

def f(n):
    n += 1                    # rebinds local n to a new int; caller's x unaffected

x = 5
f(x)
print(x)                      # 5

Implication for recursion with shared state: all recursive calls see the same list/dict/set. This is what makes the backtracking pattern necessary — add to state before recursing, remove after.

# CANONICAL BACKTRACKING TEMPLATE (tree DFS carrying path state)
def dfs(node, path):
    if not node: return
    path.append(node.val)         # ADD self to state
    # ... do work using path (compute sums, check conditions, etc.) ...
    dfs(node.left, path)          # recurse — children see path including self
    dfs(node.right, path)
    path.pop()                    # REMOVE self before returning to caller

The pop at the end is critical. By the time control returns to the caller, path is restored to its state from before the call. Each sibling subtree sees only its actual ancestors, not stale leftovers from a previously explored sibling.

Without the pop, path would accumulate every node ever visited across the entire DFS — sibling subtrees would see ancestors AND each other's leftover state.

# WRONG — forgetting the pop
def dfs(node, path):
    if not node: return
    path.append(node.val)
    dfs(node.left, path)
    dfs(node.right, path)
    # missing: path.pop()
# After DFS, path holds the LAST-visited path, but during DFS siblings see polluted state.

Alternative: pass an immutable snapshot — dfs(node.left, path + [node.val]) creates a new list per call. Works but costs O(N) per call, turning O(N) algorithms into O(N²) or worse. Reserve for cases where the snapshot is genuinely small or where backtracking is awkward.

This pattern shows up everywhere there's a "current path / current state" carried through recursion: tree path sums, graph DFS with visited tracking, combinatorial search, N-queens, permutations.

Assignment & copying

a = b doesn't copy — it binds the name a to the same object that b points to. Mutations through either name affect the same underlying object. This is the same "pass by object reference" rule applied to ordinary assignment.

a = [1, 2, 3]
b = a                          # b refers to the SAME list as a
b.append(4)
print(a)                       # [1, 2, 3, 4]  — a sees the mutation
print(a is b)                  # True — same object

For immutable types (int, str, tuple), you can't observe this because "modifications" create new objects:

a = 5
b = a
b += 1                         # b rebinds to a new int (6); a still points to 5
print(a, b)                    # 5 6

Shallow vs deep copy

# SHALLOW COPY — copies the outer container; inner references are shared
a = [[1, 2], [3, 4]]
b = a.copy()                   # or a[:], or list(a)
b.append([5, 6])
print(a)                       # [[1, 2], [3, 4]]  — a unaffected (outer copy)
b[0].append(99)
print(a)                       # [[1, 2, 99], [3, 4]]  — a SEES this (inner shared)

# DEEP COPY — fully independent
import copy
b = copy.deepcopy(a)
b[0].append(99)
print(a)                       # unchanged

Common ways to copy

Why this matters in LC

Anywhere you "snapshot" mutable state during traversal — backtracking, ancestor tracking, BFS path recording. If you assign instead of copy, the "snapshot" continues to reflect mutations:

ancestors = []
ancestors_of_p = None

def dfs(node):
    nonlocal ancestors_of_p
    ancestors.append(node)
    if node is p:
        ancestors_of_p = ancestors        # WRONG — same list, gets popped later
        ancestors_of_p = ancestors[:]     # RIGHT — independent snapshot
    for child in [node.left, node.right]:
        if child: dfs(child)
    ancestors.pop()