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 — it resizes automatically with amortized-O(1) append — so "array" in a Python interview means list.

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

A fixed-capacity array with O(1) indexing and the O(n) shift made explicit:

Copy
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 end are 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)).