An array is the structure you will use most, so its price list is worth knowing by heart.
The price list#
| what you do | cost | why |
|---|---|---|
read nums[i] | O(1) | one multiply, one add |
write nums[i] | O(1) | same |
| add at the end | O(1) usually | there is normally room |
| insert or remove in the middle | O(n) | everything after it shuffles |
| insert or remove at the front | O(n) | everything shuffles |
| search an unsorted array | O(n) | you have to look at all of it |
| search a sorted array | O(log n) | you can halve the search each time |
Two of those deserve a closer look.
"Usually" constant at the end#
Adding to the end of a growable array is almost always instant, because there is spare room. When there is not, the array is copied into a bigger space, which costs O(n).
That sounds alarming until you count it properly. Each time the array fills up, its capacity doubles. Adding a million values means copying at 1, 2, 4, 8, ... up to a million, and all those copies added together come to under two million moves. Spread across a million additions, that is under two moves each.
This is called amortised constant time: any single addition might be slow, but a run of them averages out to cheap. It is why appending in a loop is fine and nobody worries about it.
Removing without shuffling#
Sometimes you do not need to keep the order. If you can live with rearrangement, removing from the middle is instant: move the last value into the gap and shorten the array by one.
[a, b, c, d, e] remove position 1
[a, e, c, d] e moved into b's place
One move instead of three. Worth remembering, and worth being certain the caller does not care about order.
The two pointer shape#
A great many array problems come down to walking two indexes over the same array rather than looping twice. Two common shapes:
One reading, one writing. Keep a write index that only advances when you keep a value. Removing duplicates from a sorted array and pushing zeroes to the end are both this, and both are one pass with no extra array.
One at each end, walking inward. Works when the array is sorted, or when the question is symmetric, like checking a palindrome.
Both are covered properly in their own lesson. The point here is that they cost nothing extra: no second array, and each index moves forward at most n times.
What to ask before you reach for an array#
- Do I need to look things up by position? Array.
- By key? Hash table.
- Do I insert and remove in the middle constantly? Linked list, probably.
- Do I only ever care about the largest or smallest? Heap.
Common mistakes#
- Removing items from an array while looping forward over it. Positions shift underneath you and you skip values. Loop backwards, or build a new array, or use a write index.
- Reaching for a nested loop when a single pass with two indexes would do.
- Assuming an array of
nvalues uses exactlynvalues' worth of memory. A growable one usually reserves spare room.