Two pointers and safe in-place movement
Why you care
On the job, "rewrite this buffer without allocating a second copy" shows up whenever a batch is big enough that a copy hurts: dropping voided rows, deduplicating a sorted extract, splitting a file into good and bad. Interviewers ask two-pointer questions because they expose whether you can state what each pointer promises, not whether you remember a trick. The usual failure is overwriting a value you have not read yet. This card comes before windows because windows are two pointers with a running aggregate attached.
Explain like I'm 5
Picture a conveyor belt with a packer. A reader walks along the belt looking at every item. A writer stands at the start of a clear shelf and only moves forward when the reader hands over an item worth keeping. The shelf is the front of the same belt, so the writer can never get ahead of the reader. The reader has already looked at anything the writer is about to overwrite.
Core concept
Two pointers are two indices with a written promise about the region each has finished.
- Opposing pointers start at both ends and move inward. They need a proof for discarding: on sorted input, if the pair sum is too small, the left element is too small for every remaining partner. Without order there is no such proof.
- Same-direction pointers (reader and writer) keep one invariant:
xs[:w]is the answer so far,xs[w:r]is overwritable,xs[r:]is unread. Sincew <= r, a write never destroys unread data. - Cost: each pointer moves forward at most n times, so O(n) time and O(1) extra space. Derive it from movement, not loop syntax.
- State your mutation permission. After in-place compaction the tail beyond
wis stale.
Decision rule: use opposing pointers when sortedness proves which end to discard; use reader/writer to filter, dedupe or partition in place. For unsorted pairs use a set (Hash maps and sets under stated assumptions).
Minimal example Write pointer compaction
def compact(xs, drop):
w = 0
for r in range(len(xs)):
if xs[r] != drop:
xs[w] = xs[r]
w += 1
return w
orders = [5, 0, 7, 0, 0, 9]
n = compact(orders, 0)
print(n, orders[:n])
print(orders)3 [5, 7, 9]
[5, 7, 9, 0, 0, 9]The second line is the lesson: the list is not shortened, and its tail still holds old values. Return the count and let the caller slice.
In production Opposing-pointer scan and in-place filter
from itertools import pairwise
def assert_sorted(xs):
if any(a > b for a, b in pairwise(xs)):
raise ValueError("input must be sorted ascending")
def converge_on_total(amounts, target):
"""Opposing pointers on sorted input: indices i < j with sum == target."""
assert_sorted(amounts)
lo, hi = 0, len(amounts) - 1
while lo < hi:
s = amounts[lo] + amounts[hi]
if s == target:
return lo, hi
if s < target:
lo += 1 # amounts[lo] is too small for every remaining hi
else:
hi -= 1 # amounts[hi] is too big for every remaining lo
return None
def keep_in_place(rows, keep):
"""Same-direction pointers: stable, in place. Returns the kept count."""
w = 0
for r in range(len(rows)):
if keep(rows[r]):
rows[w] = rows[r]
w += 1
return w
debits = [120, 250, 400, 650, 900]
print(converge_on_total(debits, 1050))
print(converge_on_total(debits, 100))
try:
converge_on_total([900, 120, 400], 1020)
except ValueError as e:
print(f"ValueError: {e}")
batch = [("o1", "paid"), ("o2", "void"), ("o3", "paid"), ("o4", "void"), ("o5", "paid")]
n = keep_in_place(batch, lambda row: row[1] == "paid")
del batch[n:]
print(batch)(2, 3)
None
ValueError: input must be sorted ascending
[('o1', 'paid'), ('o3', 'paid'), ('o5', 'paid')]The sortedness check costs O(n), the same order as the search, so keep it in production code and drop it only when a caller contract guarantees order.
See it happen Reader and writer on one list
- The reader and writer both start at index 0; 5 is kept, so it is copied onto itself and the writer moves to 1.
- The reader sees 0, a dropped value, so the writer stays at slot 1, which is now the next target.
- The reader finds 7 and writes it into slot 1; the 0 that lived there was already read, so nothing is lost.
- The reader reaches 9 at index 5 and writes it into slot 2, after skipping two more zeros.
- The writer is at 3, so slots 0 to 2 are the answer and slots 3 to 5 are stale leftovers, not cleared values.
In your world
The situation
A Jenkins job loads a 2M-row orders extract into a list and drops voided rows with for i, o in enumerate(orders): if o.void: orders.pop(i).
What actually breaks
Popping while iterating skips the row that slides into the freed slot, so 41,870 voided rows of 312,904 survive. Each pop also shifts the tail, so the step is quadratic.
What you'd do on Monday
Use the reader/writer pass: copy kept rows forward, then del orders[w:]. Assert that no kept row is void and log kept and dropped counts to the audit table.
Imagine you work at Amazon
The numbers
40M rows × ~120 B ≈ 4.8 GB raw, about 16 GB as Python tuples. Dropping 25% with del rows[i] on 1M-row chunks shifts ~3.2 MB per drop: 250k drops × ~0.3 ms ≈ 75 s per chunk, 40 chunks ≈ 50 min. A write-pointer pass is 40M steps × ~0.15 µs ≈ 6 s.
What the Scenario-A answer does here
The Scenario A fix (reader/writer) is still the right loop, but it assumes the list fits in memory. At 16 GB it does not.
What flips at this scale
The pointers become a read cursor and a write cursor over chunk files of 1M rows (~400 MB). Survivors are appended to an output object, so memory is bounded by the chunk and the invariant is unchanged.
The trade-off you'd defend
I would defend chunked streaming filters over one giant in-place pass, trading the strict O(1) extra-space guarantee for a bounded buffer and a second output file that makes retries safe.
Illustrative figures chosen so the arithmetic is visible; not Amazon-published.
Gotchas
Overwriting a value you have not read
After a partition, one value is missing and another appears twice.
The writer got ahead of the reader, or a swap lost the displaced value.
Write what xs[:w], xs[w:r] and xs[r:] mean first, and assert w <= r.
Trusting the tail after compaction
Downstream sees [5, 7, 9, 0, 0, 9] and loads 6 rows instead of 3.
In-place compaction leaves stale values past w.
del xs[w:], or pass xs[:w].
Tricky questions
There is a while inside a for, so it is O(n squared).
Count movement. If each pointer only moves forward and never resets, the total is at most 2n moves, whatever the syntax.
Scenario question
You're handed a sorted list of 5M settlement amounts and must find a pair of amounts whose total matches a reconciliation figure, without extra memory.
Model answer
I'd use opposing pointers: if the sum is too small the left value is too small for every remaining partner, so I advance it. That is O(n) time and O(1) space. The trade-off is that I rely on sortedness, so I'd verify it once. For unsorted data I'd take a set and pay O(n) memory.
Interview corner
CommonWhen do you reach for two pointers?
TrickIs this nested loop O(n squared)?
Experience checkTell me about a time you cleaned data in place.
Memory hook
Reader looks at everything; writer only advances for keepers; the writer never passes the reader.
Write down what the region behind each pointer means before you write the loop.
Self-check
Why is overwriting safe in reader/writer?
Because
w <= r, every slot the writer touches was already read.Why do opposing pointers need sorted input?
The discard proof depends on order.
Time and space of a two-pointer pass?
O(n) time, O(1) extra space.
Take a 200,000-element list where every 4th item is "void". Time pop(i)-based removal against keep_in_place with time.perf_counter, and paste both timings plus an assertion that the kept lists are equal.