Dynamic Arrays
Lesson 2 of 7 in Foundations · 20 min · Beginner
An array that grows by moving into a bigger home.
Introduction
Python's list.append feels instant, yet an array can't count on growing in place. So where does the new item go?
An array is a block of memory bought in one piece, and whatever sits right after it may already belong to something else. So when 4 items fill a block of 4 and you call append, there is no room next door.
Yet you can append a million items in a loop without waiting. Something must happen when the block is full. What, and why doesn't it slow everything down?
Lesson overview
This lesson will show you how to:
- Explain why most pushes cost one write, not a copy.
- Trace a resize: the capacity doubles and every item moves across.
- Explain why doubling makes pushes amortised O(1) overall.
- Use a vector as a stack, pushing and popping at the back.
- Recognise when a reserve call or fixed array avoids growing entirely.
The picture
Mental model
Picture a family in a flat where you can't knock through the walls. When the family grows and every room is taken, they don't squeeze in. They rent a flat twice as big, carry everything across in one trip, and hand back the old keys.
The move is a hassle, but it buys a lot of spare rooms. The next several arrivals each just take a free room, so the family doesn't move again for a long time.
Moving everyone costs as much as the family is big, but it buys that many spare rooms, so the next pushes cost nothing extra.
Words to know
- size
- How many slots hold a real value right now. The next push writes at index size.
- capacity
- How many slots the block has in total. Size can never be bigger than capacity.
- growth factor
- How much bigger the new block is. Doubling is a factor of 2. Real libraries use values like 1.5 or 2, and any constant above 1 keeps pushes amortised O(1).
- reallocation
- Moving to a new block: allocate it, copy every element across, free the old one. It costs O(size).
- amortised
- Cost averaged over a whole run of operations. One push might copy everything, but n pushes together cost O(n), so the average push is O(1).
- iterator invalidation
- After a reallocation the elements live at new addresses. A pointer, reference or iterator into the old block now dangles, and using it is a bug (undefined behaviour in C++).
- shrink rule
- A policy for giving memory back, such as halving the block once size falls to a quarter of capacity. It is optional: std::vector and Java's ArrayList don't do it on their own.
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 build a list as you go and don't know how long it will end up.
- Yes: You read or change items by position, and mostly add or remove at the end.
- Yes: The problem says to collect, build or return a list whose length is unknown until you finish.
- Yes: You need a stack: push and pop at the back.
Not this when
- No: You insert or delete in the middle or at the front all the time. Every change shifts everything after it, so look at linked lists or queues.
- No: You look things up by value, like a name or an id. A hash map finds them without scanning.
- No: You know the exact size up front and it never changes. A plain array, or one reserve call, avoids all the growing.
Which pattern fits?
Which pattern? 1 of 5
Read a log file line by line and keep every line that contains ERROR. You can't tell how many there will be, and afterwards you want to read them by position.
Which pattern? 2 of 5
A weather app stores exactly 365 daily temperatures, never more and never fewer, and reads day 200 again and again.
Which pattern? 3 of 5
Count how many times each word appears in a document.
Which pattern? 4 of 5
A sensor appends a reading every second all day. Later you must jump straight to reading number 5,000.
Which pattern? 5 of 5
Splice a new item into the middle of a very long chain, at a spot you already hold, many thousands of times.
The code
First the idea in plain steps. Then the same idea as real code, line for line.
- 1data = an empty array of the starting capacity; size = 0; copies = 0
- for each value to push:
- 2if size == capacity:
- 3allocate a new array, twice as big (at least 1)
- 4copy data[0 .. size - 1] across, one by one
- 5data = the new array; capacity doubles; the old one is freed
- 6data[size] = value, then size = size + 1
- 7return copies
The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.
Getting the replay ready…
class Vector:
def __init__(self, capacity):
self.data = [0] * capacity
self.capacity = capacity
self.size = 0
self.copies = 0
def push_back(self, value):
if self.size == self.capacity:
bigger = [0] * max(1, 2 * self.capacity)
for i in range(self.size):
bigger[i] = self.data[i]
self.copies += 1
self.data = bigger
self.capacity = len(bigger)
self.data[self.size] = value
self.size += 1
def push_all(self, values):
for value in values:
self.push_back(value)
return self.copies- A push into a vector with a free slot is one write. A push into a full one copies everything, O(n). Over n pushes the copies add up to less than 2n, so the average push is a small constant.
- Why double instead of adding one slot? Growing by one would copy every element on every push, about n²/2 copies for n pushes. Any constant factor above 1 keeps pushes amortised O(1). A bigger factor wastes more memory, a smaller one copies more often.
- Real libraries differ, and versions change. std::vector in libstdc++ and libc++ doubles, MSVC grows by about 1.5, Java's ArrayList by about 1.5, and CPython's list by only about 1.125 plus a few slots. Treat these as ballpark numbers.
- Reading and writing by index is O(1), just like an array. Inserting or erasing in the middle is O(n) because later elements shift, and an insert needs the same room check first: if size equals capacity, grow, then shift.
- pop_back is O(1): it lowers size and copies nothing, and the old value stays in its slot until something overwrites it. Shrinking is optional. std::vector and Java's ArrayList don't shrink on their own (shrink_to_fit and trimToSize are requests you make), while CPython's list gives memory back once it falls below half full. The quarter rule in the Pop track is a common textbook policy: right after shrinking, the vector is half full, far from both growing and shrinking again.
- A reallocation invalidates every pointer, reference and iterator into the old block. If you hold one across a push_back, fetch it again afterwards. If you know roughly how many items are coming, reserve that capacity first and skip the resizes.
- A vector can start at capacity 0. The first push has to grow it to 1, so the growth rule needs max(1, 2 × capacity), because 2 × 0 is still 0 and an unguarded vector would never grow.
Worked examples
Real interview problems, solved with the same recipe.
Given an integer array nums of length n, build an array ans of length 2n where ans[i] == nums[i] and ans[i + n] == nums[i] for every 0 <= i < n. Return ans.
Input
nums = [1,2,1]
Output
[1,2,1,1,2,1]
Approach
- The answer has exactly 2n slots and you know n, so ask for all 2n slots once. The array never has to grow.
- Copy nums[i] into ans[i] for the first half.
- Copy the same nums[i] into ans[i + n] for the second half.
- Pushing 2n values into an empty vector would also be O(n) in total, but sizing it up front skips every resize and every copy.
def get_concatenation(nums):
n = len(nums)
ans = [0] * (2 * n) # ask for all 2n slots once: no resizing
for i in range(n):
ans[i] = nums[i]
ans[i + n] = nums[i]
return ansKnowledge check
Test yourself first. Try to answer these in your own words, then take the quiz below to check.
- A vector has size 4 and capacity 4. You push a fifth number. What happens?
- Why does a vector double its capacity instead of adding one slot at a time?
- Start with capacity 1 and push 8 numbers, doubling whenever the vector is full. How many copies happen in total?
- A vector with capacity 16 shrinks to capacity 8 as soon as its size falls to 8. What can go wrong?
- You hold a pointer to the first element of a vector, then a push_back triggers a reallocation. What is true about the pointer?
Question 1 of 5
Assignment
Pick one, try it cold for ten minutes, then come back for the hint.
0 of 7 solved
Solve Plus One (opens in a new tab) (LeetCode, easy)
Hint: Adding one can carry all the way and turn 999 into 1000, one digit longer than the input. Think about the only case where the answer needs an extra slot.
Solve Duplicate Zeros (opens in a new tab) (LeetCode, easy)
Hint: The array can't grow, so values pushed along fall off the end. Work out where each value lands, and fill from the back so you don't overwrite what you still need.
Solve Pascal's Triangle (opens in a new tab) (LeetCode, easy)
Hint: Build each row by appending to a new vector, using neighbouring numbers of the row above. Row i has exactly i + 1 numbers.
Solve Implement Queue using Stacks (opens in a new tab) (LeetCode, easy)
Hint: Use two vectors as stacks. Moving everything from one to the other costs O(n), but each element moves at most once, so the average cost per operation is O(1): amortised again.
Solve Design Browser History (opens in a new tab) (LeetCode, medium)
Hint: Keep the pages in a vector plus an index for the current page. Visiting a new page throws away everything ahead of the index, which is a run of pop_back calls.
Solve Design Circular Queue (opens in a new tab) (LeetCode, medium)
Hint: This is the opposite of a vector: a fixed capacity that never grows. Indices wrap around with a modulo, so both ends move without shifting anything.
Solve Insert Delete GetRandom O(1) - Duplicates allowed (opens in a new tab) (LeetCode, hard)
Hint: It is the swap-with-last and pop_back trick from the example, but a value can now appear several times, so each value maps to a set of indices instead of one.
Additional resources
- Dynamic array (opens in a new tab) — Explains capacity, resizing by doubling, and the trade-off against wasted space.
- Amortized analysis (opens in a new tab) — The averaging argument that explains why occasional expensive pushes still cost O(1) on average.
- std::vector (opens in a new tab) — The C++ vector reference, covering capacity, reserve and when reallocation invalidates references.