Arrays & Sequences

Why arrays come first

Every later module in this curriculum (linked lists, strings, hash maps, trees, graphs, dynamic programming) is, at some level, stored in an array. A string is an array of characters. A hash table is an array of buckets. A heap is an array pretending to be a tree. When you call arr[i] you are doing the same thing a compiler does when it accesses a struct field: you are offsetting from a base pointer. Getting comfortable with that single fact unlocks a surprising amount of what follows.

Most introductions present arrays as lists of items. That framing obscures the part that matters. Arrays are geometry: a rectangle of memory, cut into equal-sized slots, with a start address and a length. The consequences of that geometry fall out of the picture, not out of a table you have to memorise: indexing is O(1), appending at the end is amortised O(1), and inserting in the middle is O(n) because every later element must shift.

The core mental model

Imagine a row of identical parking spaces, numbered from 0. Each space is exactly the same size. To find space number 47, you don't drive past spaces 0 through 46; you know where space 0 is, you know each space is 8 metres wide, and you multiply. That's an array. The "list of items" metaphor makes arrays feel like pedestrians walking in line. The parking-lot metaphor makes the O(1) random access feel obvious, because in a parking lot, of course you drive straight to the spot.

Now notice what's expensive. If a new car wants to park in space 5 and every car after it must shift one space to the right, you have 42 cars to move. That's an O(n) insertion. Removing space 5 and closing the gap? Also 42 cars to move. Anything that disturbs the contiguous-memory contract pays linearly for the privilege.

Implementation & indexing arithmetic

In a language like C, an array is literally a pointer plus a length. Indexing is:

// Accessing a[i] compiles to one instruction on most CPUs
int a[N];
int value = a[i];   // *(a + i * sizeof(int))

In Python, JavaScript, or Java, the same idea is wrapped in a class (list, Array, ArrayList), and the underlying storage is a resizing buffer. When the buffer fills, the runtime allocates a buffer twice as large, copies the existing elements across, and frees the old one. That's why appending is amortised O(1): most appends are instant, but occasionally one append pays O(n) for the resize. Averaged over many appends, each costs a constant.

The three patterns you must own

Most array problems collapse into one of three shapes. Once you can name the shape, the solution is usually within reach.

Prefix sums

If you precompute P[i] = a[0] + a[1] + ... + a[i-1], then the sum of any subarray a[l..r) becomes P[r] - P[l]. One O(n) pass buys you unlimited O(1) range-sum queries. The same idea generalises: prefix XORs for XOR ranges, prefix counts for "how many vowels between index 3 and 17", prefix maxima for streaming window problems.

def prefix_sum(a):
    # P[i] = sum of a[0..i-1]; P[0] = 0 by convention.
    P = [0] * (len(a) + 1)
    for i, x in enumerate(a):
        P[i + 1] = P[i] + x
    return P

def range_sum(P, l, r):   # sum of a[l..r)
    return P[r] - P[l]

Why the off-by-one zero at P[0]? Because it makes the query symmetric: P[r] - P[l] works for any valid l <= r, including l = 0. Without the sentinel, you'd need a special case.

Two pointers

The pattern for sorted arrays and palindrome-shaped problems. You place one index at each end and move them toward each other, deciding at each step which one to advance. The classic example is the two-sum on sorted input: find indices i, j with a[i] + a[j] == target. If the sum is too small, advance the left pointer; if too large, retreat the right pointer. Each step eliminates one pair from consideration, so the algorithm runs in O(n).

def two_sum_sorted(a, target):
    i, j = 0, len(a) - 1
    while i < j:
        s = a[i] + a[j]
        if s == target: return (i, j)
        if s < target:  i += 1    # need a larger sum
        else:           j -= 1    # need a smaller sum
    return None

The full treatment, including fast/slow pointers on unsorted arrays and the "partition" pattern used inside quicksort, is in Module 09.

Sliding window

A special case of two pointers in which both indices move forward, never backward. You maintain a running summary (sum, product, maximum, character frequency) for the window [l, r), expand the window to the right, and contract from the left when a constraint is violated. This is how you find "the longest substring with at most k distinct characters" in O(n) rather than O(n·k·len).

def longest_subarray_leq_k_distinct(a, k):
    from collections import Counter
    freq = Counter()
    l = best = 0
    for r, x in enumerate(a):
        freq[x] += 1
        while len(freq) > k:          # contract until valid
            freq[a[l]] -= 1
            if freq[a[l]] == 0: del freq[a[l]]
            l += 1
        best = max(best, r - l + 1)
    return best

Complexity analysis, reasoned not recited

Why is indexing O(1) and insertion at position i O(n − i)? Because the hardware is the constraint. The CPU can compute an offset and fetch a word in a single cycle. But shifting n − i elements one slot to the right requires n − i writes, so the instruction count grows with the number of elements affected. You cannot "insert in the middle in constant time" on a true contiguous array, no matter how clever you are, because the definition of contiguity is what makes O(1) access possible in the first place. If you need mid-sequence insertion in O(1), you are looking for a linked list, which is a different trade-off entirely.

The amortised analysis of dynamic array append deserves one more sentence. A doubling strategy guarantees that of any n appends, the total work is bounded by n + n/2 + n/4 + ... < 2n, so the average per append is constant. Halving on removal, if you halve only when the array is one-quarter full, preserves the amortised bound. Halving on reaching half-full does not: it creates a pathological resize/grow cycle. That subtlety costs production systems real performance; it's not a trick question.

When to reach for an array, and when not to

Reach for an array when random access dominates your workload, when the sequence is append-heavy rather than middle-insert heavy, and when cache friendliness matters (contiguous memory is the CPU's favourite shape). Avoid arrays when you need O(1) insertion at arbitrary positions, when the sequence length varies wildly and frequently, or when you need O(1) membership testing. That's what hash sets are for.

Where beginners go wrong

• Off-by-one in prefix sums. The P[0] = 0 sentinel is not optional. Drop it and half of your range queries will silently include or exclude one endpoint.
• Mutating the list while iterating. for x in a: a.remove(x) will skip elements, because the index advances while you shift the backing storage underneath it. Build a new list instead, or iterate backward.
• Confusing amortised with worst-case. Amortised O(1) append does not mean this particular append is O(1). If you are writing a real-time system with a hard latency budget, a resize could miss your deadline.
• Assuming two pointers works on unsorted input. The correctness of the "advance smaller, retreat larger" rule depends on sortedness. On unsorted arrays, the same pattern finds a different answer, or no answer at all.

What to read next

The next module, Linked Lists, is arrays' opposite number. Where arrays trade mid-sequence insertion for O(1) access, linked lists make the reverse trade. Reading them back-to-back is the fastest way to internalise why each exists.

If you would rather go deep than wide, the companion concept page, Sliding Window in Depth, walks through three problems of increasing difficulty with full complexity proofs.