Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Arrays Explained: How They Work and What Each Operation Costs

How arrays store data in memory, why reading by index is O(1) but inserting at the front is O(n), and what that means for JavaScript arrays.

· Updated · 8 min read

An array stores a sequence of items next to each other in memory and lets you reach any of them by its position, called the index. It is the structure most problems start with, so its costs are worth knowing exactly.

How an array is stored

In a classic array, every item takes the same amount of space and the items sit side by side in one block of memory.

index:    0     1     2     3     4
value:  [ 12 ][ 45 ][  7 ][ 30 ][ 18 ]

Because the items are the same size and contiguous, the computer can calculate where any item lives:

address of item i = address of item 0 + (i × size of one item)

No searching is involved. That single calculation is why reading items[3] takes the same time whether the array has five items or five million.

What each operation costs

Operation Cost Why
Read or update by index O(1) The position is calculated directly
Add or remove at the end O(1) Nothing else has to move
Add or remove at the start O(n) Every other item shifts by one position
Add or remove in the middle O(n) Every item after that point shifts
Search for a value, unsorted O(n) Each item may need checking
Search for a value, sorted O(log n) Binary search halves the range each step

The costs follow from one fact: items must stay contiguous. Removing the first item leaves a gap, so everything after it moves down to fill it.

Why the front is expensive: a picture

Removing the first item:

before:   [ 12 ][ 45 ][  7 ][ 30 ][ 18 ]
remove 12:      [ 45 ][  7 ][ 30 ][ 18 ]    a gap at index 0
after:    [ 45 ][  7 ][ 30 ][ 18 ]          four items each moved one place

Inserting 99 at index 1:

before:   [ 12 ][ 45 ][  7 ][ 30 ]
make room:[ 12 ][    ][ 45 ][  7 ][ 30 ]    three items each moved one place
after:    [ 12 ][ 99 ][ 45 ][  7 ][ 30 ]

The number of items that move is the number of items after the change. At the end that is zero. At the start it is all of them. For an array of a million items, removing from the front a million times means roughly half a million million moves.

Dynamic arrays

A fixed block of memory cannot grow, yet push works on a JavaScript array of any length. Languages provide this with a dynamic array: when the block is full, a larger block is allocated, usually about twice the size, and the items are copied across.

One push in that situation costs O(n) for the copy. But it happens rarely, and each time the capacity doubles, so the cost averaged over many pushes stays constant. This is called amortised O(1).

Arrays in JavaScript

Method Cost
arr[i], arr[i] = x O(1)
push, pop O(1)
shift, unshift O(n)
splice O(n)
includes, indexOf, find O(n)
slice, concat, spread [...arr] O(n), and creates a new array
sort O(n log n)

Two points that cause bugs:

const numbers = [10, 9, 1];
numbers.sort();                 // [1, 10, 9]  — sorted as text
numbers.sort((a, b) => a - b);  // [1, 9, 10]  — sorted as numbers

sort without a comparison function compares items as strings, and it changes the original array rather than returning a new one.

Copies and references

Assigning an array to another variable does not copy it. Both names refer to the same array.

const original = [1, 2, 3];
const same = original;       // another name for the same array
const copy = [...original];  // a new array with the same items
 
same.push(4);
console.log(original.length); // 4
console.log(copy.length); // 3

This matters whenever a function changes an array it was given: the caller's array changes too. Methods fall into two groups.

Change the array itself Return a new array
push, pop, shift, unshift slice, concat, spread [...arr]
splice, sort, reverse map, filter
fill toSorted, toReversed

A copy made with spread or slice is shallow: the new array is separate, but any objects inside it are still shared.

Arrays of arrays

A grid is stored as an array of rows, where each row is an array. grid[row][column] reads one cell, still in O(1).

There is a well-known trap when creating one:

const shared = new Array(2).fill([]);
shared[0].push("x");
console.log(shared[1].length); // 1
 
const grid = Array.from({ length: 2 }, () => []);
grid[0].push("x");
console.log(grid[1].length); // 0

fill([]) puts the same inner array in every slot, so changing one row changes them all. Array.from calls the function once per slot and creates a separate row each time.

Ways to loop

Loop Use it when
for (let i = 0; i < arr.length; i++) You need the index, or want to skip or go backwards
for (const item of arr) You only need each item
arr.forEach(fn) As above, when a function reads better. It cannot stop early
arr.map(fn), arr.filter(fn) You want a new array built from this one
arr.reduce(fn, start) You want one value built from all the items

Every one of these is O(n). Chaining three of them is three passes: still O(n), but three times the work of doing it in one loop.

Typed arrays

A JavaScript array can hold a mix of numbers, text and objects, so the engine does extra bookkeeping behind the scenes. For large amounts of numeric data there are typed arrays, such as Float64Array and Uint8Array. They hold one kind of number, have a fixed length, and are stored as the contiguous block described at the top of this page. They are what image, audio and binary file code uses.

A worked example: reverse an array in place

"In place" means changing the array you were given without creating a second one. Reversing shows how far reading and writing by index can take you.

function reverseInPlace(items) {
  let left = 0;
  let right = items.length - 1;
 
  while (left < right) {
    [items[left], items[right]] = [items[right], items[left]];
    left++;
    right--;
  }
  return items;
}

For [1, 2, 3, 4, 5]:

left right Swap Array afterwards
0 4 1 and 5 5, 2, 3, 4, 1
1 3 2 and 4 5, 4, 3, 2, 1
2 2 Stop: the indexes have met 5, 4, 3, 2, 1

Each swap is two reads and two writes by index, all O(1). The loop runs n/2 times, so the whole thing is O(n) time and O(1) extra space. Two indexes moving towards each other is the two pointers pattern in its simplest form.

When an array is the right choice

Use an array when you need:

  • to read items by position;
  • to keep items in a specific order;
  • to add and remove mostly at the end;
  • to loop over everything.

Reach for something else when the main operation is one arrays are slow at:

Common mistakes

  • Calling includes or indexOf inside a loop. That is a loop within a loop: O(n²). A Set gives the same answer in O(n) overall.
  • Removing items while looping forwards. After a removal the following items shift down and the next one is skipped. Loop backwards, or build a new array with filter.
  • Off-by-one errors. The last valid index is length - 1. Reading arr[arr.length] gives undefined in JavaScript rather than an error, which can hide the bug.
  • Assuming assignment copies. const b = a gives a second name for the same array. Use [...a] for a copy.
  • Sorting numbers without a comparison function. [10, 9, 1].sort() gives [1, 10, 9].
  • Using shift in a loop. Each call is O(n). Keep an index for the front instead.

Practise

Four patterns work directly on arrays:

Pattern Idea Start with
Two pointers Two indexes moving through the array Valid Palindrome
Sliding window A range that moves along Maximum Sum Subarray of Size K
Prefix sums Running totals stored once Find Pivot Index
Binary search Halving a sorted array Binary Search

Summary

  • An array stores items side by side, so any item can be reached by index in O(1).
  • Adding or removing at the end is O(1). Anywhere else is O(n), because later items must shift.
  • A dynamic array grows by copying into a larger block, which averages out to O(1) per push.
  • Searching is O(n), or O(log n) with binary search if the array is sorted.
  • Assigning an array shares it. Copy it when you need a separate one.
  • When the main job is lookup by value, or adding at the front, use a different structure.