Arrays & Strings

Arrays are the default shape of interview input because they are simple to draw and brutal about cost. You can jump to nums[i] instantly, but you pay for anything that forces elements to move.

Strings look similar, but in Python they are immutable. That one fact changes how you build and edit them: repeated concatenation copies; collecting pieces and calling "".join(...) does one final copy.

The core habit is to separate reading from writing. Often one index scans the original data while another writes the compacted result in place.

The mental model

An array stores elements in contiguous slots. If the runtime knows the address of slot 0 and the size of each element reference, it can compute the address of slot i directly. That is why indexing is O(1).

Python’s list is a dynamic array: when it fills up, Python allocates a larger backing array and copies the old references into it. One unlucky append can be O(n), but because the array grows by extra capacity instead of one slot at a time, a long sequence of appends averages to amortized O(1) per append.

nums = []
for x in range(5):
    nums.append(x)       # amortized O(1)

third = nums[2]          # O(1) indexing
nums.insert(1, 99)       # O(n): shifts everything from index 1 onward
nums.pop(1)              # O(n): shifts elements left

For strings, treat each edit as producing a new string:

# Bad for many pieces: each += copies the growing prefix.
out = ""
for part in parts:
    out += part

# Good: collect references, then copy once.
out = "".join(parts)

For in-place array edits, keep a write index:

def keep_positive(nums):
    write = 0
    for x in nums:
        if x > 0:
            nums[write] = x
            write += 1
    return nums[:write]

The read loop sees every element once. The write pointer marks the next slot in the compacted prefix.

Pattern recognition

Variations

Worked problems

Try to name the cost before opening each solution. The code is short because the pattern is the point.

def remove_duplicates(nums):
    if not nums:
        return 0

    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1

    return write

def move_zeroes(nums):
    write = 0

    for x in nums:
        if x != 0:
            nums[write] = x
            write += 1

    for i in range(write, len(nums)):
        nums[i] = 0

def product_except_self(nums):
    ans = [1] * len(nums)

    left = 1
    for i, x in enumerate(nums):
        ans[i] = left
        left *= x

    right = 1
    for i in range(len(nums) - 1, -1, -1):
        ans[i] *= right
        right *= nums[i]

    return ans

The classic pitfall

For strings, the same rule is hiding in a different form: repeated concatenation moves the whole growing prefix again and again. Build a list of pieces, then join once.