Drag along the row.
An array is a type case: one row of equal compartments, side by side in memory. Because every compartment is the same size, the address of any slot is simple arithmetic (start + index × size), so the pointer reaches any index in one jump. Adding at the end touches one compartment. Adding in the middle makes every tile to its right shift over. A stack is the same row, used only at the end.
FIG. 1 · A row of 8 reserved compartments holding 5 tiles, laid on a strip of memory starting at address 0x1000. Each slot is 8 bytes. Red marks what the code is touching right now. Callouts: A values, B indexes, C addresses, D the index pointer.
Move every 0 to the end in place, keeping the other values in order. The read index i scans once; the write index w marks where the next non-zero goes.
w = 0 for i, x in enumerate(nums): if x != 0: nums[w], nums[i] = nums[i], nums[w] w += 1 # O(n) time, O(1) extra space
Each opener is pushed, and each closer pops the top, which must be its matching opener.
stack, pair = [], {')': '(', ']': '[', '}': '{'}
for c in s:
if c in pair:
if not stack or stack.pop() != pair[c]:
return False
else:
stack.append(c)
return not stack # O(n) time, O(n) space
The last column fills in as you run operations on the bench, using the steps the machine actually took.
| Operation | Cost | Why | Last run on the bench |
|---|---|---|---|
| Access by index | O(1) | The address is computed, not searched for: start + index × element size. | not run yet |
| Append or pop at the end | O(1) amortized for dynamic arrays | Nothing has to move. A dynamic array sometimes pays for a full copy when it runs out of room, but doubling keeps the average constant. | not run yet |
| Insert or delete in the middle | O(n) | Every element to the right shifts one slot to open or close the gap. | not run yet |
| Search, unsorted | O(n) | With no order to exploit, the pointer checks slots one by one from index 0. | not run yet |
Amortized cost is the average cost per operation over a long run, not the cost of each single one. A dynamic array that doubles when full copies 8 elements once, then has room for 8 cheap appends, then copies 16 once, and so on. Most appends take 1 step and a rare one takes n steps, but the total for n appends is under 3n, so each append averages O(1). A single append can still be slow; it is the average that is constant. Fill the bench in Dynamic mode: the Amortized append figure jumps when the row resizes, then falls back toward 1 as the cheap appends follow.
Exactly n slots, reserved up front. O(n) total, and it can never hold more than its capacity.
Still O(n), but capacity can be up to twice the length, and during a resize the old row and the new row exist at the same time.
O(n) in the worst case, when every item is pushed before any is popped. Each push and pop is O(1). A stack can sit on either kind of array: a static one gives a fixed-size stack that overflows when full, a dynamic one (like a Python list) grows, so push is O(1) amortized.
Swapping or overwriting elements inside the row needs O(1) extra space. That is what "in-place" asks for.
You need to reach positions directly or walk the row once.
Last in, first out: the item you need next is always the one you saw last.
# Array: loop with index and value for i, x in enumerate(nums): pass # process nums[i] # Stack: push, pop, peek, is empty stack = [] for x in items: while stack and should_pop(stack[-1], x): # condition depends on problem stack.pop() stack.append(x) # stack[-1] peeks at the top; check "if stack" before peeking or popping