Arrays and Strings: Indexing, Operations & Complexity

An array stores elements in one contiguous block of memory, and a string is essentially an array of characters. That layout is what makes index access instant: the computer can jump straight to position $i$ without scanning anything before it.

The trade-off is rigidity. Reading by index costs $O(1)$, but inserting or deleting in the middle costs $O(n)$, because every later element has to shift. Most array and string problems come down to managing that trade-off.

How array indexing works

Arrays are zero-based in most languages: the first element lives at index $0$ and the last at index $n - 1$ for an array of length $n$. Access is constant time because the address of any element is a direct calculation:

No loop is needed, which is why arr[500000] is exactly as fast as arr[0].

For the array $[8, 3, 5, 1]$:

Complexity of common operations

The middle-insert cost is the one students underestimate. Deleting index $0$ from a million-element array touches all $999{,}999$ remaining elements, because each one slides left by a single slot.

Strings are arrays with one extra rule

In many languages — Python, Java, JavaScript — strings are immutable: you cannot change a character in place. Every "modification" actually builds a new string.

That makes one pattern dangerously slow. Concatenating inside a loop copies the whole string each time:

s = ""
for ch in data:   # O(n^2) total
    s += ch

Each += copies everything built so far, so the total work is

The fix is to collect pieces in a list and join once at the end ("".join(parts) in Python), which is $O(n)$.

Worked example: reverse an array in place

Put one pointer at each end, swap, and move inward:

def reverse(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

Trace on $[4, 9, 2, 7, 5]$:

Each element is touched once, so the reversal runs in $O(n)$ time with $O(1)$ extra space. This two-pointer pattern reappears constantly in array and string problems.

Worked example: check if two strings are anagrams

Two strings are anagrams if they use the same characters with the same counts. Count characters from one string, then subtract with the other:

def is_anagram(a, b):
    if len(a) != len(b):
        return False
    counts = {}
    for ch in a:
        counts[ch] = counts.get(ch, 0) + 1
    for ch in b:
        counts[ch] = counts.get(ch, 0) - 1
        if counts[ch] < 0:
            return False
    return True

For a = "listen" and b = "silent", every count returns to zero, so the function returns True. This runs in $O(n)$ — better than sorting both strings first, which would cost $O(n \log n)$.

Common mistakes

Off-by-one errors

The last valid index is $n - 1$, not $n$. A loop written as while i <= len(arr) reads one element past the end and crashes — or worse, silently reads garbage in low-level languages.

Concatenating strings in a loop

As shown above, repeated += on an immutable string is $O(n^2)$. Collect parts in a list and join once, or use a string builder.

Modifying an array while iterating forward

Deleting elements during a forward loop shifts the remaining ones, so the loop skips the neighbor of every removed element. Iterate backwards or build a new array instead.

Confusing length with last index

len(arr) is the count of elements; len(arr) - 1 is the last position. Mixing the two is the single most common cause of index-out-of-range errors.

Where this takes you next

Arrays are the backbone of nearly everything else: hash tables keep their buckets in arrays, sorting algorithms permute arrays, and binary search depends on $O(1)$ index access to jump to the middle of a range. Once you can predict the cost of an array operation before running it, the data structures built on top of arrays become far easier to reason about.