What this module covers: Arrays are the first data structure everyone learns and the last one most engineers actually understand at the memory level. This module covers why array indexing is O(1), why insertion and deletion aren't the same cost everywhere in the array, how JavaScript engines grow arrays under the hood, and the reversal/subarray/flattening patterns that show up in almost every other module in this course.
Why Indexing Is O(1)
An array is a block of memory where every element sits the same distance apart, one after another. If you know the address where the array starts, and you know how large each element is, you can compute the address of any element with one multiplication and one addition:
address_of(arr[i]) = base_address + (i × element_size)
No searching. No walking through the structure. The engine computes an address and reads directly from it. That's why arr[500000] and arr[0] cost exactly the same — one arithmetic operation, regardless of array size. This is what O(1) access actually means at the hardware level, and it's the reason arrays are the default choice whenever you need to read by position.
Analogy: An array is an apartment building with a fixed unit size. If you know the building's street address and that each floor is identical, you can walk straight to apartment 47 without checking apartments 1 through 46 first. A linked list (Module P-2) is the opposite — you have to walk through every unit in order, because unit 47 doesn't tell you where it is until unit 46 hands you directions to it.
Why this matters in production: this is exactly why users[userId]-style lookups by numeric position are cheap, and why reaching for an array when you actually need to look things up by an arbitrary key (an email, a UUID) is the wrong structure — that's what Module F-4 (Hash Maps) is for. Arrays are fast at "give me position N." They are not fast at "find me the thing with this ID," because that requires scanning.
Insertion and Deletion: It Depends Where
Reading is uniformly O(1). Writing is not — the cost depends entirely on where in the array you insert or remove.
typescript
push/pop at the end don't disturb any other element — the array's shape after the operation just has one more or one fewer slot at the tail. unshift/shift/splice in the middle or at the front require physically moving every subsequent element to close or open a gap, because the whole point of an array is that elements stay contiguous and evenly spaced. Insert at the front of a 100,000-element array and you move 100,000 elements to make room for one.
This is the single most common array performance mistake: reaching for unshift() in a hot path (a queue implemented as array.push() + array.shift(), for instance) without realizing that the "removal" half of that pattern is O(n), not O(1). Module F-7 (Queues) covers the structure that actually gives you O(1) on both ends.
How Dynamic Arrays Actually Grow
JavaScript arrays (and Python lists, and Java's ArrayList) look like they can grow forever with no cost, because push() never asks you to declare a size upfront. Under the hood, engines allocate a fixed-size backing buffer and grow it by over-allocating — when the buffer is full, the engine allocates a new, larger buffer (commonly double the size) and copies every existing element into it.
typescript
Any single push() is usually O(1), but occasionally — when the buffer is full — it's O(n) because of the copy. Averaged over many pushes, the cost works out to O(1) amortized: the occasional expensive resize is "paid for" by all the cheap pushes between resizes. This is why building an array by repeated push() in a loop is the right pattern, and why, when you already know the final size, pre-allocating (new Array(n)) avoids every intermediate resize entirely — no correctness difference, but measurably less copying under heavy load.
Subarrays, Slicing, and Flattening
Most array problems you'll meet in the rest of this course aren't about single elements — they're about contiguous ranges (subarrays) or restructuring nested arrays.
typescript
reverseInPlace does the swap with O(1) extra space — no second array allocated, just the original array's contents rearranged. This in-place, two-pointer shape reappears constantly: it's the backbone of Module F-8 (Two-Pointer Technique) and shows up again in Module P-2 when reversing a linked list.
sumRange, computed naively, is O(n) per call — fine once, expensive if you call it thousands of times over overlapping ranges on the same array. That repeated-range problem is exactly what prefix sums and the sliding window pattern (Module F-9) exist to solve, by avoiding recomputation from scratch on every call.
Where This Shows Up in Your Stack
Node.js hot paths: building a large array via array.push() inside a loop is the correct, idiomatic pattern — V8's amortized growth handles it well. Building the same array by repeated [...array, newItem] spread in a loop is O(n) per iteration because each spread copies the entire array so far, turning an O(n) build into O(n²) overall. This is a common accidental-quadratic bug in reducer-style code that "looks" functional and clean but silently costs far more than the equivalent push().
MongoDB:$push appends to an array field on a document without rewriting the rest of the document or reindexing anything else — cheap, and the reason array fields in MongoDB are commonly used as append-only logs (recent activity, comment threads) rather than something you constantly reorder.
PostgreSQL: array slicing syntax (my_array[2:5]) and LIMIT/OFFSET pagination both lean on the same underlying idea as sumRange above — a contiguous range read is cheap relative to scanning and filtering the whole set, which is part of why range-based pagination patterns exist at all.
React/Next.js list rendering: re-deriving a filtered or sorted array on every render with array.filter().map() chains is fine at typical list sizes, but doing it inside a component that re-renders on every keystroke (a live search box over a large in-memory list, for instance) reintroduces the O(n) cost on every keystroke — this is one of the more common reasons a "just add a search filter" feature quietly makes typing feel laggy.
Summary
Array indexing is O(1) because element addresses are computed by arithmetic (base + i × size), not by searching.
Insertion/deletion cost depends on position. End operations (push/pop) are O(1); front or middle operations (unshift/shift/splice) are O(n) because elements must shift to stay contiguous.
Dynamic arrays grow by over-allocating and doubling. Any single push() is usually O(1), occasionally O(n) during a resize — averaging out to O(1) amortized.
Reversal and flattening are O(n) time. In-place reversal (two pointers swapping toward the middle) does it in O(1) extra space; flattening a 2D array is O(1) space impossible — the output is proportional to the input, so it's inherently O(n) space.
Repeated range queries over the same array are wasteful if recomputed from scratch each time — the motivation for prefix sums and sliding windows, both coming up shortly.
The next module, Strings: Immutability and Manipulation Patterns, looks at a data type that behaves like an array in memory but comes with one crucial difference in JavaScript: you can never modify a string in place.
Knowledge Check
Why is array.push(item) typically O(1), while array.unshift(item) is O(n) even though both only add a single new element?
Building a large array in a loop using result = [...result, newItem] on each iteration is a well-known accidental-quadratic pattern. Why does this happen, given that push() on the same loop is O(n) overall?
According to the module, why is reversing an array in-place with two pointers considered O(1) space, while flattening a 2D array into a 1D array cannot be done in O(1) space?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
const items =['a','b','c','d','e'];items.push('f');// O(1) — append at the end, no reflow neededitems.pop();// O(1) — remove from the end, no reflow neededitems.unshift('z');// O(n) — every existing element must shift right by oneitems.shift();// O(n) — every remaining element must shift left by oneitems.splice(2,0,'x');// O(n) — everything after index 2 must shift right
// Conceptually, what happens inside push() when the backing buffer is full:functiongrowAndPush<T>(buffer:T[], capacity:number, item:T):{ buffer:T[]; capacity:number}{if(buffer.length < capacity){ buffer.push(item);return{ buffer, capacity };}const newCapacity = capacity *2;// double the backing sizeconst newBuffer =newArray(newCapacity);// O(n) — copy every element acrossfor(let i =0; i < buffer.length; i++) newBuffer[i]= buffer[i]; newBuffer.push(item);return{ buffer: newBuffer, capacity: newCapacity };}
// Reverse an array in-place — two pointers moving toward each other (Module F-8 in full)functionreverseInPlace(arr:number[]):void{let left =0;let right = arr.length -1;while(left < right){[arr[left], arr[right]]=[arr[right], arr[left]];// swap left++; right--;}}// Flatten a 2D array into a 1D arrayfunctionflatten(grid:number[][]):number[]{const result:number[]=[];for(const row of grid){for(const value of row){ result.push(value);}}return result;// Note: JavaScript's built-in `grid.flat()` does exactly this, one level deep.}// A subarray slice — the range [start, end)functionsumRange(arr:number[], start:number, end:number):number{let total =0;for(let i = start; i < end; i++) total += arr[i];return total;}