Lesson 1 of 8

How Arrays Work

"Bad programmers worry about the code. Good programmers worry about data structures and their relationships." — Linus Torvalds

Everything in this Volume — every list, stack, queue, heap, and hash table — is built, at some layer, on top of the array. It is the oldest data structure we have and still the most important, because it is the one that maps most directly onto how a computer actually stores things: a straight run of memory, one cell after another. Understand what that contiguous layout gives you and what it costs you, and half of data-structures reasoning falls out for free. Misunderstand it — assume every operation is cheap because the syntax is short — and you will write O(n²) code that looks innocent. This chapter is the free preview of Part II for exactly that reason: arrays are where intuition about performance is won or lost.

The question this chapter answers

Why is reading arr[9999] just as fast as reading arr[0], while inserting at the front of that same array is painfully slow — and how do you know which array operations are the traps?

Core Concepts

An array is a contiguous block of memory

Strip away the language and an array is one idea: a single, unbroken block of memory divided into equal-sized cells, laid end to end. If an array of 32-bit integers starts at memory address 1000, then element 0 lives at 1000, element 1 at 1004, element 2 at 1008, and so on — each cell four bytes wide, no gaps.

index:     0      1      2      3      4
         ┌──────┬──────┬──────┬──────┬──────┐
memory:  │  10  │  20  │  30  │  40  │  50  │
         └──────┴──────┴──────┴──────┴──────┘
addr:    1000   1004   1008   1012   1016

That layout is the whole source of the array's superpower. To find element i, the computer does not walk the array looking for it. It does one piece of arithmetic:

address = base + index × elementSize

To reach element 3: 1000 + 3 × 4 = 1012. One multiply, one add, one memory fetch — and it costs exactly the same whether index is 3 or 3,000,000. This is why index access is O(1): it is a calculation, not a search. No other data structure gives you that for a positional lookup, and it is the reason arrays underpin nearly everything else.

Everyday analogy

Think of a street of identical houses, numbered from a known corner. To visit house 47 you don't knock on 1, then 2, then 3 — you know each plot is the same width, so you compute where 47 must be and walk straight there. That's base + index × width. Now imagine a new family wants to move into house 1 and keep the numbering tidy: every other family has to shift one house down the street. That's the cost of inserting at the front — and no amount of cleverness removes it, because the houses are physically in a row.

Static arrays vs dynamic arrays

A static array (the C-style int[10]) has a fixed size chosen when it's created. The block is allocated once and never grows. Fast and predictable, but if you need an eleventh element you're out of luck.

The arrays you actually use every day are dynamic arrays: JavaScript's Array, Python's list, C++'s vector, Java's ArrayList. They feel like they grow on demand — but underneath, memory is still contiguous and still fixed-size. The trick is what happens when you fill it up. The dynamic array quietly holds a bigger block than it needs (its capacity), and when a push would overflow that capacity, it allocates a new, larger block (typically double the size), copies every existing element across, and frees the old one.

That copy is O(n) — so how can we call push cheap? Because the expensive resizes are rare and get rarer as the array grows. Averaged over a long run of pushes, the total copying work is linear in the number of pushes, so each one is amortized O(1). That is precisely the argument we built in the Amortized Analysis chapter — arrays are its headline example.

Deriving the cost of every array operation

Once you hold "contiguous memory" in your head, the complexity of each operation is not something to memorise — you can derive it. Index access is arithmetic. Anything that changes the array's shape near the front or middle must physically shift the elements after it. Here is the whole table, with the reason attached:

Operation	Time	Why
Read / write `arr[i]`	`O(1)`	address = base + i × size — pure arithmetic
Push (add at end)	Amortized `O(1)`	usually just a write; occasional resize + copy
Pop (remove at end)	`O(1)`	drop the last cell; nothing shifts
Unshift (add at front)	`O(n)`	every existing element shifts one slot right
Shift (remove at front)	`O(n)`	every remaining element shifts one slot left
Insert / delete in middle	`O(n)`	every element after the point shifts
Search by value	`O(n)`	no address to compute — you must scan

The line that surprises people is search. Access by index is O(1), but access by value ("is 42 in here, and where?") is O(n), because a value gives you no address to jump to — you have no choice but to look at each cell. That asymmetry is why the next Volumes reach for hash maps and trees the moment lookup-by-value becomes hot.

Let's see the front-vs-end difference by counting the actual element moves each one forces:

JavaScript — Try it Yourself

Loading editor…

Console

Runs automatically. Edit the code to see it change.

Five elements, five shifts to insert at the front; zero to append at the end. Scale that to a million-element array and the front insert copies a million values every single time — the difference between a program that scales and one that melts.

The engineer's notebook

What experienced engineers actually do with array costs:

• They append, never prepend, in hot loops. Building a list? push and, if you need it reversed, reverse once at the end (O(n)) rather than unshift in the loop (O(n²)).
• They never use an array as a queue via push + shift. Every shift is O(n); a million dequeues is O(n²). Reach for a real queue or two-pointer trick instead.
• They preallocate when the size is known. new Array(n) or filling to a known length avoids repeated resize-and-copy churn.
• They keep arrays dense and single-typed — for reasons the next section makes clear.

JavaScript arrays: an honest footnote

Everything above is the textbook array, and it is exactly how a C array or a typed array behaves. A plain JavaScript Array is a little more slippery, and you should know the truth. Under the hood, modern engines (V8, SpiderMonkey) will store an array as a genuine contiguous block only while it stays "dense" and integer-keyed — no holes, ideally one element type. The moment you make it sparse (arr[0] = 1; arr[9999] = 2) or mix in non-index keys (arr.foo = 'x'), the engine can quietly deoptimise it into a hash-map-backed dictionary, and your beautiful O(1) index access loses its guarantee along with a lot of speed.

The practical rule is simple: keep arrays dense and contiguous. Fill them in order, avoid leaving holes, don't hang random properties off them, and prefer a single element type. Do that and you get the real contiguous array with all its complexity guarantees intact. (For number-crunching where you want a guaranteed contiguous block, that's what Int32Array / Float64Array and the other typed arrays are for.)

Multi-dimensional arrays and row-major layout

A matrix, a game board, an image — these are 2D data, but memory is stubbornly 1D. So a 2D array is really a 1D block with an addressing convention laid over it. In JavaScript a 2D array is literally an array of row-arrays, and you index it grid[row][col] — row first, then column. (Getting that order backwards is the single most common 2D bug.) Iterating the whole grid is two nested loops, so it costs O(rows × cols) — linear in the number of cells, which is what you'd expect: you touch each cell once.

JavaScript — Try it Yourself

Loading editor…

Console

Runs automatically. Edit the code to see it change.

History changed here

The array is nearly as old as programming itself. When John Backus's team shipped FORTRAN in 1957 — the first widely used high-level language — its headline feature was the array with subscript notation, so scientists could write A(I) instead of hand-computing memory addresses. That single abstraction, index instead of address, is why we can say arr[i] today without thinking about base + i × size at all. Nearly seventy years later every language you touch inherited it, unchanged in spirit.

The built-in methods that quietly cost O(n)

The most expensive mistake in array code isn't a wrong algorithm — it's assuming a one-line built-in is cheap because it's short. It isn't. Every method that touches all the elements is at least O(n), and calling one inside a loop over the same data is how O(n²) sneaks in disguised as clean code:

Method	Time	Note
`map`, `filter`, `reduce`, `forEach`	`O(n)`	visits every element once
`slice(a, b)`	`O(n)`	copies the selected range into a new array
`splice(i, …)`	`O(n)`	inserts/removes then shifts the tail
`indexOf`, `includes`, `find`, `some`	`O(n)`	a linear scan — no free lookups
`concat`, `join`, `reverse`	`O(n)`	touches every element
`sort`	`O(n log n)`	the good comparison-sort bound

Read includes and indexOf twice. arr.includes(x) looks like a hash-map membership test but it is a full linear scan. Put it inside a loop over the array and you have written O(n²) — the exact trap the Big-O chapter warned about, now wearing a friendly method name.

Real-world example — chika.ng Academy

The Academy holds a lesson's content as an ordered array of "blocks" (prose, code, quiz). Rendering the lesson is a single map over that array — O(n), and appropriate. The trap appears in the editor: an early version checked "is this block already selected?" with selectedIds.includes(block.id) inside the map over every block — an O(n²) scan that was invisible on a 5-block lesson and janky on a 200-block one. The fix was one line: turn selectedIds into a Set and use .has() for O(1) membership, dropping the whole render back to O(n). Same feature, same output, a different data structure underneath.

Common Mistakes

Using shift/unshift in a loop. They're O(n) each, so a loop of them is O(n²). Append with push and reverse once, or use a proper queue. This is the number-one hidden quadratic in array code.
Assuming includes/indexOf are cheap. They're linear scans. Needing repeated membership checks is a signal to switch to a Set or Map, not to keep scanning the array.
Confusing index access with value search. arr[i] is O(1); "find the item equal to x" is O(n). They are not the same operation, and only one is free.
Forgetting splice shifts. splice isn't just insert/delete — removing element i from the middle forces every later element to move, so it's O(n), not O(1).
Off-by-one in 2D indexing. Writing grid[col][row] instead of grid[row][col], or looping c < rows. State the dimensions out loud before you write the loops.
Creating sparse arrays by accident. Assigning to a far-off index (arr[10000] = x on a short array) or deleting with delete arr[i] leaves holes that can deoptimise the array. Keep it dense.

Thought experiment

You need to reverse a 1,000,000-element array. Approach A: loop through the source and unshift each element onto a new array. Approach B: loop through the source and push each element onto a new array, then don't even bother — just call reverse(). Approach A feels equivalent, but every unshift is O(n), so a million of them is O(n²) — roughly a trillion element moves. Approach B is O(n). Same reversed array; one finishes instantly, the other never does. The lesson isn't "reverse is special" — it's that where you touch a contiguous array decides everything.

Interview Corner

Interview Corner — the same idea at three levels. Answer yours; recognise the one above it.

Junior

"What's the time complexity of accessing an element in an array by its index, and why?"

Model answer — "It's O(1). An array is a contiguous block of memory with equal-sized cells, so the machine computes the address directly — base + index × elementSize — and jumps straight there. It's arithmetic, not a search, so it costs the same for index 0 or index a million."

Follow-up they'll throw: "And finding an element by its value?" → O(n). A value gives you no address to compute, so you have to scan cell by cell.

Intermediate

"Why is push considered O(1) but unshift is O(n)? They're both 'add one element.'"

Model answer — "Because of where they add. push writes to the end — usually a free slot in the array's spare capacity, so O(1); occasionally the block is full and it must allocate a bigger one and copy everything, but that resize is rare enough to average out to amortized O(1). unshift adds at the front, which means every existing element has to shift one slot right to make room — that's unavoidably O(n) because the memory is contiguous."

Follow-up: "What about splice to insert in the middle?" → O(n) too — everything after the insertion point shifts.

Senior

"A background job builds a work queue with a JS array — push to enqueue, shift to dequeue — and it's grinding to a halt as volume grows. Diagnose and fix it."

Model answer — "shift is the smell. Every dequeue removes from the front, which shifts all remaining elements left — O(n) per dequeue, so draining n items is O(n²). That's the quadratic melting it. The cheapest fix keeps the array but stops shifting: track a head index and just advance it on dequeue (O(1)), compacting occasionally. Cleaner still is a purpose-built structure — a linked-list queue or a circular buffer — giving true O(1) enqueue and dequeue. I'd pick based on whether the queue is bounded and whether I need it to shrink."

The senior move: name the exact operation causing the quadratic, then show you know the array can be salvaged and when to reach past it for the right structure entirely.

Company lens — how the same topic gets asked

micro1Live and conversational — the AI interviewer wants you to narrate the memory model. Say "contiguous block, so index is address arithmetic" out loud; state each operation's complexity as you touch it.

GoogleWants rigor: derive the amortized O(1) for push from the doubling-and-copying argument, and be ready to distinguish worst-case from amortized per operation.

MetaSpeed and clean code on the classic patterns — in-place two-pointer array manipulation, avoiding needless slice/splice copies. They watch for the hidden O(n²) from a scan inside a loop.

AmazonOperational lens: "what happens at 100× volume?" Tie shift-in-a-loop to a real outage, and frame the fix in terms of throughput and memory — pairs naturally with a Leadership-Principles "dive deep" story.

Hands-on exercise

In the editor above, extend insertAtFront to insert at an arbitrary index k and return the shift count. Predict the count for k = 2 on a 5-element array before running it, then confirm — and state the general formula in terms of n and k.
Using the 2D grid block, write a loop that sums only the diagonal (grid[i][i]) and say out loud why that's O(n) while summing the whole grid is O(n²).
Say it out loud, as in a micro1 screen: explain in one breath why arr[999999] is no slower than arr[0], then why arr.includes(x) gives you no such guarantee.
Take a snippet that calls arr.includes(id) inside a map over the same array. State its complexity, then rewrite it with a Set and state the new one.

Chapter Summary

An array is a contiguous block of equal-sized cells; that layout is the source of all its behaviour.
Index access is O(1) because the address is computed (base + index × elementSize), not searched — the array's defining superpower.
Dynamic arrays grow by allocating a bigger block and copying, which makes push/pop at the end amortized O(1), while unshift/shift/insert/delete at the front or middle are O(n) — they must shift elements.
Search by value is O(n); only access by index is free. That asymmetry drives the rest of this Volume toward hash maps and trees.
JS arrays are only truly contiguous while dense and integer-keyed — keep them that way or the engine may deoptimise them into hash maps.
2D arrays are 1D memory with a row-major convention; index grid[row][col] and expect O(rows × cols) to traverse.
Built-in methods aren't free: map/filter/slice/splice/includes/indexOf are O(n), sort is O(n log n) — and one inside a loop is a hidden O(n²).

Narrative bridge

Arrays gave us the contiguous, index-addressable foundation everything else is built on. But there's a special kind of array you use constantly and rarely think of as an array — the humble string, a sequence of characters. It looks simple and it is quietly full of traps: immutability that turns innocent concatenation into O(n²), encodings where one "character" is really several code units, and comparisons that aren't what they seem. That's next: Strings & Their Gotchas.

Editorial reflection — the array is the structure people assume they already understand, and that assumption is exactly what trips them. The syntax is a decade old to you; the memory model beneath it is what interviews and outages actually test. Once you can see the contiguous block — feel the elements physically shifting on a front insert, hear the resize-and-copy behind a push — you stop guessing at complexity and start deriving it. Everything else in this Volume is a variation on that one honest picture of how memory is laid out.

Enrol to track progress

Q&A · 0

Enrol to ask questions and join the discussion.

No questions yet — be the first to ask.