Arrays and Strings

1. What It Is and Why It Exists

An array is a contiguous block of memory holding elements of the same type, addressed by an integer index. Because the elements are contiguous and equal-sized, the address of element i is computed in one arithmetic step (base + i * size), which is why random access is O(1). That single property — instant indexed access — is what makes arrays the default container for almost every algorithm: two pointers, sliding window, prefix sums, sorting, and binary search all rely on cheap positional access. Without it you would be back to linked structures where reaching element i costs O(i).

A string is logically an array of characters with one twist that dominates interview answers: in Python, strings are immutable. Any "modification" (s + c, s.replace(...)) builds a new string in O(n). The classic trap is concatenating in a loop, which is O(n^2); the fix is to collect characters in a list and "".join(...) once at the end. Python's list is a dynamic array of fixed-size references, so its elements can refer to objects of different types. It resizes automatically with amortized-O(1) append: a long sequence of appends costs O(1) per append overall even though an individual resize costs O(n). The examples here use list as the array representation.

2. Operations and Complexity

Space is O(n). The operations interviewers actually probe: insert/delete in the middle is O(n) (the shift) and front operations are O(n) — knowing to switch to collections.deque for queue-like access is a frequent signal. For strings, the probe is "you concatenated in a loop — what's the complexity?" (O(n^2)).

3. Implementation

The wrapper below demonstrates O(1) indexing and the O(n) shift using a fixed-capacity Python list. Use a positive capacity, insert only at 0 <= i <= current length, and delete only at 0 <= i < current length; these two methods assume valid indices rather than checking them. This is a teaching example, not a full replacement for list.

class Array:
    def __init__(self, capacity):
        self._data = [None] * capacity   # contiguous slots
        self._n = 0
        self._cap = capacity

    def get(self, i):                    # O(1): direct address arithmetic
        if not 0 <= i < self._n:
            raise IndexError
        return self._data[i]

    def set(self, i, x):                 # O(1)
        if not 0 <= i < self._n:
            raise IndexError
        self._data[i] = x

    def insert(self, i, x):              # O(n): shift right to make a hole
        if self._n == self._cap:
            raise OverflowError
        for j in range(self._n, i, -1):  # this shift IS the O(n) cost
            self._data[j] = self._data[j - 1]
        self._data[i] = x
        self._n += 1

    def delete(self, i):                 # O(n): shift left to fill the gap
        for j in range(i, self._n - 1):
            self._data[j] = self._data[j + 1]
        self._n -= 1

In a real interview, use Python's built-in list — it is already a dynamic array with amortized-O(1) append. For string building, use a list + "".join(...), never += in a loop. Reach for collections.deque the moment you need O(1) operations at the front.

4. When to Reach for It

• You need indexed/random access or the input is already a sequence you scan by position.
• The problem screams two pointers, sliding window, or prefix sum — all require O(1) positional access.
• You need a sorted sequence for binary search (O(log n) lookups).
• You are building a string incrementally → array of chars + join.
• You need a stack (append/pop at the end are amortized O(1)) — a list is the natural stack.

5. Common Pitfalls

• String concatenation in a loop: s += c for n chars is O(n^2) (immutable rebuild each time). Fix: "".join(list_of_chars).
• list.pop(0) / list.insert(0, x) in a loop: each is O(n), so the loop is O(n^2). Fix: collections.deque (O(1) both ends), or reverse the logic to work from the back.
• Mutating a list while iterating it: skips elements or raises; iterate a copy or build a new list.
• [[0]*n]*m aliasing: all rows are the same list object; mutating one mutates all. Use [[0]*n for _ in range(m)].
• Off-by-one on bounds: range(n) vs range(n-1), inclusive vs exclusive slice ends — the most common array bug interviewers watch for.
• Forgetting slices copy: a[1:] inside a loop is a hidden O(n) per call → O(n^2).

6. Interview Cheat Sheet

• "Array gives O(1) indexed access because elements are contiguous; the cost is O(n) insert/delete in the middle due to shifting."
• "Python list is a dynamic array: append/pop at the end are amortized O(1); insert(0)/pop(0) are O(n) — I'd use deque for front operations."
• "Python strings are immutable, so I build with a list and ''.join to avoid an O(n^2) concatenation."
• "Allocating extra space is O(n); in-place rearrangement keeps it O(1) auxiliary."

Follow-ups:

• "Array vs linked list?" — Array: O(1) access, O(n) middle insert, cache-friendly. Linked list: O(n) access, O(1) insert/delete at a known node. Interviews almost always want an array unless the problem needs O(1) splicing.
• "Why is your string building O(n^2)?" — Immutable strings: each += copies the whole prefix. Use a list and join → O(n).
• "How do you delete from the middle in O(1)?" — You can't preserve order in O(1); if order doesn't matter, swap the target with the last element and pop() (O(1)).