The idea: a numbered row of boxes
Picture a row of identical boxes lined up with no gaps, numbered 0, 1, 2, and so on. Each box holds one value, and you refer to any value by its box number — its index. That is an array. The crucial detail is that the boxes are contiguous: they occupy one unbroken block of memory, one right after another.
Because the boxes are the same size and sit next to each other, the computer never has to search for element i. It computes the location directly: base address + i × element size. That single multiply-and-add is why arrays feel instant — there is no walking through earlier elements to reach a later one.
The mechanics: why access is O(1) and edits are O(n)
Reading or overwriting arr[i] is O(1) — constant time — no matter how large the array is, thanks to that address formula. This is the array's superpower and the reason it underpins almost every other data structure.
The cost appears when you change the array's shape. Insert a value at the front and every existing element must slide one slot right to make room — O(n) work. Delete from the middle and everything after the gap slides left to close it. Appending to the end is the happy exception: usually O(1), though dynamic arrays occasionally pay for a resize.
A fixed-size array (C arrays, Java's int[]) has its length set at creation. Dynamic arrays — Python's list, JavaScript's Array, C++'s std::vector — grow by allocating a bigger block and copying the elements over. That copy makes an occasional append O(n), but amortized over many appends it averages out to O(1).
Why arrays are the base of most problems
Most higher-level structures are arrays underneath. Hash tables use an array of buckets, heaps are arrays interpreted as trees, strings are arrays of characters, and matrices are arrays of arrays. Learning to reason about indices, bounds, and shifting carries directly into all of them.
Arrays also unlock a whole family of techniques that assume O(1) indexed access and a cache-friendly contiguous layout: binary search, two pointers, sliding window, and prefix sums all live on arrays. Master the array and a large slice of interview problems suddenly share one foundation. Watching the indices shift step by step makes the O(n) cost obvious in a way a paragraph cannot.
class DynamicArray:
def __init__(self):
self._data = [None] # fixed-size backing block
self._size = 0 # slots actually used
def get(self, i): # O(1) — direct index
if not 0 <= i < self._size:
raise IndexError(i)
return self._data[i]
def append(self, value): # O(1) amortized
if self._size == len(self._data):
self._resize(2 * len(self._data)) # double + copy: O(n)
self._data[self._size] = value
self._size += 1
def insert(self, i, value): # O(n) — shift right to open a gap
if self._size == len(self._data):
self._resize(2 * len(self._data))
for j in range(self._size, i, -1):
self._data[j] = self._data[j - 1]
self._data[i] = value
self._size += 1
def _resize(self, capacity):
self._data = self._data[:self._size] + [None] * (capacity - self._size)Best/fast paths are index access and end-append (O(1)). The worst case for inserting or deleting is O(n) because elements must shift. Dynamic-array appends are O(1) amortized but O(n) on the occasional resize that doubles capacity.
When to use it
- You need fast random access by position — reading, updating, or repeatedly scanning elements many times.
- The data is a sequence you mostly append to or iterate over, and you rarely insert or delete in the middle.
- You want compact, cache-friendly storage: a contiguous layout makes iteration genuinely fast in practice, not just on paper.
- You are applying an array-based technique such as binary search, two pointers, sliding window, or prefix sums.
Watch out for
- Off-by-one and out-of-bounds errors: valid indices run 0 to n-1. Looping while i <= n, or forgetting the array can be empty, is the classic array bug.
- Repeatedly inserting or deleting in the middle inside a loop and being surprised it is slow — each such edit is O(n), so doing it n times is O(n^2). Rebuild the array in one pass or pick a different structure.
- Assuming append is always O(1). It is O(1) amortized; an individual append can trigger an O(n) resize, which matters for tight-latency or real-time code.
Arrays are the single most common substrate in coding interviews — the majority of easy and medium problems hand you an array and ask you to search, transform, or find something within it. Interviewers rarely test whether you know what an array is; they watch how you use one. Can you avoid an O(n^2) brute force by scanning once with two pointers, a hash map, or a running total? Do you handle the empty and single-element cases, keep every index in bounds, and state the time and space complexity of your approach out loud? Cleanly modifying an array in place, without allocating extra space, is a frequent bar-raiser.