Introduction to Arrays

EditorialUpdated Oct 25, 2026

Any index in one step

A school corridor has 500 lockers in a row, all the same width. To get to locker 317 you don't open the 316 before it. You know where the first one is and how wide each one is, so you walk straight there.

An array is that corridor in memory: values stored side by side, each taking the same number of bytes, with no gaps. If the array starts at address start and each value takes size bytes, value i lives at

start + i × size

That's one multiplication and one addition, whatever i is. You can see the pattern by printing addresses from C++ on the judge. Counted from a[0], the five values of an int array sat at bytes 0 4 8 12 16, because an int takes 4 bytes. A long long takes 8, and its offsets went 0 8 16 24. So reading a[731] costs exactly what reading a[0] costs: O(1), whether the array holds ten values or ten million.

Eight int values in a row of memory, a[0] to a[7], with each box's address underneath: 1000, 1004, 1008 and so on up to 1028. A card says the array starts at 1000 and each value takes 4 bytes. To read a[5], a second card works out 1000 + 5 × 4 = 1020, and an arrow goes straight to the box at 1020; a[0] to a[4] are marked as never read. Two chips below show the same one step for a[0] (1000) and a[731] (1000 + 731 × 4 = 3924).

What each operation costs

The rule that makes indexing fast, side by side with no gaps, is also what makes the middle of an array expensive. To insert a value at index i, every value from i on has to move one slot right to open a gap. To delete one, every value after it moves one slot left to close the gap. At the end of the array, nothing has to move.

An array of six values, 3, 8, 1, 9, 4, 6, in a block of eight slots. Inserting 7 at index 2 moves 1, 9, 4 and 6 one slot right each, four moves, and 7 goes into the gap at index 2: 3, 8, 7, 1, 9, 4, 6. Appending 7 instead puts it in the free slot at index 6, and nothing moves.

So the cost depends on where you work:

Operation	Cost	Why
Read or write `a[i]`	O(1)	one address calculation
Append at the end	O(1) on average	the next section shows why
Insert or delete at index `i`	O(n − i)	the values after it move one slot each
Insert or delete at the front	O(n)	every value moves
Find a value, unsorted	O(n)	any value could be the one
Find a value, sorted	O(log n)	binary search halves the range with each look

It adds up quickly. Building an array of 100,000 values by inserting each one at the front moves 1 + 2 + … + 99,999 = 4,999,950,000 values. On the judge, the C++ version took 0.36 seconds; appending the same 100,000 values took 0.7 milliseconds.

When the array is full

A plain array has a fixed size: int a[100] in C++ or new int[100] in Java holds 100 values, for good. The arrays you use most, C++'s vector, Java's ArrayList, Python's list and JavaScript's Array, can grow. They're dynamic arrays: an ordinary array underneath, with room to spare. Each keeps two numbers, its size (the values stored) and its capacity (the slots reserved).

Appending into a spare slot is a plain write. But when every slot is taken, the array can't simply extend itself, because the memory right after it may belong to something else. So it moves house: it reserves a bigger block somewhere else, copies every value across, and frees the old block. That copy is O(n). How often it happens depends on how much bigger each new block is.

Try it below. Append values one at a time and watch the block fill up and move. Insert at the front of a full array. Then switch the rule to One more slot, which replays your steps the naive way.

Grow the Array: append, insert and delete, and count every value that moves

Doubling is what keeps appends cheap. The copies happen when the size reaches 1, 2, 4, 8 and so on, and each copies that many values. After n appends they add up to 1 + 2 + 4 + …, which is less than 2n. Spread over the n appends, that's fewer than 2 copies each: O(1) per append, on average (textbooks say amortized). The judge agrees. Over 1,000 push_backs, a C++ vector's capacity went 1, 2, 4, 8, … 1,024, and it copied 1,023 values in all.

Any rule that grows by a factor works the same way. A bigger factor copies less and leaves more slots empty. Java's ArrayList starts at 10 slots and grows by half: 1,000 appends copy 2,456 values. A Python list grows by about an eighth; on the judge its capacity went 4, 8, 16, 24, 32, 40, 52, 64, 76, 92, and so on. (Its memory allocator can sometimes extend a block in place and skip the copy, but the cost per append is O(1) on average either way.) V8, the JavaScript engine in Chrome and Node, grows by half plus 16.

A rule that adds a fixed amount, one slot or a hundred, copies the whole array again and again. One slot at a time, 1,000 appends copy 1 + 2 + … + 999 = 499,500 values: about n²/2, so O(n) per append. No real library does that, and now you know why.

Two habits follow:

If you know the size, say so. v.reserve(n) in C++ or new ArrayList<>(n) in Java reserves the room once. After reserve(1000), 1,000 push_backs copied 0 values.
In C++, a growing vector moves its values. A pointer, reference or iterator into a vector points at freed memory once it grows. On the judge, data() changed when a full 4-value vector took a fifth (its capacity went 4 → 8). Don't keep one across a push_back.

One walk, the right records

Most questions about one array are answered in a single walk from left to right, carrying a few numbers along. The skill is choosing those numbers. Here's a test that works: say what each one means, as a sentence that's true after every step. If you can, the code follows, and so does the proof that it's right.

The largest value. Carry best, meaning the largest value seen so far. Starting at nums[0] makes that true after the first value. Each step keeps it true, because the largest of what you've seen now is either the old best or the new value. So after the last step, it's the largest of everything:

def find_max(nums):
    best = nums[0]                              # the largest of the values seen so far: just nums[0]
    for x in nums[1:]:
        if x > best:
            best = x                            # still the largest of everything seen so far
    return best

find_max([4, 7, 6, 3, 1]) returned 7, find_max([-3, -7, -1]) returned −1, and find_max([42]) returned 42.

The second largest. Second Maximum Without Sorting asks for the largest value that's strictly below the maximum, or −1 if there isn't one. Sorting would take O(n log n). Two records do it in one pass: first, the largest so far, and second, the largest so far that's below first. Each new value does one of three things:

it beats first: the old first drops to second place, and the new value takes first;
it lands between them: it becomes the new second;
anything else (a copy of first, or no bigger than second): nothing changes.

In the first case, order matters: copy the old first into second before you overwrite it.

The second largest of [12, 35, 1, 10, 34, 1] — The current value is lit; the labels above the row mark where first and second came from.

int secondLargest(const vector<int>& nums) {
    int first = -1, second = -1;                   // -1: none yet (every value is positive)
    for (int x : nums) {
        if (x > first) {                           // a new largest: the old one becomes the runner-up
            second = first;
            first = x;
        } else if (x < first && x > second) {      // below the largest, above the runner-up
            second = x;
        }
    }
    return second;                                 // still -1 if no value was below the largest
}

def second_largest(nums):
    first = second = -1                         # -1: none yet (every value is positive)
    for x in nums:
        if x > first:                           # a new largest: the old one becomes the runner-up
            second, first = first, x
        elif first > x > second:                # below the largest, above the runner-up
            second = x
    return second                               # still -1 if no value was below the largest

static int secondLargest(int[] nums) {
    int first = -1, second = -1;                   // -1: none yet (every value is positive)
    for (int x : nums) {
        if (x > first) {                           // a new largest: the old one becomes the runner-up
            second = first;
            first = x;
        } else if (x < first && x > second) {      // below the largest, above the runner-up
            second = x;
        }
    }
    return second;                                 // still -1 if no value was below the largest
}

function secondLargest(nums) {
    let first = -1, second = -1;                   // -1: none yet (every value is positive)
    for (const x of nums) {
        if (x > first) {                           // a new largest: the old one becomes the runner-up
            second = first;
            first = x;
        } else if (x < first && x > second) {      // below the largest, above the runner-up
            second = x;
        }
    }
    return second;                                 // still -1 if no value was below the largest
}

Each prints 34, 5, −1, −1, 3, 5, 4 and 4 for [12, 35, 1, 10, 34, 1], [10, 5, 10], [10, 10, 10], [7], [3, 9], [9, 3, 5], [1, 2, 3, 4, 5] and [5, 4, 3, 2, 1]. The −1 start works because the problem's values are all positive. With negative values allowed, start at the smallest possible value, or keep a separate flag for "none yet".

The longest run. Max Consecutive Ones carries streak, the length of the run of 1s ending here, and best, the longest run so far. A 1 extends the streak and a 0 resets it. Compare best at every step, not only when a 0 ends a run:

def find_max_consecutive_ones(nums):
    streak = best = 0                           # the run of 1s ending here, and the longest run so far
    for x in nums:
        streak = streak + 1 if x == 1 else 0
        best = max(best, streak)                # compared at every step, so a run at the very end counts
    return best

It returned 3, 2, 0 and 1 for [1, 1, 0, 1, 1, 1], [1, 0, 1, 1, 0, 1], [0, 0] and [1].

The best pair, earlier then later. Best Time to Buy and Sell Stock: buy on one day and sell on a later one, for the biggest profit (0 if prices only fall). Trying every pair of days is 4,999,950,000 pairs for 100,000 days. One record cuts it to a single pass: the lowest price before today. Whichever day you sell on, the best day to have bought is the cheapest one before it. So each day, try selling at today's price against that record, then let today's price lower the record if it can.

Best Time to Buy and Sell Stock on [7, 1, 5, 3, 6, 4] — Today is lit; the green cell is the lowest price before today, the day to have bought on.

int maxProfit(const vector<int>& prices) {
    int lowest = prices[0], best = 0;              // the lowest price before today, and the best sale so far
    for (size_t day = 1; day < prices.size(); day++) {
        best = max(best, prices[day] - lowest);    // sell today, having bought at the lowest price before it
        lowest = min(lowest, prices[day]);         // only now may today count as a buying day
    }
    return best;
}

def max_profit(prices):
    lowest, best = prices[0], 0                 # the lowest price before today, and the best sale so far
    for price in prices[1:]:
        best = max(best, price - lowest)        # sell today, having bought at the lowest price before it
        lowest = min(lowest, price)             # only now may today count as a buying day
    return best

static int maxProfit(int[] prices) {
    int lowest = prices[0], best = 0;              // the lowest price before today, and the best sale so far
    for (int day = 1; day < prices.length; day++) {
        best = Math.max(best, prices[day] - lowest);   // sell today, having bought at the lowest price before it
        lowest = Math.min(lowest, prices[day]);    // only now may today count as a buying day
    }
    return best;
}

function maxProfit(prices) {
    let lowest = prices[0], best = 0;              // the lowest price before today, and the best sale so far
    for (let day = 1; day < prices.length; day++) {
        best = Math.max(best, prices[day] - lowest);   // sell today, having bought at the lowest price before it
        lowest = Math.min(lowest, prices[day]);    // only now may today count as a buying day
    }
    return best;
}

Each prints 5, 0, 2, 0, 1 and 2 for [7, 1, 5, 3, 6, 4], [7, 6, 4, 3, 1], [2, 4, 1], [3], [1, 2] and [2, 1, 2, 1, 0, 1, 2]. One pass and two numbers: O(n) time, O(1) space.

A total that tells you what's missing. Two of the practice problems carry a single total. Missing Number has every number from 0 to n except one. Their sum is n(n + 1)/2, so the missing number is that minus the array's sum: for [3, 0, 1] that's 6 − 4 = 2. Single Number has every value twice except one. Combine them all with XOR (^): a value XOR itself is 0, so the pairs cancel and the single value is left ([4, 1, 2, 1, 2] gave 4). The Bit Manipulation & Number Theory section covers XOR properly.

Each record answers one kind of question:

The question	What to carry	Practice
the largest, the second largest	the best so far, and the runner-up	Find Maximum in Array, Second Maximum Without Sorting
the longest run	the run ending here, and the best run	Max Consecutive Ones
the best pair, earlier then later	the best partner seen so far	Best Time to Buy and Sell Stock
what's missing or unpaired	one total over everything	Missing Number, Single Number

Arrays in your language

What each language calls an array, what b = a gives you, and what a bad index does. All of these ran on the judge.

Language	Arrays	`b = a`	A bad index
C++	`vector` grows; `int a[n]` and `std::array` are fixed	a copy	not checked; `.at(i)` throws
Python	`list`	the same list; `a[:]` copies	`IndexError`, but `a[-1]` reads the last value
Java	`ArrayList<Integer>` grows; `int[]` is fixed and starts as zeros	the same array	throws
JavaScript	`Array`	the same array; `[...a]` copies	`undefined`, and no error

And the trap in each:

C++: passing a vector by value copies all n values on every call. Pass const vector<int>&.
Python: [[0] * 3] * 3 makes three references to one row, so grid[0][0] = 1 gave [[1, 0, 0], [1, 0, 0], [1, 0, 0]]. Build each row on its own with [[0] * 3 for _ in range(3)].
Java: list.remove(1) removes index 1, not the value 1: on [1, 2, 3] it left [1, 3]. list.remove(Integer.valueOf(1)) removes the value, which left [2, 3].
JavaScript: sort() with no argument compares values as text: [10, 9, 1, 100].sort() gave [1,10,100,9]. Pass (x, y) => x - y. And new Array(3).fill([]) puts one shared array in every slot: one push gave [[1],[1],[1]].

When an array isn't the answer

An array is the default, and the right choice when:

you reach values by position: the i-th, the next, the previous;
you walk the values in order, once or a few times;
values change in place, or come and go only at the end.

Reach for something else when the operation a problem repeats is one an array is slow at:

many inserts or deletes at the front, like a queue: each one moves everything. A deque does both ends in O(1) (Stacks & Queues).
many "is x in here?" questions: each one scans the array. A hash set answers in O(1) on average (Hashing), or sort once and binary search (Binary Search).
values that must stay sorted as you add them: each insert into a sorted array is O(n). A heap gives you the smallest or largest quickly (Heaps & Priority Queues), and a balanced tree keeps everything in order.
inserting in the middle at a spot you already hold: a linked list does it in O(1) (Linked Lists: From Basics to Advanced).

One more thing worth noticing: the records in this lesson never look back. They work even when the values arrive one at a time and can't all be kept, like a live stream of prices.

Common mistakes

Starting the maximum at 0. best = 0

Fine for heights, wrong for temperatures: on [-3, -7, -1] it returns 0, a value that isn't even in the array. Start at nums[0].

Starting both records at the first value. first = second = nums[0]

When nums[0] is the largest, second never drops below it: [9, 3, 5] returns 9, where the answer is 5. Start second at "none".

Letting a copy of the largest in. elif x > second: without x < first

On [10, 5, 10] it returns 10: the second 10 beat second and took its place. The answer is 5.

Comparing the streak only when a 0 arrives. best = max(best, streak) inside the else

A run that lasts to the end is never compared: [1, 1, 0, 1, 1, 1] returns 2, where the answer is 3. Compare at every step.

Answering the stock problem with max − min. max(prices) - min(prices)

The highest price can come before the lowest, so this sells before it buys. It returns 6 for [7, 1, 5, 3, 6, 4] (the answer is 5) and 6 for [7, 6, 4, 3, 1] (the answer is 0).

Deleting while walking forward. if (list.get(i) == 0) list.remove(i); inside for (i++)

Each delete slides the next value into slot i, and then i moves past it. Removing the zeros from [0, 0, 1, 0, 2] left [0, 1, 2]. Walk backwards, or copy the values you keep into a new array (Two Pointers shows how to do that in place).

Check yourself

Quiz

1 / 6

Multiple choice

An int array (4 bytes a value) starts at address 1000. At what address is a[6]?

Practice problems

From easier to harder:

Find Maximum in Array: one record, started at the first value.
Second Maximum Without Sorting: two records, updated in the right order.
Max Consecutive Ones: the run ending here, and the best run.
Missing Number: one total, the sum of 0 to n minus the sum of the array.
Single Number: one XOR over everything; the pairs cancel.
Union of Two Arrays: two sorted arrays walked side by side, a first taste of Two Pointers.
Binary Search: what sorted order buys you. Introduction to Binary Search teaches it in full.
Best Time to Buy and Sell Stock: the lowest price before today.

Next: Rearranging Arrays in Place, where the values move: rotating, reversing and putting each value in its own slot.