Arrays and Strings — Algorithmics

An array is the simplest data structure there is, and understanding exactly what makes it fast explains most of the others by contrast.

One multiplication

The elements sit in memory back to back, all the same size. So the computer never searches for element 5. It calculates where it is:

address = start + 5 × bytesPerElement

One multiply and one add, regardless of whether the array has ten elements or ten million. That is what $O(1)$ indexing means, and it is the only reason arrays are worth anything.

What contiguity costs

Everything is back to back, so inserting in the middle means physically shifting everything after it:

values.splice(2, 0, 99);   // everything from index 2 rightwards moves one slot

$O(n)$ . Same for deleting from the middle. Adding at the end is cheap, because nothing is in the way.

Which gives the table people memorise, now with a reason attached:

	Cost	Because
Read `a[i]`	$O(1)$	arithmetic
Overwrite `a[i]`	$O(1)$	arithmetic
Push / pop at the end	$O(1)$ amortised	nothing is in the way
Insert / delete in the middle	$O(n)$	everything after it shifts
Search unsorted	$O(n)$	no structure to exploit
Search sorted	$O(\log n)$	binary search

“Amortised” is doing real work in that table

A fixed block of memory cannot grow. So when a dynamic array — Array in JavaScript, vector in C++, list in Python — runs out of room, it allocates a bigger block and copies everything across.

If it grew by one slot each time, every single push would copy the whole array and $n$ pushes would cost $O(n^2)$ . Instead it doubles. Watch where the copies land:

Push 1 / 16

1 items in a slot array of 1

copies this push: 0
copies so far: 0
average per push: 0.00

There was a free slot, so this push is a single write — the cheap case, and it is the case almost every time. The running average stays under 2 no matter how far you go.

The distinction matters in exactly one place: hard real-time code, where a single slow operation is unacceptable even if the average is fine. Everywhere else, amortised is the number you should reason with.

Strings are arrays with two complications

They are usually immutable. In JavaScript, Java, Python and C#, a string cannot be changed in place. Every += builds a whole new string:

let out = '';
for (const ch of input) out += ch;      // O(n²) — a fresh copy every iteration

For a 100,000-character input that is five billion character copies. Collect into an array and join once instead:

const parts: string[] = [];
for (const ch of input) parts.push(ch);
const out = parts.join('');             // O(n)

A character is not a character

"café".length is 4. "👨‍👩‍👧".length is 8.

JavaScript strings are sequences of UTF-16 code units, not of things a human would call letters. Anything outside the basic multilingual plane — emoji, many CJK extensions, musical notation — takes two units, and s[i] can hand you half of one.

const s = '👍';
s.length      // 2
s[0]          // '\ud83d' — a lone surrogate, meaningless on its own
[...s].length // 1 — iteration is code-point aware

Reversing a string with s.split('').reverse().join('') corrupts every emoji in it, and this is the single most common string bug in JavaScript. Use [...s] when you mean characters, and a proper grapheme segmenter (Intl.Segmenter) when you mean what a user would call characters.

The one precomputation worth knowing

If you will be asked “what is the sum of the range i to j?” many times, build a prefix sum array once:

const prefix = [0];
for (const v of values) prefix.push(prefix[prefix.length - 1]! + v);

// Sum of values[i..j] inclusive, in one subtraction:
const rangeSum = (i: number, j: number) => prefix[j + 1]! - prefix[i]!;

prefix[k] is the sum of the first k values. Everything before i is in both totals, so subtracting cancels it exactly and leaves the middle.

$O(n)$ to build, $O(1)$ per query. It converts a nested loop into two passes often enough that it is worth recognising the shape: many range questions over data that does not change.

In JavaScript specifically

Array is not really an array. It is an object with integer-ish keys, and the engine keeps it as a genuine contiguous block only while you behave:

const a = [1, 2, 3];
a[1000] = 4;        // now sparse — the engine switches to a dictionary
delete a[1];        // creates a hole; use splice if you mean "remove"

Once it converts, indexing is a hash lookup and the cache benefit is gone. Keep arrays dense, keep the element types uniform, and reach for Int32Array or Float64Array when you want a guarantee rather than a hope.