Arrays & Strings Fundamentals
Quick reference
| Index read / write | O(1) |
| Append (at the end) | O(1) amortized |
| Insert / delete at an arbitrary index | O(n) |
| Unsorted search (find a value) | O(n) |
| String concatenation, naive (in a loop) | O(n²) total |
| String concatenation, via buffer | O(n) total |
An array is a row of numbered lockers sitting side by side in memory, each one exactly the same size. Because every locker is the same size and they're all lined up in order, the computer never has to search for locker #47 — it computes the address directly: base address + 47 × (size of one locker). That single multiplication and addition is why reading arr[47] costs the same whether the array has 100 elements or 100 million. Contrast that with the Linked List (Phase 2): a linked list is a scavenger hunt where each stop only tells you where the next one is, so reaching the 47th node means walking through 46 stops first. Arrays trade that walk for a strict requirement — every element has to be the same size and sit in one contiguous block — in exchange for instant jump-to-anywhere access.
A string is, underneath, an array of characters — same contiguous block, same index-to-address arithmetic. But strings carry a wrinkle many languages bake in: immutability. In Python, Java, and JavaScript, a string value can't be changed in place once created — "editing" a string by appending or replacing a character doesn't modify the original locker row, it builds an entirely new one and points your variable at that instead. That's invisible when you write it once; it matters a lot the moment it happens inside a loop.
Structures
structure Array:
data // one contiguous block of memory, one slot per index
length // how many slots currently hold real elements
capacity // how many slots are actually allocated (>= length)
// address(i) = base_address + i * element_size
// pure arithmetic, no searching — this formula is WHY index access is O(1)read / write by index — O(1)
function readAt(arr, i):
return arr.data[i] // one address computation, one memory access
function writeAt(arr, i, value):
arr.data[i] = value // same arithmetic, just a write instead of a readappend — O(1) amortized
function append(arr, value):
if arr.length == arr.capacity: // no room left in the current block
newCapacity = arr.capacity * 2 // double it, don't just add one slot
newData = allocate(newCapacity)
copy arr.data into newData // O(n) — every existing element must move
arr.data = newData
arr.capacity = newCapacity
arr.data[arr.length] = value
arr.length += 1insert / delete at an arbitrary index — O(n)
function insertAt(arr, i, value):
// everything from i onward has to slide one slot right first, to open a gap —
// there's no way to make room without physically moving them
for j from arr.length down to i + 1:
arr.data[j] = arr.data[j - 1]
arr.data[i] = value
arr.length += 1
function deleteAt(arr, i):
// mirror image: everything after i slides one slot left to close the gap
for j from i to arr.length - 2:
arr.data[j] = arr.data[j + 1]
arr.length -= 1building a string — naive concatenation vs. a buffer
// naive: looks like one simple loop, but each += silently builds an entire NEW string
function buildNaive(words):
result = ""
for w in words:
result = result + w // copies the ENTIRE result so far, every single time
return result
// buffer: collect pieces in a resizable array (append is O(1) amortized, see above),
// then pay for exactly one real string-build at the very end
function buildWithBuffer(words):
buffer = []
for w in words:
buffer.append(w) // O(1) amortized per piece
return join(buffer) // one O(n) pass over the total output lengthTwo questions decide the cost: is the position of the work fixed (an index you already know) or does it depend on searching through or shifting other elements? Fixed-position work is O(1); anything that has to look at or move other elements scales with n.
| Operation | Time | Space | Why |
|---|---|---|---|
| Index read / write | O(1) | O(1) | Pure address arithmetic — no dependence on how many elements exist elsewhere in the array. |
| Append (at the end) | O(1) amortized | O(1) amortized | Usually a direct write. The occasional O(n) resize-and-copy is spread across enough prior appends that the average stays O(1). |
| Insert / delete at an arbitrary index | O(n) | O(1) | Every element after the target index has to shift one slot to open or close the gap — worst case (index 0) shifts almost the whole array. |
| Unsorted search (find a value) | O(n) | O(1) | No shortcut to a value's position — elements are checked one at a time until found or exhausted. |
| String concatenation, naive (in a loop) | O(n²) total | O(n²) total allocated | Each += copies everything accumulated so far because strings are immutable — n concatenations copy roughly 1 + 2 + ... + n characters. |
| String concatenation, via buffer | O(n) total | O(n) | Collecting pieces in a resizable array costs O(1) amortized per piece; joining once at the end is a single O(n) pass. |
Empty array
arr[0] on an empty array isn't "the first element, whatever that is" — there is no first element. Reading, searching, or looping over an empty array has to be a valid no-op, not a crash; code that assumes "there's always at least one element" breaks on the smallest legal input.
Off-by-one at the boundary
The last valid index of an array with length n is n − 1, not n. Loop conditions like i <= length, or hand-written boundary math (a midpoint, a window edge, a last-common-index check like in Longest Common Prefix), are the classic source of an out-of-bounds read or write exactly one past the real end.
Mutating an immutable string in place
In languages where strings are immutable, something like s[0] = 'x' either throws an error or silently does nothing useful, because there is no "in place" — every apparent edit produces a new string object. Code that assumes a string behaves like a mutable character array (as arrays do) either crashes or quietly keeps operating on a stale copy.
Modifying an array while iterating over it
Deleting index i while a loop's cursor is also at i shifts every later element down one slot — the loop's next step then skips whatever slid into the spot it just left, silently missing an element. The safe pattern is to iterate backward when deleting, or build a fresh array of what should remain instead of mutating mid-walk.
Sign in to mark problems done — progress syncs across devices.