🧩 Data Structures & Algorithms · Chapter 2

Arrays and strings

Reading item 900,000 of an array is as fast as reading item 0. Inserting a new item at the front means moving all 900,000 others. Both facts come from the same design.

Study this lesson free in the app →

The basics

An array stores items side by side in one continuous block of memory, each in a numbered slot starting at 0. A string is an array of characters.

The problem it solves: you need to keep many values and jump to any one of them instantly. Because the slots are equal-sized and contiguous, the computer finds slot i with simple arithmetic — start + i × slot_size — no searching at all.

The mental model: a row of numbered lockers in a hallway. Walking straight to locker 742 is instant. But to fit a new locker between 3 and 4, every locker from 4 onwards has to shuffle one place down the hall.

Explained

scores[900_000] — instant.

scores.insert(0, 99) on the same million-item list — every single item moves one slot to the right first.

Same data structure. One operation is O(1), the other is O(n). Knowing which is which is half of every array interview question.

Seats in a cinema row

A cinema row has 20 numbered seats and a group of friends sitting in seats 1 to 12, no gaps.

Finding your friend in seat 9 is instant — you walk straight to the number.

A latecomer wants to sit next to the friend in seat 3. Everyone from seat 4 to seat 12 has to stand up and move one seat along. Nine people disturbed for one arrival.

Someone in seat 2 leaves, and the group wants no gap — so seats 3 to 12 all shuffle back one.

And when the row is full and a 13th friend arrives? The whole group gets up and moves to an emptier row. That's exactly what a dynamic array does when it runs out of room.

Precisely

Access is arithmetic. For an array starting at memory address base with 8-byte slots, a[5] lives at base + 5 × 8. One multiplication, one addition: O(1) regardless of n.

Cost of the common operations (Python list):

| Operation | Time | | --- | --- | | a[i], a[i] = x, len(a) | O(1) | | a.append(x), a.pop() | O(1) amortised | | a.insert(i, x), a.pop(i), del a[i] | O(n − i) — shifting | | x in a, a.index(x), a.remove(x) | O(n) — linear scan | | a[i:j] | O(j − i) — a copy | | a.sort() | O(n log n) |

Strings behave like arrays for reading — s[i] is O(1), len(s) is O(1) — but in Python they are immutable. s.upper(), s.replace(...), s + t all build a brand-new string: O(length).

Searching for something that isn't there

The array is unsorted, so there is no shortcut: to prove 5 is absent, linear search must check all 8 slots. That's the true worst case of O(n). Try typing 7 instead — found on the first check, the best case.

Watch the shifting cost

Insertion sort builds a sorted prefix and inserts each new item into it — exactly an array insert. Watch the 1: it has to shift past 2, 4, 5 and 6, moving each one slot right. Every insert near the front pays for every item after it. Over n items that adds up to O(n²) in the worst case.

Everyday array and string moves

temps = [21, 19, 24, 18, 25]

temps[2]                # O(1)  -> 24
temps.append(22)        # O(1) amortised
temps.pop()             # O(1)  removes from the end
temps.insert(0, 20)     # O(n)  shifts everything right
temps.pop(0)            # O(n)  shifts everything left
24 in temps             # O(n)  linear scan
temps[1:3]              # O(k)  a new list [19, 24]

# Strings are immutable: build pieces, join once  -> O(n)
words = ["arrays", "are", "contiguous"]
sentence = " ".join(words)

# Reverse a string: slicing makes a reversed copy, O(n) time and space
"stressed"[::-1]        # 'desserts'

# Count characters with one pass: O(n) time, O(k) space
counts = {}
for ch in "banana":
    counts[ch] = counts.get(ch, 0) + 1   # {'b': 1, 'a': 3, 'n': 2}

Why append is O(1) even though copying is O(n)

A dynamic array reserves more slots than it uses. When it fills up, it allocates a bigger block (textbooks say double; CPython adds about 1/8 plus a little; Java ×1.5), copies everything over, and frees the old one.

Doubling from an empty array to 1,024 items copies 1 + 2 + 4 + … + 512 = 1,023 items in total — about one copy per append. So:

• a single append can be O(n) (the unlucky one that triggers the copy)
• n appends cost O(n) in total → O(1) amortised each

At scale, two more things matter:

• Cache locality — neighbouring slots are loaded into the CPU cache together, so scanning an array is far faster in practice than chasing pointers through a linked list with the same Big-O.
• Pre-sizing — if you know you'll hold 10 million items, allocate once ([0] * n, NumPy arrays) instead of growing repeatedly.

Gotchas

• list.pop(0) as a queue — O(n) per call; draining n items is O(n²). Use collections.deque.
• s += piece in a loop — each step may copy the whole string so far: O(n²) in the worst case. Append to a list, then ''.join once.
• Mutating a list while iterating it — removing items shifts the rest under the loop's feet, so some are skipped.
• [[0] * 3] * 2 — two references to the same inner list; changing one row changes both. Use [[0] * 3 for _ in range(2)].
• Off-by-one — the last index is len(a) - 1; slices exclude the end: a[1:3] has 2 items.
• Slices aren't free — a[1:] inside a recursive function copies on every call, turning O(n) into O(n²).

Words to know

In two minutes

• An array is a contiguous block of equal-sized slots; a[i] is computed as start + i × size, so access by index is O(1).
• Search in an unsorted array is O(n) — you may have to look at every slot, and proving something is absent always does.
• Insert or delete at position i shifts everything after it: O(n − i), so O(n) at the front and O(1) at the end.
• Dynamic arrays (Python list) over-allocate and copy when full; one append can cost O(n), but appends average O(1) — amortised.
• Strings are immutable in Python: s[0] = 'H' fails, and s += c in a loop can rebuild the string each time. Collect pieces and ''.join once — O(n).
• Slicing copies: a[i:j] is O(j − i) time and space.
• Arrays win on access speed and cache-friendliness; they lose when you insert or delete at the front or middle often.

Test yourself

There are 9 questions, 3 puzzles and 5 recall cards for this lesson in the app — the recall cards come back on later days, just before you would forget.