Arrays & Strings

What is an array?#

An array is the most fundamental data structure: a collection of elements stored in contiguous memory, each reachable directly by its numeric position (its index). Think of it like a row of numbered lockers bolted together in a hallway — locker #0, locker #1, locker #2, and so on. Because the lockers sit right next to each other in a fixed order, if you know a locker's number, you can walk straight to it without checking any of the others first.

That "walk straight to it" property is what makes array access so fast: the computer doesn't search for element i, it calculates its exact memory address (start_address + i * element_size) and jumps straight there.

scores = [85, 92, 78, 90, 88]
print(scores[2])  # 78 — computed directly, no searching required

Fixed-size arrays vs dynamic arrays#

In lower-level languages (like C or Java's raw arrays), an array's size is fixed at creation — you decide up front "I need room for 10 elements," and that's final. If you need an 11th slot, you have to create an entirely new, bigger array and copy everything over.

Python's built-in list (and similarly, Java's ArrayList, C++'s std::vector) is a dynamic array — it looks like it grows freely, because it manages that "create bigger, copy everything over" process automatically behind the scenes. Internally, it keeps some spare capacity so that append usually just drops the new item into an already-reserved slot — an O(1) operation. Only occasionally, when the spare capacity runs out, does it silently allocate a new, larger block (often roughly double the size) and copy every existing element into it — an O(n) operation, but one that happens rarely enough that the average cost per append still works out to O(1). (You'll see the formal name for this — amortized analysis — in the algorithms course.)

numbers = []
for i in range(5):
    numbers.append(i)   # looks free, but Python is managing capacity behind the scenes
print(numbers)  # [0, 1, 2, 3, 4]

Operations and their Big-O#

The "shifting" cost is the part that trips people up, so make it concrete. Inserting 99 at the front of [1, 2, 3, 4, 5] requires physically moving every existing element one slot to the right first:

values = [1, 2, 3, 4, 5]
values.insert(0, 99)   # every one of the 5 existing elements must shift right
print(values)          # [99, 1, 2, 3, 4, 5]  — this was an O(n) operation

Compare that to adding at the end, where nothing else needs to move:

values = [1, 2, 3, 4, 5]
values.append(99)      # nothing shifts — just fills the next free slot
print(values)           # [1, 2, 3, 4, 5, 99] — this was O(1)

This asymmetry — cheap at the end, expensive at the start or middle — is exactly the trade-off the next page (linked lists) exists to fix for the "insert/delete at the front" case.

Strings are arrays of characters#

A string is, under the hood, an array of characters — which is why so many string operations look and behave like array operations. Indexing, slicing, and iterating over a string all work the same way they do for a list:

word = "hello"
print(word[0])      # 'h' — direct index access, O(1)
print(word[1:4])    # 'ell' — a slice
for ch in word:
    print(ch)        # iterating character by character, O(n) overall

One important difference from a Python list: strings are immutable — you cannot change a character in place (word[0] = 'H' raises a TypeError). Any "modification" actually builds an entirely new string. This matters for performance: repeatedly concatenating strings in a loop (result += next_char) can silently become O(n²) overall, because each += may have to copy the entire string built so far. When you need to build up a string piece by piece, it's much better to collect the pieces in a list and join them once at the end:

# Avoid — potentially O(n^2) due to repeated copying
result = ""
for ch in "hello world":
    result += ch.upper()

# Prefer — O(n), one single join at the end
pieces = []
for ch in "hello world":
    pieces.append(ch.upper())
result = "".join(pieces)

Classic problem 1: reverse a string#

A great first exercise, because it's simple enough to trace by hand but touches the core array intuition: swap elements from the outside in.

def reverse_string(s: str) -> str:
    chars = list(s)          # strings are immutable, so work on a list of characters
    left, right = 0, len(chars) - 1

    while left < right:
        chars[left], chars[right] = chars[right], chars[left]  # swap
        left += 1
        right -= 1

    return "".join(chars)

print(reverse_string("hello"))  # "olleh"

Trace it by hand on "hello" (indices 0-4, left=0, right=4):

1. Swap chars[0] ('h') and chars[4] ('o') → ['o','e','l','l','h'], left=1, right=3
2. Swap chars[1] ('e') and chars[3] ('l') → ['o','l','l','e','h'], left=2, right=2
3. left == right, loop stops.
4. Join: "olleh".

This runs in O(n) time (one pass, each element visited once) and O(n) space (the new list of characters — Python strings can't be reversed truly "in place" since they're immutable, though a mutable array in another language could be reversed with O(1) extra space).

Classic problem 2: find the first non-repeating character#

Given a string, find the first character that doesn't repeat anywhere else in it. For example, in "swiss", 'w' is the answer — 's' repeats, and 'w' is the first character that appears exactly once.

The naive approach checks, for each character, whether it appears again anywhere else in the string — that's an O(n) scan for every character, so O(n²) overall. A much better approach counts every character's frequency first in one pass, then makes a second pass looking for the first one with a count of exactly 1:

from collections import Counter

def first_non_repeating(s: str) -> str | None:
    counts = Counter(s)              # one pass: O(n) to count every character's frequency

    for ch in s:                     # second pass: O(n) to find the first count == 1
        if counts[ch] == 1:
            return ch

    return None                      # no non-repeating character exists

print(first_non_repeating("swiss"))    # 'w'
print(first_non_repeating("aabbcc"))   # None

Trace it on "swiss":

1. Build counts: {'s': 3, 'w': 1, 'i': 1}.
2. Walk the string in order: 's' → count 3, skip. 'w' → count 1, return 'w'.

Two full passes over the string is still O(n) overall (two passes is 2n steps, and Big-O drops the constant), which is a huge improvement over the naive O(n²) approach — and it's the same trick you'll see again on the hash tables page: trade a bit of extra memory (the counts dictionary) for a large reduction in time.

Common mistakes#

• Assuming insertion is always fast. append is (amortized) O(1), but insert(0, ...) or inserting in the middle is O(n) — a very common source of surprisingly slow code when done inside a loop.
• Building strings with repeated += in a loop. Each concatenation can copy the whole string so far, silently turning an intended O(n) operation into O(n²). Collect pieces in a list and "".join(...) once instead.
• Off-by-one errors with indices, especially with slicing (arr[left:right]) or two-pointer swaps like the reverse-string example — always trace a small example by hand when in doubt.
• Forgetting strings are immutable in Python. Code that tries to do my_string[0] = 'x' will raise a TypeError — convert to a list first if you need in-place character changes.