Arrays

Contiguous memory

An array stores elements back-to-back. Because every slot is the same size, address(i) = base + i * size, so reading arr[i] is O(1). The cost is that inserting in the middle must shift everything after it — O(n).

Row of numbered lockers

You can walk straight to locker 47 without checking 1–46. But to squeeze a new locker between 10 and 11, every later locker has to move down one.

Core operations

Access and append (amortised) are cheap; insert/delete at the front are linear.

a = [10, 20, 30, 40]
a[2]            # O(1)  -> 30
a.append(50)   # O(1) amortised
a.insert(0, 5) # O(n)  shifts everything right
a.pop()        # O(1)  from the end
a.pop(0)       # O(n)  from the front

Interview pattern

Clues like "sorted array", "in place", "contiguous subarray", or "fixed extra space" point to arrays with two pointers, prefix sums, or a sliding window.