Arrays and Strings: List Mechanics, In-Place Updates, Two Pointers

A truck weighbridge logger writes -1 whenever a sensor read fails. By the end of a shift the list of readings has holes in it, and the downstream report must not see them. The tempting fix is to build a new list; the better question is whether you can clean the original in a single pass without extra memory. Answering it needs a clear picture of what a Python list is, and then one small idea: use two indexes instead of one.

What a Python list actually is

A Python list is a dynamic array: a contiguous block of references that grows when it fills up. Reading readings[i] jumps straight to slot i, so indexing is O(1). append is O(1) amortized because capacity is reserved ahead of use. Anything that has to move the elements after a position, such as insert(0, x) or del a[0], is O(n).

Strings are arrays of characters too, and indexing and slicing work the same way, with one important difference you will meet in the last lesson: strings cannot be changed in place.

Two traps hiding in innocent-looking code

Assignment never copies a list; it adds a second name for the same object. And multiplying a list of lists repeats the reference, not the contents. Both are visible in a few lines.

readings = [412, 415, 409, 420]
alias = readings            # a second name, same list
snapshot = readings[:]      # a slice builds a new list
alias.append(430)
print("readings:", readings)
print("snapshot:", snapshot)
print("same object?", alias is readings, "| copy same object?", snapshot is readings)

grid = [[0] * 3] * 2        # two references to ONE inner list
grid[0][1] = 9
print("shared rows  :", grid)

grid = [[0] * 3 for _ in range(2)]
grid[0][1] = 9
print("separate rows:", grid)

print(readings[-1], readings[1:3], readings[::-1])
try:
    readings[10]
except IndexError as err:
    print("IndexError:", err)
print(readings[10:12])      # slices are forgiving; indexes are not

readings: [412, 415, 409, 420, 430]
snapshot: [412, 415, 409, 420]
same object? True | copy same object? False
shared rows  : [[0, 9, 0], [0, 9, 0]]
separate rows: [[0, 9, 0], [0, 0, 0]]
430 [415, 409] [430, 420, 409, 415, 412]
IndexError: list index out of range
[]

The first trap is why functions that "modify a list" surprise their callers: the caller's name points at the same object. The second is why one assignment to grid[0][1] appears in both rows. The list comprehension builds a fresh inner list per row. Note also the last two lines: an out-of-range index raises IndexError, while an out-of-range slice quietly returns an empty list.

Cleaning a list in place with a write pointer

Back to the weighbridge. Use one index, read, to scan every value, and a second, write, that marks where the next kept value belongs. Because write never runs ahead of read, you can overwrite the front of the same list safely. At the end, everything before write is the cleaned data and the leftover tail is deleted.

def drop_failed_reads(readings, bad=-1):
    """Remove every `bad` value in place, keeping order. Returns the new logical length."""
    write = 0
    for read in range(len(readings)):
        if readings[read] != bad:
            readings[write] = readings[read]
            write += 1
    del readings[write:]            # trim the leftover tail
    return write


weighbridge = [18200, -1, 17950, -1, -1, 18010, 18400, -1]
same_list = weighbridge
kept = drop_failed_reads(weighbridge)
print(weighbridge, "kept", kept)
print("still the same list object:", weighbridge is same_list)

[18200, 17950, 18010, 18400] kept 4
still the same list object: True

One pass, O(n) time, O(1) extra space, and every other reference to the list sees the cleaned data. The same skeleton solves "remove duplicates from a sorted array", "move zeros to the end" and "keep only values that pass a test": only the if condition changes.

Two pointers from opposite ends

When the array is sorted you can place one pointer at each end and move whichever one improves the situation. A cafe gives a voucher of 225 and wants two menu items whose prices add up to exactly that. If the sum is too small, only moving the low pointer up can help; if it is too large, only moving the high pointer down can. Each step discards one candidate for good, so at most n - 1 steps are needed instead of checking every pair.

def pair_for_voucher(prices, voucher):
    """prices sorted ascending. Return two prices summing exactly to voucher, plus steps taken."""
    left, right, steps = 0, len(prices) - 1, 0
    while left < right:
        steps += 1
        total = prices[left] + prices[right]
        if total == voucher:
            return (prices[left], prices[right]), steps
        if total < voucher:
            left += 1               # need a bigger sum: move the low end up
        else:
            right -= 1              # need a smaller sum: move the high end down
    return None, steps


menu = [40, 55, 70, 95, 120, 150, 185, 230]
print(pair_for_voucher(menu, 225))
print(pair_for_voucher(menu, 100))


def reverse_range(a, i, j):
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1


def rotate_right(a, k):
    """Rotate in place by k using three reversals."""
    n = len(a)
    k %= n
    reverse_range(a, 0, n - 1)
    reverse_range(a, 0, k - 1)
    reverse_range(a, k, n - 1)


shifts = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
rotate_right(shifts, 3)
print(shifts)

((40, 185), 2)
(None, 7)
['Fri', 'Sat', 'Sun', 'Mon', 'Tue', 'Wed', 'Thu']

The pair search finished in 2 steps for a valid voucher and in 7 (n - 1) for an impossible one. The rotation trick is a second two-pointer pattern: reverse the whole list, then reverse each of the two parts, and the elements land in their rotated positions without a second list. Be careful that the technique depends on the sorted order; the same pointer moves on unsorted data give plausible, wrong answers.

Common mistakes

• Removing items while looping over the same list. Symptom: some elements are silently skipped, for example looping over [1, 1, 2] and removing each 1 leaves [1, 2]. Use a write pointer or build a new list.
• **[[0] * n] * m for a grid.** Symptom: writing to one cell changes a whole column of cells. Use a comprehension for the rows.
• Slice end off by one. Symptom: results that are always missing the last element. a[i:j] includes i and excludes j.
• Reading `a[i + 1]` on the last iteration. Symptom: IndexError: list index out of range. Stop the loop one earlier or check bounds first.
• Using the opposite-ends pattern on unsorted input. Symptom: no error, wrong answers. Sort first, or use a hash set instead.

How this shows up in real projects and interviews

In real code the write-pointer idea appears in log compaction, de-duplicating sorted records and in-place buffer cleanup, and the aliasing trap is behind a large share of "why did my data change?" bug reports. Interviewers use "remove duplicates in place", "move zeroes", "two sum on a sorted array" and "rotate an array by k" because they test exactly the two habits in this lesson: tracking positions with indexes, and stating the time and space cost. Say aloud which pointer moves and why, and mention that you are modifying the input, since some interviewers expect you to ask whether that is allowed. The next lesson, the sliding window, extends the two-pointer idea to ranges.