Lesson 07
Arrays & Memory: Boxes in a Row
Why reading index 5,000 is instant but inserting at the front is slow.
01Why it matters & the intuition
The array is the foundation of almost every other structure — heaps, hash tables, dynamic programming tables and adjacency lists all sit on top of one. Understanding contiguous memory explains most performance surprises.
Think of it like…
An array is a row of numbered lockers. To open locker 5,000 you walk straight to start + 5000 × lockerWidth — one calculation, O(1). But to squeeze a new locker in at the front, every item has to shuffle one to the right: O(n).
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- comparing / current
- moving / removing
- done / found / visited
03Key ideas
Contiguous memory
Elements sit side by side, so address(i) = base + i × size. That arithmetic is why random access is O(1) and why CPUs cache arrays so well.
Shifting costs
Inserting or deleting at index i moves every element after i. At the end that is 0 moves; at the front it is n moves.
Dynamic arrays
JavaScript arrays and Python lists grow automatically. When full, they allocate double the capacity and copy everything — O(n) once, but amortised O(1) per push.
Amortised analysis
Doubling means n pushes cause copies of 1 + 2 + 4 + … + n ≈ 2n elements in total — still O(1) per push on average.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
// A dynamic array built on a fixed-size buffer — what JS does for you.
class DynamicArray<T> {
private data: (T | undefined)[];
private length = 0;
constructor(private capacity = 2) {
this.data = new Array(capacity);
}
get size() { return this.length; }
get(index: number): T {
if (index < 0 || index >= this.length) throw new RangeError("index out of bounds");
return this.data[index] as T;
}
push(value: T): void {
if (this.length === this.capacity) this.resize(this.capacity * 2);
this.data[this.length++] = value;
}
insert(index: number, value: T): void {
if (index < 0 || index > this.length) throw new RangeError("index out of bounds");
if (this.length === this.capacity) this.resize(this.capacity * 2);
for (let i = this.length; i > index; i--) this.data[i] = this.data[i - 1]; // shift right
this.data[index] = value;
this.length++;
}
removeAt(index: number): T {
const value = this.get(index);
for (let i = index; i < this.length - 1; i++) this.data[i] = this.data[i + 1]; // shift left
this.data[--this.length] = undefined;
return value;
}
private resize(newCapacity: number): void {
const next = new Array<T | undefined>(newCapacity);
for (let i = 0; i < this.length; i++) next[i] = this.data[i];
this.data = next;
this.capacity = newCapacity;
}
}05Complexity
| Operation | Time | Space |
|---|---|---|
| Read / write by index | O(1) | — |
| Push / pop at end | O(1) amortised | — |
| Insert / delete at front or middle | O(n) | — |
| Search unsorted | O(n) | — |
| Grow (resize + copy) | O(n) | O(n) |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Reverse in place
Write reverse_in_place(arr) that reverses the array in place using O(1) extra space (no .reverse(), no new array) and returns the same array.