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 in memory. Each locker is the same size. The lockers are in order, side by side. Thus the computer does not search for locker #47. The computer calculates the address directly: base address + 47 × (size of one locker). This is one multiplication and one addition. This is why a read of arr[47] has the same cost for an array of 100 elements or 100 million elements. A linked list (Phase 2) is different. In a linked list, each node tells you only where the next node is. To reach the 47th node, you must go through 46 nodes first. An array has a strict rule: each element must be the same size and must be in one continuous block. In exchange, an array gives you immediate access to any position.
A string is an array of characters. It uses the same continuous block and the same index-to-address calculation. But many languages make strings immutable. In Python, Java, and JavaScript, you cannot change a string value after you create it. When you "edit" a string, you do not change the original locker row. The computer builds a completely new string and points your variable at the new string. This is not important when you do it one time. This is very important when it happens inside a loop.
Structures
structure Array:
data // one continuous block of memory, one slot for each index
length // the number of slots that hold real elements now
capacity // the number of slots that are allocated (>= length)
// address(i) = base_address + i * element_size
// This is only arithmetic, with no search. 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 calculation and one memory access
function writeAt(arr, i, value):
arr.data[i] = value // the same arithmetic, but a write instead of a readappend — O(1) amortized
function append(arr, value):
if arr.length == arr.capacity: // there is no more room in the current block
newCapacity = arr.capacity * 2 // multiply the capacity by two, do not add one slot
newData = allocate(newCapacity)
copy arr.data into newData // O(n) — the computer must move each element
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):
// Each element from i to the end must move one slot to the right to make a gap.
// You cannot make room without a physical move of these elements.
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):
// This is the opposite: each element after i moves one slot to the 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: this looks like one simple loop, but each += builds a completely new string.
function buildNaive(words):
result = ""
for w in words:
result = result + w // This copies the full result each time.
return result
// Buffer: collect the pieces in a resizable array (append is O(1) amortized, see above).
// Then build the real string one time at the end.
function buildWithBuffer(words):
buffer = []
for w in words:
buffer.append(w) // O(1) amortized for each piece
return join(buffer) // one O(n) pass over the total output lengthTwo questions decide the cost. First, is the position of the work fixed (an index that you already know)? Second, does the work depend on a search through other elements or a move of other elements? Fixed-position work is O(1). Work that must look at or move other elements increases with n.
| Operation | Time | Space | Why |
|---|---|---|---|
| Index read / write | O(1) | O(1) | This is only address arithmetic. It does not depend on the number of other elements in the array. |
| Append (at the end) | O(1) amortized | O(1) amortized | This is usually a direct write. The occasional O(n) resize-and-copy is spread over enough earlier appends. The average stays O(1). |
| Insert / delete at an arbitrary index | O(n) | O(1) | Each element after the target index must move one slot to open or close the gap. The worst case (index 0) moves almost the full array. |
| Unsorted search (find a value) | O(n) | O(1) | There is no shortcut to the position of a value. The computer checks the elements one at a time until it finds the value or reaches the end. |
| String concatenation, naive (in a loop) | O(n²) total | O(n²) total allocated | Each += copies all the content so far, because strings are immutable. n concatenations copy approximately 1 + 2 + ... + n characters. |
| String concatenation, via buffer | O(n) total | O(n) | To collect the pieces in a resizable array costs O(1) amortized for each piece. To join one time at the end is one O(n) pass. |
Empty array
arr[0] on an empty array is not "the first element". There is no first element. A read, a search, or a loop over an empty array must be a valid operation with no effect, not a crash. Code that assumes "there is always at least one element" fails 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. A loop condition such as i <= length is a common error. Manual boundary math is also a common error, for example a midpoint, a window edge, or a last-common-index check like in Longest Common Prefix. These errors make an out-of-bounds read or write exactly one position past the real end.
Mutating an immutable string in place
In languages with immutable strings, a statement such as s[0] = 'x' makes an error or does nothing useful. There is no "in place" operation. Each apparent edit makes a new string object. Code that assumes a string is a mutable character array (like an array) crashes or continues to use an old copy.
Modifying an array while iterating over it
If you delete index i while the loop cursor is also at i, each later element moves down one slot. The next step of the loop then skips the element that moved into the position it just left. The loop misses an element with no error. The safe method is to iterate backward when you delete, or to build a new array of the elements to keep instead of a change during the walk.
Sign in to mark problems done — progress syncs across devices.