DevPath
Tracks

Arrays and Dynamic Arrays

How arrays sit in memory, why indexing is instant, and how a growable array amortizes its cost.

beginner35 min#arrays#memory#amortized-analysis

Why it matters

Arrays are the default container of almost every program, and many other structures (hash tables, heaps, stacks, queues, matrices, even the vectors behind AI embeddings) are built on top of one. Interviewers love them because a small change in the problem (sorted? duplicates? in-place?) changes the best solution.

Intuition

Picture a row of numbered lockers, all the same size, built side by side. If you know the number of the first locker and the size of each, you can walk straight to locker i without opening any other: address = start + i * size. That single multiplication is why reading a[i] takes the same time whether the array holds ten items or ten million.

The price is rigidity. Lockers are contiguous, so inserting in the middle means sliding every later item over by one, and the row cannot grow if something else sits right after it.

10
0x00
20
0x04
30
0x08
a[2]
40
0x0C
50
0x10
Five 4-byte numbers in a row. Item 2 lives at start + 2 * 4 = 0x08, so the computer jumps straight there.

How it works

  • Contiguous memory: items are stored back to back, which is also very friendly to CPU caches.
  • Fixed capacity: a low-level array has a size decided up front.
  • Dynamic array: Python's list and JavaScript's Array hide a fixed array behind a wrapper. When it fills up, the wrapper allocates a bigger block (typically about twice the size), copies everything, and carries on.

Growing by a constant factor makes appends cheap on average. If the capacity doubles each time, copies happen at sizes 1, 2, 4, 8, ... and the total copying work for n appends is about 2n. Spread over n appends, that is O(1) each. This is called amortized O(1).

7
0
3
1
9
2
1
3
Size 4, capacity 4. The array is full.
step 1 / 5

A dynamic array of capacity 4 receiving a 5th item. Click Next to step through.

OperationTimeNotes
Read / write a[i]O(1)Address arithmetic
Append at endO(1) amortizedOccasional O(n) resize
Insert / delete at index iO(n)Shifts later items
Search unsortedO(n)Check each item
Search sorted (binary search)O(log n)Halve the range each step

Code: build a dynamic array

The best way to understand the table above is to build the wrapper yourself. Python's list already does this, so we use a plain list only as raw storage and never call its growth features.

class DynamicArray:
    def __init__(self):
        self._capacity = 4
        self._size = 0
        self._data = [None] * self._capacity  # raw fixed-size storage
 
    def __len__(self):
        return self._size
 
    def __getitem__(self, i):
        if not 0 <= i < self._size:
            raise IndexError("index out of range")
        return self._data[i]
 
    def append(self, value):
        if self._size == self._capacity:
            self._resize(self._capacity * 2)
        self._data[self._size] = value
        self._size += 1
 
    def insert(self, i, value):
        if not 0 <= i <= self._size:
            raise IndexError("index out of range")
        if self._size == self._capacity:
            self._resize(self._capacity * 2)
        for j in range(self._size, i, -1):  # shift right: O(n)
            self._data[j] = self._data[j - 1]
        self._data[i] = value
        self._size += 1
 
    def pop(self):
        if self._size == 0:
            raise IndexError("pop from empty array")
        value = self._data[self._size - 1]
        self._data[self._size - 1] = None
        self._size -= 1
        if self._capacity > 4 and self._size <= self._capacity // 4:
            self._resize(self._capacity // 2)  # shrink at 1/4 to avoid thrashing
        return value
 
    def _resize(self, new_capacity):
        new_data = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
        self._data = new_data
        self._capacity = new_capacity
 
 
arr = DynamicArray()
for n in range(10):
    arr.append(n * n)
arr.insert(2, 99)
print(len(arr), arr[2], arr.pop())

Both versions print 11 99 81.

Common pitfalls

  • Off-by-one errors: valid indexes are 0 to n - 1. Insert allows n (the end); read does not.
  • Mutating while looping: removing items from a list you are iterating skips elements. Build a new list or loop backwards.
  • Hidden O(n): list.insert(0, x) in Python and array.shift() or unshift() in JavaScript shift every item. Use a deque or an index pointer for queues.
  • Copy vs reference: b = a does not copy the array. Use a[:] / list(a) in Python or [...a] / a.slice() in JavaScript, and remember these are shallow copies.

Practice

Two Sum (sorted input) easy

Hint

Keep one pointer at each end. If the sum is too small, which pointer should move?

Show solution

Use two pointers. Start l = 0, r = n - 1. If a[l] + a[r] equals the target, return the pair; if it is smaller, move l right to increase the sum; otherwise move r left. Each step discards at least one candidate, so the time is O(n) and the extra space is O(1).

Remove duplicates in place medium

Hint

Use a slow pointer for where the next unique value goes and a fast pointer that scans.

Show solution

For a sorted array, keep write = 1. For each read from 1 to n - 1, if a[read] != a[read - 1] copy it to a[write] and increment write. Return write. O(n) time, O(1) space.

Rotate an array by k medium

Hint

Reversing is its own inverse. How many reversals give a rotation?

Show solution

Reverse the whole array, then reverse the first k % n items, then reverse the rest. Three O(n) passes, O(1) extra space.

Interview questions

  1. Why is array indexing O(1) but insertion O(n)? Indexing is address arithmetic; insertion shifts every later element.
  2. Why is append amortized O(1) and not O(1)? An occasional append triggers an O(n) resize; averaged over many appends the cost per append is constant.
  3. When would you pick a linked list over an array? Rarely in practice. Mainly when you hold node references and need O(1) splicing, or must never invalidate references. Arrays win on cache locality for most workloads.

Interviewers look for: stating complexity unprompted, asking whether the input is sorted or can contain duplicates, and handling the empty array and single-element cases.

Quick check

You append 1,000,000 items to a dynamic array that doubles when full. Roughly how many total element copies happen during resizes?

Finished this lesson?

Further resources

Related lessons