Dynamic arrays and growth

Blocks can't grow

A plain array has a fixed length, set when its block of memory is allocated. Programs, though, rarely know in advance how many items they will collect: lines read from a file, results of a query, events from a network. They need an array that grows.

The difficulty is that a block of memory can't simply get longer. The bytes after it may hold other data. Occasionally the allocator can extend a block in place, but nothing guarantees it. The general solution is to allocate a larger block somewhere else, copy the elements across and free the old one. Python's list, Java's ArrayList, C++'s std::vector, Rust's Vec, Go's slices and JavaScript's arrays all work this way. They are called dynamic arrays.

Size and capacity

Copying everything on every append would make each append O(n), and building a list of n items O(n²). So a dynamic array keeps two numbers: its size, how many elements it holds, and its capacity, how many fit in its current block. The slots between size and capacity are spare. As long as there is a spare slot, an append is a single write and an increment, exactly like assigning to an index.

The trace above starts with size 4 and capacity 4. Appending 9 finds no room, so the array allocates a block of 8, copies the 4 elements, frees the old block and then writes 9. The next three appends need no copying at all. Only the append after those, the ninth, will trigger another resize.

Why doubling works

Doubling makes resizes rare, but each resize copies more elements than the last. To see the total, follow an array from capacity 1 as n elements are appended. It resizes when it holds 1, 2, 4, 8 and so on, copying that many elements each time:

1 + 2 + 4 + … + n/2 + n  <  2n

Each term of that sum is one more than all the terms before it combined, so the whole sum stays below twice its largest term. Building an array of n elements therefore costs fewer than 2n copies plus n writes: O(n) in total, which is O(1) per append when averaged over all of them. That average, taken over a sequence of operations rather than over random inputs, is called the amortized cost. It is a guarantee, not a probability: any sequence of n appends costs O(n).

Individual appends are not all cheap. The one that triggers a resize costs O(n) on its own. For most programs only the total matters. For a program with strict latency limits, such as a game rendering frames or a trading system, one slow append at the wrong moment can be a problem, and reserving capacity in advance avoids it.

Why a fixed step fails

Growing by a fixed amount, say 10 slots at a time, sounds more economical but changes the cost class. With n elements, the array has resized about n/10 times, copying 10, then 20, then 30 elements and so on: roughly n²/20 copies in total. Divide by n and each append costs O(n) on average.

Any constant growth factor greater than 1 gives amortized O(1). The factor only trades memory for copying:

A larger factor copies less often but can leave up to half the block unused. Python's small factor wastes little memory, at the price of more frequent resizes.

Reserving and shrinking

When you know how many elements are coming, say so. std::vector::reserve(n), new ArrayList<>(n), make([]T, 0, n) in Go and Vec::with_capacity(n) allocate the final block once, so no resize ever happens. This is one of the cheapest optimizations available, and in C++ it also keeps pointers into the vector valid while you fill it.

Removing elements raises the opposite question. Most dynamic arrays don't shrink when you remove elements, because memory that was needed once is likely to be needed again. Those that do, such as Python's list, shrink only when the array is much emptier than its capacity. Shrinking as soon as it is half full would be a trap: an array that alternately appends and removes one element at the boundary would resize on every operation.

Moving invalidates

A resize moves every element to a new address. In garbage-collected languages that is invisible, because the list's references are updated together. In C++, any pointer, reference or iterator into the old block becomes invalid, and using it is undefined behavior. Go has a related surprise: append may return a slice backed by a new array, so two slices that used to share elements stop sharing them after one of them grows.

The project for this level

The Foundations project asks you to build a dynamic array yourself: a fixed block, a size, a capacity, an append that doubles, and a benchmark of a million appends against your language's built-in list. The practice lab for this lesson is a good first step, because it lets you watch a real list resize.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Dynamic arrays and growth from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

def append(arr, x):
    if arr.size == arr.capacity:
        new = allocate(2 * arr.capacity)
        copy(arr.data, new, arr.size)
        free(arr.data)
        arr.data = new
    arr.data[arr.size] = x
    arr.size += 1

#include <vector>
#include <algorithm>
 
long long processArrayInvariants(std::vector<int>& nums) {
    long long acc = 0;
    int lo = 0, hi = static_cast<int>(nums.size()) - 1;
    while (lo <= hi) {
        acc += nums[lo];
        if (lo < hi) acc += nums[hi];
        ++lo; --hi;
    }
    return acc;
}

public class ArrayInvariantSolver {
    public static long processArrayInvariants(int[] nums) {
        long acc = 0;
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            acc += nums[lo];
            if (lo < hi) acc += nums[hi];
            lo++; hi--;
        }
        return acc;
    }
}

def process_array_invariants(nums: list[int]) -> int:
    acc = 0
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        acc += nums[lo]
        if lo < hi:
            acc += nums[hi]
        lo += 1
        hi -= 1
    return acc

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.