Arrays and dynamic-array operation costs
Why you care
Every Python ETL job you have written is built on list, so you already use a dynamic array daily and probably cannot say which operations are cheap. That gap shows up as a job that takes four minutes on 50,000 rows and four hours on 5 million, because somebody wrote rows = rows[1000:] in a loop or batch.pop(0) to "consume" a batch. Interviewers ask about append cost, middle insertion and slicing to separate people who count work from people who count lines. This card comes first because every later structure is compared against the array.
Explain like I'm 5
Picture a row of numbered lockers in a corridor. Opening locker 417 is instant because you walk straight to the number. Adding a locker at the far end is easy while there is spare wall; when the wall runs out, the school builds a longer corridor and moves everything across once. Adding a locker at the front shifts every other locker one slot down. Copying "lockers 100 to 200" means carrying 100 items to a new row.
Core concept
A list is a contiguous block of references with a length and spare capacity, so position is a direct jump.
- Index read/write
xs[i]: O(1). - Scan (
in,index,count,max): O(n).inon a list is a scan, not a lookup. append/pop()at the end: amortized O(1). Most calls use spare capacity; an occasional call reallocates and copies all n references. The claim is about the total over many calls, not each call.insert(i, v)/pop(i)/del xs[i]: O(n - i), because the tail shifts. Front operations are O(n).- Slice
xs[a:b]: O(k), k = b - a, and it allocates a new list. Slicing in a loop is a hidden quadratic. - Copy
xs[:],list(xs): O(n) and shallow. The new list holds the same element objects.
Say the assumption with the cost: "append is amortized O(1) under geometric over-allocation". Use Complexity and amortization if pushed: n appends total O(n), so the average per call is O(1).
Decision rule: use a list when you read by position, append and remove at the end, or sort in place. Switch when you remove from the front (deque, Stacks, queues and deques), test membership repeatedly (set, Hash maps and sets under stated assumptions), or repeatedly want the smallest (heap, Heaps as partial order).
Minimal example Alias, copy and the repeated-row trap
a = [1, 2, 3]
b = a
c = a[:]
a.append(4)
print(b, c)
grid = [[0] * 2] * 2
grid[0][0] = 1
print(grid)
rows = [[0] * 2 for _ in range(2)]
rows[0][0] = 1
print(rows)[1, 2, 3, 4] [1, 2, 3]
[[1, 0], [1, 0]]
[[1, 0], [0, 0]]In production Catalogue batches, resize counting and shallow snapshots
import sys
import time
def count_resizes(n):
xs, last, changes = [], sys.getsizeof([]), 0
for i in range(n):
xs.append(i)
size = sys.getsizeof(xs)
if size != last:
changes, last = changes + 1, size
return changes
def elapsed(fn):
start = time.perf_counter()
fn()
return time.perf_counter() - start
N = 20_000
print("resizes under 1% of appends:", count_resizes(N) < N // 100)
def tail_appends():
xs = []
for i in range(N):
xs.append(i)
def head_inserts():
xs = []
for i in range(N):
xs.insert(0, i)
print("head insert slower than append:", elapsed(head_inserts) > elapsed(tail_appends))
catalogue = [["SKU1", 100], ["SKU2", 250]]
snapshot = catalogue[:]
catalogue[0][1] = 90
print("shallow snapshot sees price:", snapshot[0][1])
deep = [row[:] for row in catalogue]
catalogue[1][1] = 200
print("row-copy snapshot keeps price:", deep[1][1])
try:
[].pop()
except IndexError as exc:
print(f"IndexError: {exc}")resizes under 1% of appends: True
head insert slower than append: True
shallow snapshot sees price: 90
row-copy snapshot keeps price: 250
IndexError: pop from empty listIn your world
The situation
Your nightly Jenkins job reads a 300,000-row price file from S3 into a list, then loads it into Postgres in batches of 1,000. To "take the next batch" you wrote batch = rows[:1000] then rows = rows[1000:]. It passed every test with 5,000 rows.
What actually breaks
Each rows = rows[1000:] copies the remaining list: 300 batches × 150,000 average remaining = 45 million reference copies, slow but green. Finance then sends a 4.8-million-row backfill: 4,800 × 2.4M = 11.5 billion copies. Jenkins kills the job at 61% loaded, and the audit table says RUNNING with no end time.
What you'd do on Monday
Never rebuild the list to consume it. Walk with an offset, so each slice is O(batch) and total work is O(n).
for start in range(0, len(rows), BATCH):
batch = rows[start:start + BATCH] # O(BATCH), source untouched
load(batch)
audit.write(batch_no=start // BATCH, rows=len(batch))Imagine you work at Nykaa
The numbers
2.4M rows, batches of 1,000, so 2,400 slices. Rebuilding the list copies about 1.2M references per slice on average: 2,400 × 1.2M ≈ 2.9 billion pointer copies, roughly 23 GB of memmove at 8 bytes each, every hour.
What the Scenario-A answer does here
The Scenario A offset loop still works and its cost is flat. What breaks is the rest: 2.4M row dicts at an assumed 300 bytes is about 720 MB resident, and a rows[:] rollback snapshot shares every dict, so a later price edit corrupts it.
What flips at this scale
Stop materialising the whole list. Stream the file, build one batch of 1,000 at a time and checkpoint per batch in the audit table.
The trade-off you'd defend
I would defend a streamed batch loop over a full in-memory list, trading random access to any row for a flat memory ceiling and restartable batches.
Illustrative sizes and row counts; not Nykaa-published. The 300 bytes per row is an assumption.
Gotchas
Multiplying a list of lists
Setting grid[0][0] = 1 changes every row; the printed grid shows the same value in each.
[[0] * m] * n repeats references to one inner list.
[[0] * m for _ in range(n)].
Shallow copy that shares inner rows
A backup made with xs[:] shows the new price after an in-place edit to an inner list.
Slicing copies only the outer references.
[row[:] for row in xs].
Tricky questions
list.append O(1)?Yes, always constant time.
Amortized O(1). A call that triggers a reallocation costs O(n); the claim holds over a sequence of appends.
Scenario question
You're handed a function that removes processed records from the front of a 2-million-element list with pop(0) and is "mysteriously slow".
Model answer
I'd say each pop(0) shifts the remaining elements, so draining n items costs about n²/2 moves, around 2 trillion for 2 million. If order is FIFO I'd switch to a deque and popleft; if I only read once I'd iterate with an index. The trade-off is that a deque gives up cheap middle indexing.
Interview corner
CommonWhat are the costs of append, insert(0, x) and x in xs?
insert(0, x) is O(n) because everything shifts, and in is an O(n) scan.”TrickYou copy with ys = xs[:]. Are xs and ys independent?
Experience checkWhere has quadratic list work hit you?
Memory hook
A corridor of numbered lockers: jump to any number, add at the far end, never at the front, and never carry a slice you can walk past.
Count how many elements move; the tail is cheap, the front and the copy are not.
Self-check
Which list operations are O(n) but look like O(1)?
insert(0, x),pop(0),x in xs, andxs[a:b](O(b - a)).What does
xs[:]share withxs?The element objects. Only the outer array is new.
What does amortized O(1) append not promise?
That every call is constant.
Run the production block, then add a timing of xs.pop() n times versus xs.pop(0) n times for N = 20,000 and 40,000. Paste the four timings.