Arrays

No. 01 · SVG · Type casestatic array · dynamic array · stack (LIFO)

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.

value: the data in a slot index: position, from 0 address: where the slot is in memory the index being read len: first free slot
Length n
Capacity
Space
Amortized append

Examples

Array · LeetCode 283

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.

O(n) timeO(1) spaceone pass over the array; only two index variables, i and w
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
Stack · LeetCode 20
input

Each opener is pushed, and each closer pops the top, which must be its matching opener.

O(n) timeO(n) spaceeach character is pushed or popped once; the stack can hold every 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

Time: what each operation costs

The last column fills in as you run operations on the bench, using the steps the machine actually took.

OperationCostWhyLast run on the bench
Access by indexO(1)The address is computed, not searched for: start + index × element size.not run yet
Append or pop at the endO(1) amortized for dynamic arraysNothing 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 middleO(n)Every element to the right shifts one slot to open or close the gap.not run yet

What "amortized" means

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.

Space: what the row itself costs

Static array

Exactly n slots, reserved up front. O(n) total, and it can never hold more than its capacity.

Dynamic array

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.

Stack (LIFO)

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.

Working in place

Swapping or overwriting elements inside the row needs O(1) extra space. That is what "in-place" asks for.

Trigger words: which one the problem wants

Plain array

  • index
  • in-place
  • iterate

You need to reach positions directly or walk the row once.

Stack (LIFO)

  • valid parentheses
  • most recent
  • undo
  • nested
  • next greater element

Last in, first out: the item you need next is always the one you saw last.

Template

# 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