Arrays

Lesson 1 of 7 in Foundations · 25 min · Beginner

A row of numbered boxes, side by side in memory.

Introduction

Your phone holds 10,000 songs. Tap song number 7,342 and it starts at once. How does it find that song without counting past the first 7,341?

If you were walking along a shelf of 10,000 records, you would count your way there, and a longer shelf would mean a longer walk. Yet the phone takes the same tiny moment for song 7,342 as for song 1.

Here is the clue. The songs sit in one unbroken row of boxes, all the same size, and the phone knows where the first box starts.

Lesson overview

This lesson will show you how to:

Explain why an array reaches any index in constant time.
Trace how inserting in the middle shifts later elements right.
Trace how deleting from the middle shifts later elements left.
Choose an array when you read by position and the length barely changes.
Spot when a prefix sum or hash map beats scanning the array.

The picture

Array nums with 5 slots: 7, 3, 9, 4, 1. Pointers: i at index 3. Marked: index 3 focus.

Mental model

Picture a corridor of lockers, all the same width, bolted side by side and numbered from 0 at the door.

To reach locker 7 you don't open the first six to check. You know every locker is one width wide, so you walk 7 widths from the door and you are there. An array is that corridor in memory.

Same-size boxes in an unbroken row, so the box you want is at start + index × size and you can go straight to it.

Words to know

index: The number of a box, counting from 0. The first box is index 0, so a list of 5 has indexes 0 to 4.
element: The value stored in one box.
contiguous: Side by side with no gaps. An array's boxes are contiguous in memory.
address: Where a box lives in memory, as a number. Address = start + index × size of one box.
capacity: How many boxes the array was built with. It is fixed. The size is how many of them are in use.
shift: Copying elements one slot over to open a gap (insert) or close one (delete). Every shifted element is one step of work.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

Yes: You read or change items by their position, again and again.
Yes: The data is a plain list that mostly stays the same length.
Yes: The problem says "given an array" and asks you to scan, count, compare or rearrange it.
Yes: You know, or can bound, how many items there will be.

Not this when

No: You keep inserting or deleting in the middle of a long list. Every change shifts everything after it, so look at linked lists.
No: You look things up by a key, like a name or an id, instead of a position. Hash maps find them without scanning.
No: You ask the same "sum from here to there" question over and over. Precompute running totals with prefix sums instead of re-adding.

Which pattern fits?

Which pattern? 1 of 5
Store the temperature for each of the last 365 days, then read the temperature of day 200 many times.
Which pattern? 2 of 5
Given thousands of customer names, answer "is Priya a customer?" quickly, many times over.
Which pattern? 3 of 5
A long list gets thousands of inserts and deletes at its front, and you never read by position.
Which pattern? 4 of 5
A list of numbers never changes. You get 100,000 questions of the form "what is the sum from index l to r?"
Which pattern? 5 of 5
Find where a number sits in a sorted list of a million numbers as fast as you can.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode

1if size == capacity: stop, there is no room
for j from size down to i + 1:
2copy nums[j - 1] into nums[j]
3nums[i] = value
4size = size + 1, and return it

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

def insert(nums, size, i, value):
    if size == len(nums):
        return -1
    for j in range(size, i, -1):
        nums[j] = nums[j - 1]
    nums[i] = value
    return size + 1

Time · O(n)Space · O(1)

Insert shown here. Delete is the mirror image: slide the elements after index i one slot left, then clear the last slot.
Access is O(1): address = base + i × size, so every index costs one jump.
Insert and delete are O(n) in the worst case because up to n elements shift. At the very end nothing has to move, so they are O(1) there.
Search by value is O(n): in the worst case every slot is looked at. A sorted array can do better with binary search.
Insert and delete work in place, so they use O(1) extra space. The array itself takes O(n). A full array can't grow: you would copy everything into a bigger one.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode

Given an integer array nums and a value val, remove every occurrence of val in place. Return k, the number of elements not equal to val. The first k slots of nums must hold them, in any order.

Input

nums = [3,2,2,3], val = 3

Output

2, with nums = [2,2,_,_]

Approach

Deleting each 3 with a shift would cost O(n) per delete. Instead, make one pass and keep a write position for the next slot to fill.
Walk through the array with read. Whenever nums[read] is not val, copy it into nums[write] and move write on.
Here 3 is skipped, 2 goes to slot 0, 2 goes to slot 1, and the last 3 is skipped.
write ends at 2. The first 2 slots hold [2, 2], and whatever sits after them doesn't matter.

def remove_element(nums, val):
    write = 0
    for read in range(len(nums)):
        if nums[read] != val:
            nums[write] = nums[read]
            write += 1
    return write

Time · O(n)Space · O(1)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

Why can the computer read nums[500] as fast as nums[0]?
An array starts at address 2000 and each box takes 8 bytes. Where does index 5 live?
You insert a number at index 0 of an array that holds 100 numbers and has room to spare. How many numbers move?
Why does insert shift from the last number backwards, not from the front?
You search an unsorted array of n numbers for a value that isn't there. How many slots do you look at?

Question 1 of 5

Why can the computer read nums[500] as fast as nums[0]?

The boxes are the same size and side by side, so the address is start + 500 × size.It sorts the boxes before it reads.It keeps the first 500 boxes in a faster kind of memory.Computers count so quickly that 500 steps don't show.

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

Solve Running Sum of 1d Array (opens in a new tab) (LeetCode, easy)
Hint: Each new total is the previous total plus one more number, so a single left-to-right pass is enough.
Solve Contains Duplicate (opens in a new tab) (LeetCode, easy)
Hint: Scanning for repeats for every number is slow. Remember what you have seen and ask whether the current number is in there.
Solve Merge Sorted Array (opens in a new tab) (LeetCode, easy)
Hint: The free room is at the end of the array, so fill from the back, taking the bigger number each time. Nothing gets overwritten.
Solve Remove Duplicates from Sorted Array (opens in a new tab) (LeetCode, easy)
Hint: Equal numbers sit side by side. Use a write position and only copy a number when it differs from the one before it.
Solve Find Pivot Index (opens in a new tab) (LeetCode, easy)
Hint: At each index, the right sum is the total minus the left sum minus the current number. Keep the left sum as you go.
Solve Product of Array Except Self (opens in a new tab) (LeetCode, medium)
Hint: The answer at i is everything to its left times everything to its right. Build the left products in one pass and fold in the right products in another.
Solve Maximum Subarray (opens in a new tab) (LeetCode, medium)
Hint: At each number decide: extend the run you have, or start fresh here. A run with a negative total only drags the next number down.
Solve First Missing Positive (opens in a new tab) (LeetCode, hard)
Hint: Use the array as its own lookup: a number v between 1 and n belongs at index v - 1, so swap each one home and look for the first slot that is wrong.

Additional resources

Array data structure (opens in a new tab) — Covers contiguous memory, index arithmetic, and why inserts and deletes cost O(n).
Data Structures (Python tutorial) (opens in a new tab) — A short tour of Python lists, the array-like type you will use most day to day.
std::array (opens in a new tab) — The fixed-size C++ array, showing contiguous, fixed-capacity storage in a precise reference.