How an array is stored in memory
One-line list operations can cost very different amounts. a[i] takes one step however long the list is. On a list of values, x in a takes up to steps, and a.pop(0) takes steps while a.pop() takes one. The differences all come from how a list is stored in memory.
Our example is the closing price of a stock on six days, numbered from 0:
day 0 1 2 3 4 5price 7 1 5 3 6 4In a program this is the list prices = [7, 1, 5, 3, 6, 4], and prices[3] is 3, the price on day 3.
Definition
An array stores its values in slots of equal size, placed side by side in one block of memory. A slot's position in the block, counted from 0, is its index, so an array of values has indices 0 to .
Find a slot from its index
Memory is a long row of numbered bytes, and the number of a byte is its address. Because the slots are equal in size and have no gaps between them, the program never has to search for slot . It computes the slot's address from the address where the block starts:
In the figure the block starts at address 1000 and each slot takes 4 bytes, so slot 3 is at . In an array of 100,000 prices, the last one would be at , found with the same multiplication and addition. So reading or replacing the value at an index takes the same few steps for every index and every length, which is constant time, .
The figure draws 4-byte slots, the size of a C++ int. A Python list's slots are 8 bytes each, and each slot holds the address of a value stored elsewhere in memory, which is how one list can hold a short string beside a long one. The arithmetic is the same.
Finding a value is different. The formula turns an index into an address, but nothing turns the value 6 into an index. To learn whether any day closed at 6, the program compares the slots with 6 one at a time, and if the 6 is in the last slot or is missing, that takes comparisons, which is .
The cost of adding and removing a value
A Python list is a dynamic array, an array whose length can change. Its values still have to sit side by side with no gaps, because the address formula depends on that, and keeping them that way is what makes some changes expensive. Here are five changes to our prices, with the list after each one:
prices = [7, 1, 5, 3, 6, 4]
prices.append(8) # [7, 1, 5, 3, 6, 4, 8] goes in the next free slot
prices.pop() # [7, 1, 5, 3, 6, 4] nothing else moves
prices.insert(0, 9) # [9, 7, 1, 5, 3, 6, 4] all 6 values move right
prices.pop(0) # [7, 1, 5, 3, 6, 4] all 6 move back left
prices.pop(2) # [7, 1, 3, 6, 4] 3, 6 and 4 move left
print(prices)Prints [7, 1, 3, 6, 4].
Look at the last change. Removing the 5 from index 2 leaves a gap in the block, and the gap has to be filled, because the address formula puts index 3 exactly three slots from the start. So the 3, the 6 and the 4 each move one slot left. An insertion works the other way: the values from the insertion point onward each move one slot right to make room for the new value. In general, a removal at index moves the values after it, and an insertion at index moves the values from index onward.
So the cost depends on where the change happens. Nothing moves at the end and everything moves at the front, although both are one short line of code. Suppose a program empties an array of 200,000 values from the front, one removal at a time. The first removal moves 199,999 values, the next 199,998, and so on:
At the rule-of-thumb rate of simple steps a second, that would be about 200 seconds of work. From the back, the same job takes 200,000 steps.
In practice, the program that empties from the front runs faster than that. Python shifts the values with one call to a library routine built for moving a block of memory, which is much faster than a loop that moves one value at a time. That makes each move cheaper, but the number of moves stays the same, so the time still grows with the square of the length. On our laptop, a.pop(0) took about 2.5 seconds to empty 200,000 values, and half as many values took about a quarter of that. a.pop() emptied them from the back in about 0.004 seconds.
| Operation | Code | Cost | Why |
|---|---|---|---|
| Read or replace index | a[i], a[i] = x | The address is computed | |
| Add or remove at the end | a.append(x), a.pop() | , amortized for adding | No other value moves, except when an append finds the array full, which the next part covers |
| Insert or remove at index | a.insert(i, x), a.pop(i) | , or when an insert finds the array full | Every later value moves one slot; a full array is first copied to a larger block, as the next part explains |
| Search for a value | x in a, a.index(x) | Slots are compared one at a time |
Adding at the end: spare capacity and doubling
Adding a value at the end, an append, moves nothing. But the new value needs a slot after the last one, and that memory may already belong to something else. So a dynamic array usually holds more slots than it uses, and it keeps count of how many of them hold values. Its length is the number of values in it, and its capacity is the number of slots it holds. While the length is below the capacity, an append writes one slot.
When the two are equal, the array is full. The next append has to get a larger block of memory, copy every value into it and then write the new one, so that one append copies the whole array. How often this happens depends on how much larger the new block is. Suppose the capacity doubles each time. The figure follows nine appends to an array that starts with one slot.
The four appends that found the array full copied 1, 2, 4 and 8 values, 15 in all. Going back from the last copy, each earlier copy is half the one after it: 4 is half of 8, 2 is a quarter of 8 and 1 is an eighth of 8. Those add up to 7, which is less than 8. The same happens with more copies: before a copy of 16, the earlier copies add up to 15. So all the copies together come to less than twice the last one.
The last copy moved only values that were already in the array, which is fewer than , the number of appends so far. So appends make fewer than copies:
Add the writes of the new values, and appends take fewer than steps. A single append can still cost steps, but spread over all appends the cost is less than 3 steps for each. A cost like this, an average that holds for every sequence of operations on an array that starts empty, is called an amortized cost. So an append takes amortized time, and when you add up the steps a program takes, you can count each append as a constant number of them.
Recall An array starts with one slot and doubles when full. How many values does it copy while you append 1,000 values?
1,023. The appends that find it full are numbers 2, 3, 5, 9 and so on up to 513, and they copy values, which is less than .
Deeper read: growth factors other than 2
The capacity does not have to double. Multiplying it by any fixed factor above 1 keeps the total number of copies proportional to . A smaller factor copies more often and leaves fewer slots unused.
CPython, the standard Python, gives a full list room for its new length, plus one eighth of that length, plus 6, rounded down to a multiple of 4. A comment in its source lists the capacities a growing list passes through: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76 and so on. The extra 6 matters for short lists; a long list grows by about one eighth each time.
What does not work is adding a fixed number of slots. If the capacity grows by one slot at a time, every append finds the array full and copies all of it:
That is about 50,000 copies for each append, where doubling needs fewer than 2. Growing by 100 slots at a time divides the total by about 100, and it still grows with .
Keep the lowest value so far while reading the array
Many array problems can be solved by reading the values once, from left to right, while keeping track of a few numbers, such as the lowest value so far. We start with our prices, 7, 1, 5, 3, 6 and 4 on days 0 to 5. Suppose you may buy one share on one day and sell it on a later day. Buying at 1 on day 1 and selling at 6 on day 4 earns 5, and no other pair of days earns more.
You get the price of one stock on each of days, in a list prices. Choose one day to buy and a later day to sell, and return the largest profit you can make. If no sale makes a profit, return 0.
Constraints
Sample 1 · Input
prices = [7,1,5,3,6,4]
Output
5
Sample 2 · Input
prices = [7,6,4,3,1]
Output
0
In the second sample the price falls every day, so every trade loses money, and the answer is 0: the best choice is not to trade.
The direct method tries every buy day with every later sell day. For days that is pairs, and the problem allows days:
That is about 50 times the simple steps a computer runs in a second. Most of the pairs can be ruled out without being looked at. Fix the day you sell on, say day 4, when the price is 6. The earlier prices are 7, 1, 5 and 3, and the sale brings in 6 whichever of them you bought at, so the best purchase is the cheapest, 1. The same holds for every sell day: the best trade that sells on day buys at the lowest price before day .
So the program can read the prices once, from day 0 onward, and remember one number: the lowest price seen so far. Keeping it up to date takes one comparison a day, and on each day the program also works out what selling that day would earn.
Step through the pass over the prices
Step through the six prices, then change them. Try 9, 7, 4, 1, where the price only falls, and 3, 8, 2, where the lowest price comes after the best trade.
The code keeps lowest, the lowest price so far, and best, the best profit so far.
def max_profit(prices):
lowest = prices[0]
best = 0
for price in prices:
best = max(best, price - lowest)
lowest = min(lowest, price)
return best
print(max_profit([7, 1, 5, 3, 6, 4]))
print(max_profit([7, 6, 4, 3, 1]))Prints 5, then 0.
best starts at 0, the profit of not trading, so a falling market returns 0 without a special case. The profit line comes before the line that updates lowest, so each sale is priced against the days before it. (On day 0 lowest is the day's own price, and the profit is 0. Swapping the two lines gives the same answer, because a day that sets a new lowest price would earn 0 against itself.) The pass takes steps where the pairs took about , which is steps in place of .
The largest sum of consecutive values
The trading question can also be asked about how the price changes from each day to the next:
price 7 1 5 3 6 4change -6 +4 -2 +3 -2If you buy on day 1 and sell on day 4, you earn the three changes in between, . So when some trade makes a profit, the profit of the best trade is the largest sum of consecutive changes. Consecutive values of an array form a subarray, which we will also call a run. The next problem asks for the largest sum of a run in any list of numbers:
You get a list of integers nums. Among its subarrays of one or more values, find the one with the largest sum, and return that sum.
Constraints
Sample 1 · Input
nums = [-2,1,-3,4,-1,2,1,-5,4]
Output
6
Sample 2 · Input
nums = [1]
Output
1
Sample 3 · Input
nums = [5,4,-1,7,8]
Output
23
The problem is only hard when some values are negative. If every value were positive, the answer would be the sum of the whole array.
A run is fixed by its first and last positions, which can be the same position, so values have runs. For values that is 5,000,050,000, again about 50 seconds of work even at one step per run.
As with the sell day, we fix one end. Let the run end at position . A run that ends there is one of two kinds:
- the value at position alone;
- a run that ends at position , followed by the value at position .
In the second kind, adding the value at changes the sum of every run that ends at by the same amount, so the best choice extends the run ending at with the largest sum. If we work through the positions in order, we already know that sum when we reach . So the best sum of a run ending at takes one addition and one comparison:
Here is the calculation for the five changes:
| Position | Value | Extending the run before | Best ending here | Best so far |
|---|---|---|---|---|
| 0 | no run before | |||
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 |
At position 1 the run before has a negative sum, so the 4 does better alone and a new run starts there. At position 2 the run continues through the , because 2 is more than alone. Every run ends at some position, so the answer is the largest number in the "Best ending here" column: 5, the profit from the last part.
Kadane’s algorithm for the maximum subarray sum
This one-pass method is called Kadane's algorithm. The widget runs it on the five changes, and you can change the values: try -3, -1, -2, where every value is negative, and the problem's first sample, -2, 1, -3, 4, -1, 2, 1, -5, 4.
def max_subarray(nums):
ending_here = best = nums[0]
for k in range(1, len(nums)):
ending_here = max(nums[k], ending_here + nums[k])
best = max(best, ending_here)
return best
print(max_subarray([-6, 4, -2, 3, -2]))
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print(max_subarray([1]))
print(max_subarray([5, 4, -1, 7, 8]))Prints 5, then 6, 1 and 23 for the samples.
Both variables start at nums[0] and the loop starts at position 1, because a run holds at least one value. Starting them at 0 would allow a run of no values, the counterpart of not trading, and [-3, -1, -2] would return 0 where this problem's answer is , its largest single value. The pass takes steps.
Rearrange an array in place with a write position
The two passes so far only read the array. Move Zeroes asks us to rearrange it: [0, 4, 0, 7, 2], for example, has to become [4, 7, 2, 0, 0], with the zeros at the end and the other values in their original order.
You get a list of integers nums. Move every 0 to the end while keeping the other values in their original order.
Change nums in place, without making a copy of it. The function returns nothing; the judge reads nums afterwards.
Constraints
Sample 1 · Input
nums = [0,1,0,3,12]
Output
[1,3,12,0,0]
Sample 2 · Input
nums = [0]
Output
[0]
To change an array in place is to move values around inside the array you were given, without building a second one. The judge looks at the list it passed in, so the function has to write into that list with nums[i] = …. Giving the name nums a new list would leave the judge's list as it was.
The first method to try removes each zero and appends a 0. A removal moves every later value one slot left, so if the first half of a 10,000-value array is zeros, that is 5,000 removals of almost 10,000 moves each, about moves. At this problem's limit of values, that took a few milliseconds on our laptop. But the cost grows with , and a million values would take moves.
Each value can go straight to its final slot instead. Read the array from left to right, and keep a second index, write, for the slot where the next nonzero value belongs. A zero is skipped. A nonzero value is copied to slot write, and write moves one slot right. After the last value, every slot from write to the end is set to 0.
Worked example
Step through the read and write positions
The trace runs this on [0, 4, 0, 7, 2]. The other presets are three cases to check:
- zeros at the front, where
writewaits at slot 0; - a negative value, which is not zero and is kept;
- no zeros at all, where every value is copied onto itself.
Keep the nonzero values in their original order. write marks the next free output position.
- write
- 0
Change the example input
Current result: [4,7,2,0,0]
def move_zeroes(nums):
write = 0
for value in nums:
if value != 0:
nums[write] = value
write += 1
for i in range(write, len(nums)):
nums[i] = 0
nums = [0, 4, 0, 7, 2]
move_zeroes(nums)
print(nums)Prints [4, 7, 2, 0, 0].
Loop invariant
The slots before write hold exactly the nonzero values read so far, in their original order.
A loop invariant is a statement that is true before the first step and that every step keeps true. At the start nothing has been read and no slot is before write, so the statement holds. Skipping a zero changes neither the slots before write nor the list of nonzero values read. A nonzero value is copied to slot write and write moves right, so the value joins the end of the slots before write, and it is also the latest nonzero value read. Either way the statement still holds.
The copy never destroys a value the pass still needs. write goes up by at most one for each value the loop reads, so it never gets ahead of the loop, and the slot being written has already been read. After the last value, the slots before write hold every nonzero value in order, and the zeros fill the rest. That takes steps and one index of extra memory.
Deeper read: writing ahead of the read position in a grid
Move Zeroes is safe because its writes stay behind its reads. In the next problem, the obvious one-pass method writes ahead of its reads. It is set on a grid, a two-dimensional array in which matrix[r][c] is the value in row and column . Take a 3 by 3 grid of 1s with a single 0 in the middle. Every row and every column that holds a 0 has to become all 0s, so here the middle row and the middle column are cleared.
You get an grid of integers matrix. Wherever a cell holds 0, set its entire row and its entire column to 0. Change the grid in place.
Constraints
Sample 1 · Input
matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output
[[1,0,1],[0,0,0],[1,0,1]]
Sample 2 · Input
matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output
[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Suppose the pass reads the grid row by row and clears a row and a column the moment it reads a 0. On the 3 by 3 grid, the 0 in the middle clears the four cells beside it, and two of them, the one to its right and the one below it, have not been read yet. When the pass reaches them, it cannot tell a 0 that it wrote from a 0 that was given, so it clears their rows and columns too:
clearing at once correct1 0 0 1 0 10 0 0 0 0 00 0 0 1 0 1The fix is to keep the reading apart from the writing. A first pass changes nothing and records which rows and which columns hold a 0. A second pass sets a cell to 0 when its row or its column was recorded.
def set_zeroes(matrix):
rows, cols = len(matrix), len(matrix[0])
zero_row = [False] * rows
zero_col = [False] * cols
for r in range(rows):
for c in range(cols):
if matrix[r][c] == 0:
zero_row[r] = True
zero_col[c] = True
for r in range(rows):
for c in range(cols):
if zero_row[r] or zero_col[c]:
matrix[r][c] = 0
matrix = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
set_zeroes(matrix)
print(matrix)Prints [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]], the second sample's answer.
On a 200 by 200 grid, the largest the problem allows, the two passes visit cells, and the record holds marks.
Deeper read: Set Matrix Zeroes in constant extra space
The follow-up to Set Matrix Zeroes asks for a constant amount of extra memory, so the 400 marks need another place to live. The grid's own first row and first column can hold them: a 0 in matrix[0][c] marks column , and a 0 in matrix[r][0] marks row . The steps, in order:
- Record in two variables whether row 0 holds a 0 and whether column 0 holds a 0, because the marks are about to overwrite cells there.
- For every cell outside row 0 and column 0 that holds a 0, write its two marks:
matrix[r][0] = 0andmatrix[0][c] = 0. - Set every cell outside row 0 and column 0 to 0 if
matrix[r][0]ormatrix[0][c]is 0. - Clear row 0 if the first variable says it held a 0, and column 0 if the second says so.
Step 4 comes last because clearing row 0 or column 0 earlier would erase marks that step 3 still reads. A 0 that was in row 0 from the start already works as a mark, since its column has to be cleared anyway, and the same goes for column 0.
Split an array into three regions in one pass
The write position split the array into two regions, the values kept and the rest. With more indices of the same kind, one pass can split an array into three. The usual example is an array that holds only the values 0, 1 and 2 and has to be sorted:
You get a list nums of values, each 0, 1 or 2 (red, white and blue). Sort it in place without the library sort.
Constraints
- is 0, 1 or 2
Sample 1 · Input
nums = [2,0,2,1,1,0]
Output
[0,0,1,1,2,2]
Sample 2 · Input
nums = [2,0,1]
Output
[0,1,2]
You could count the 0s, 1s and 2s and write the array again from the three counts. That takes two passes, and it works because one 0 is the same as any other 0. If the values were labels on larger items, such as tasks marked with priority 0, 1 or 2, rewriting the labels would lose the tasks, and the items themselves would have to move. The method below moves them, by swapping, in a single pass.
It keeps three indices, low, mid and high. They cut the array into a region for each of the three values and a fourth region for the values not read yet:
- before
low, the 0s; - from
lowup tomid, withoutmiditself, the 1s; - from
midtohigh, both included, the values not read yet; - after
high, the 2s.
At the start nothing has been read, so low and mid are 0 and high is the last index. The pass ends when the unread region is empty, which leaves the three sorted regions.
Each step reads nums[mid], the first value not read yet, and puts it in its region:
- A 0 is swapped with
nums[low], andlowandmidboth move right. The value that comes back fromlowis a 1, or the 0 itself whenlowequalsmid, somidcan step past it. - A 1 is already at the end of the 1s, so
midmoves right. - A 2 is swapped with
nums[high], andhighmoves left.midstays where it is, because the value that came back fromhighhas not been read.
Trace Sort Colors on its first sample
Here is the pass on the first sample, [2, 0, 2, 1, 1, 0]. A value remains unread while mid is at most high, so that is the loop's condition.
| Step | low, mid, high | nums[mid] | Action | Array after |
|---|---|---|---|---|
| 1 | 0, 0, 5 | 2 | Swap indices 0 and 5; high becomes 4 | [0, 0, 2, 1, 1, 2] |
| 2 | 0, 0, 4 | 0 | Swap index 0 with itself; low and mid become 1 | [0, 0, 2, 1, 1, 2] |
| 3 | 1, 1, 4 | 0 | Swap index 1 with itself; low and mid become 2 | [0, 0, 2, 1, 1, 2] |
| 4 | 2, 2, 4 | 2 | Swap indices 2 and 4; high becomes 3 | [0, 0, 1, 1, 2, 2] |
| 5 | 2, 2, 3 | 1 | mid becomes 3 | [0, 0, 1, 1, 2, 2] |
| 6 | 2, 3, 3 | 1 | mid becomes 4, past high | [0, 0, 1, 1, 2, 2] |
Step 1 brings a 0 back from the end, and because mid did not move, step 2 reads it. Every step moves mid right or high left, so the unread region loses one value per step and the pass ends after exactly steps, six here.
def sort_colors(nums):
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
nums = [2, 0, 2, 1, 1, 0]
sort_colors(nums)
print(nums)Prints [0, 0, 1, 1, 2, 2].
Common array mistakes
Reading the slot after the last one.
- Where it breaks
- A loop that compares
a[i]witha[i + 1]for everyiup to readsa[n]on its last turn. Python stops withIndexError: list index out of range. C++ does not check the index. It reads whatever is stored past the block, and the program can print a wrong answer with no error. - The fix
- End the loop at , so that is at most .
Moving
midforward after swapping withhighin Sort Colors.- Where it breaks
[1, 2, 0]ends as[1, 0, 2]: the 0 that came back from the end is never read.- The fix
- After a swap with
high, move onlyhigh.
Changing a copy when the problem asks you to change the input.
- Where it breaks
- In Move Zeroes, the Python line
nums = [x for x in nums if x != 0] + [0] * nums.count(0)points the namenumsat a new list, and a C++ parameter writtenvector<int> nums, without the&, is a copy. Either way the judge still sees[0, 4, 0, 7, 2]. - The fix
- Write into the array you were given, slot by slot, and keep the
&on the C++ parameter.
Further reading
- USACO Guide, BronzeIntroduction to Data Structures(opens in a new tab)
The module that this page's parts on storage follow: dynamic arrays in C++, Java and Python, a run of insertions and erasures with their costs, pairs and tuples, and how many values fit in a memory limit.
- Antti Laaksonen (PDF)Competitive Programmer’s Handbook, section 2.4: Maximum subarray sum(opens in a new tab)
Three solutions to the maximum subarray problem, , and , with measured running times up to . Its version allows the empty subarray, so its variables start at 0.
- WikipediaDynamic array(opens in a new tab)
Capacity and geometric expansion, the amortized argument from this lesson, and a table of the growth factors real libraries use.
- cppreferencestd::vector(opens in a new tab)
The C++ dynamic array: the cost of each operation,
sizeagainstcapacity, and when a reallocation invalidates references to its elements. - WikipediaDutch national flag problem(opens in a new tab)
Dijkstra’s three-way partition, the algorithm behind Sort Colors, with pseudocode whose indices , and play the roles of
low,midandhigh. - Pat MorinOpen Data Structures, Chapter 2: Array-Based Lists(opens in a new tab)
Section 2.1 builds a list on an array that doubles when full and shrinks when mostly empty, and proves that all the resizing in insertions and removals costs ; Section 2.2 speeds up the shifting with block-copy routines. Parts of this page adapt this chapter’s text, licensed CC BY 2.5 Canada (creativecommons.org/licenses/by/2.5/ca), with changed wording, examples and code.