Array

Array Code Labs

Mental Model

An interview “array” in Python is usually a list: an ordered sequence whose integer indices form a dense range from zero through len(values) - 1. Treat the index as part of the data model. A loop invariant should say what the processed prefix means, not merely that a loop counter moved.

For example, after processing values[:right], a result array might contain the answer for exactly those positions. That statement makes an off-by-one error visible: either right is already processed or it is the next position, but it cannot be both.

Python List Representation and Ownership

Python lists hold references to objects. Assignment creates another name for the same list; it does not copy the elements. A shallow copy creates a new outer list but still shares nested objects. In an interview, say whether the function may mutate its input before using an in-place technique.

The Python list documentation(opens in a new tab) defines the operations. Index reads and writes are constant-time operations. Appending is amortized O(1), while inserting or deleting near the front shifts later references and therefore costs O(n).

def replace_at(values, index, item):
    previous = values[index]
    values[index] = item
    return previous

Indexed Access, Mutation, and Copying

Choose the operation whose cost matches the proof:

Slicing inside a loop can turn a linear-looking solution into quadratic work. Repeatedly creating values[:right] copies a growing prefix; prefer indices or a maintained aggregate when the algorithm only needs a boundary.

def changed_copy(values, index, item):
    result = values.copy()
    result[index] = item
    return result

Use an Index as State

When values come from a known dense domain, a list can replace a hash lookup. If every value is in 1..n, index value - 1 is a collision-free location for that label. The invariant is precise: after scanning a prefix, seen[i] is true exactly when i + 1 occurred in that prefix. A duplicate sets the same boolean again; it must not toggle the bit back to false.

def mark_seen_indices(values):
    seen = [False] * len(values)
    for value in values:
        seen[value - 1] = True
    return seen

Choose an Array or a Different Structure

Use a list when positions are dense, order matters, and indexed access or mutation dominates. Use a dictionary instead when keys are sparse or not integers. Use a deque rather than a list when the hot operation removes from the front. Use a set when only membership matters and no positional answer is required.

Sorting may expose useful order, but it changes positions and costs O(n log n). Before sorting, check whether the required answer includes original indices or whether a one-pass hash map preserves the needed information more directly.

Common Pitfalls

• matrix = [[0] * columns] * rows aliases the same inner list; use a comprehension to allocate independent rows.
• if target in values is O(n), not O(1); placing it inside a scan can produce O(n squared) work.
• values = values + [item] allocates a new list, while append mutates the existing list.
• Negative indices wrap from the end, so an accidental -1 can return a plausible but wrong value.

Explain It in an Interview

Before coding, state: “I will use the index as the stable identity of each position, and after each iteration the processed prefix has its final result.” While coding, call out whether the list is an input you may mutate, a fixed-size output buffer, or auxiliary state. At the end, count every full scan, slice, sort, insertion shift, and allocated list before giving time and space bounds.

The focused Mark Seen Indices(opens in a new tab) drill practices direct domain-to-index mapping. Product Except Self(opens in a new tab) then requires two directional invariants over the same dense positions without hiding an extra division or nested scan.