Arrays in memory (and why strings bite)
Arrays are the substrate of almost everything else, and most "array tricks" make sense only once you see what an array physically is: one contiguous block of memory.
Why contiguity matters
Because element i lives at a predictable address, indexing is O(1) — the CPU computes the address with one multiplication. This is the superpower. Everything else about arrays is a consequence.
The cost table you must know cold
| Operation | Complexity | Why |
|---|---|---|
| Read / write by index | O(1) | Address arithmetic |
| Append at end | O(1) amortized | Occasionally doubles and copies |
| Insert / delete at front or middle | O(n) | Every later element must shift |
| Search unsorted | O(n) | Must check each element |
| Search sorted | O(log n) | Binary search |
Consequence 1: never delete from the middle in a loop
Deleting arr[i] shifts everything after it. Doing that inside a loop is an accidental O(n²). The pattern to avoid it: overwrite-and-shrink (write survivors forward with a write pointer — this is the two-pointer pattern, next section).
Consequence 2: strings are arrays with a twist
In Python and Java, strings are immutable arrays of characters. Every s += char in a loop copies the whole string — an accidental O(n²). Build a list of parts and join once:
# BAD: O(n^2) — each += copies the whole string
out = ""
for ch in s:
out += transform(ch)
# GOOD: O(n)
parts = []
for ch in s:
parts.append(transform(ch))
out = "".join(parts)Interviewers deliberately pick problems where naive array/string handling is O(n²) and the intended answer is O(n). If your solution shifts, copies, or re-scans inside a loop, pause and look for a pattern.