Skip to content

level 1 · Foundations

Arrays & Memory

The row of numbered boxes that everything else is built on.

8 min 50 XP

what is it

Start here

Imagine a long row of boxes, all the same size, all touching each other. Each box holds one number. That is an array.

Every box has an address — its index. The first box is index 0, not 1. That trips up almost everyone at the start, and there is a good reason for it: the index is really a *distance*. Box 0 is zero boxes away from the start. Box 3 is three boxes away.

Because the boxes are the same size and sit in a row, the computer can jump to any one of them instantly. It doesn't search. It calculates where the box must be, and goes straight there. That single fact is the array's superpower — and everything it's bad at is the price it pays for it.

real-life analogy

Picture it

A street of identical houses

If houses 0 to 99 sit in a row and every house is the same width, you never search for house 57 — you know exactly how far down the street it is. But if a new family wants to move *into the middle*, everyone from that point on has to shift down one house. That is exactly what happens when you insert into an array.

interactive visualization

Watch it run

Type numbers separated by spaces. Watch what inserting costs.

  1. 4
    0
  2. 8
    1
  3. 15
    2
  4. 16
    3
  5. 23
    4

An array is a row of numbered boxes, sitting side by side in memory. The numbers on the boxes are the indexes, and they always start at 0.

step 01/13

  • comparing
  • moving
  • in final place
  • found it
1// Reading is instant. The computer can work out
2// exactly where box i lives, so it jumps straight there.
3const value = a[i];
4
5// Inserting in the middle is not instant.
6function insertAt(a, index, value) {
7 for (let i = a.length; i > index; i--) {
8 a[i] = a[i - 1]; // everyone shuffles right
9 }
10 a[index] = value;
11 return a;
12}
13
14function deleteAt(a, index) {
15 for (let i = index; i < a.length - 1; i++) {
16 a[i] = a[i + 1]; // everyone shuffles left
17 }
18 a.length--;
19 return a;
20}

variables right now

length
5
comparisons 0moves 0

the dry run · every step, in words

13 steps

complexity

What it costs

best case
O(1) to read
average
O(n) to insert
worst case
O(n) to insert
extra memory
O(n)

Reading is instant no matter how big the array gets. Inserting or deleting in the middle means shuffling everything after it — so the cost grows with the size of the array.

  • O(1)
  • O(log n)
  • O(n) · this one
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Thinking the last item of a 5-element array is at index 5.

    It is at index 4. With n boxes the last index is always n − 1, because counting starts at 0.

  • Assuming inserting at the front is as cheap as inserting at the end.

    Inserting at the end is usually instant. Inserting at the front makes every single element shuffle right — the most expensive thing you can do to an array.

  • Reading a[10] on an array of 5 items and expecting nothing bad to happen.

    That box was never yours. Some languages hand you undefined, some crash, and C++ will happily read a stranger's memory. Always check your bounds.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+50 XP

01An array has 8 items. What is the index of the last one?

02Why can a computer read a[500] instantly, without looking at the 500 boxes before it?

03You insert a value at the front of a 1,000,000-item array. Roughly how many items have to move?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.