ASAPUtils
1. The physical picture
An array is one contiguous block of memory. Element i lives at base + i × elementSize, which
is a single multiply-and-add — that’s the entire reason indexing is O(1).
A dynamic array (vector<int>, a JS array) is that block plus a capacity. When you append
past the capacity, it allocates a bigger block (usually double), copies everything over, and frees
the old one. That copy is O(n), but it happens so rarely that the average append is O(1). That’s
amortised cost, and it’s why push_back is considered free.
2. The invariant
Elements occupy positions
0 .. size-1with no gaps, in the order you put them.
Everything expensive about arrays follows from maintaining “no gaps”: insert or delete in the middle and everything after it has to shift.
3. Operations and complexity
| Operation | Cost | Why |
|---|---|---|
Read/write a[i] | O(1) | Pointer arithmetic |
| Append at the end | O(1) amortised | Occasional doubling, spread out |
| Insert/delete at the end | O(1) | Nothing shifts |
| Insert/delete in the middle | O(n) | Everything after shifts |
| Search (unsorted) | O(n) | Must look at each |
| Search (sorted) | O(log n) | Binary search |
| Sort | O(n log n) |
4. C++ and JavaScript
vector<int> v; // dynamic array
v.push_back(5); // amortised O(1)
v.size(); v.empty(); v.back();
vector<vector<int>> g(R, vector<int>(C, 0)); // 2-D, all zeros
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
const v = [];
v.push(5); // amortised O(1)
v.length;
const g = Array.from({ length: R }, () => Array(C).fill(0));
v.sort((a, b) => a - b); // ALWAYS pass a comparator
v.reverse();
Two traps worth burning in: [10, 9, 1].sort() gives [1, 10, 9] in JavaScript because the
default sort is lexicographic; and Array(R).fill(Array(C).fill(0)) gives you R references to
the same row, so writing one cell writes them all.
5. How you travel it
- Forward walk —
for (i = 0; i < n; i++). The default. - Backward walk — when writing in place and you don’t want to clobber unread data.
- Two ends inward —
l = 0, r = n-1, the two-pointer pattern. - Two passes — left-to-right then right-to-left, which is how Product of Array Except Self avoids division.
- Fast and slow — one index moves every step, the other only when a condition holds. This is the “write pointer” idea behind every in-place removal problem.
6. It’s the answer when…
- You need order, or you need to index by position.
- Keys are small dense integers — a
int freq[26]frequency array beats a hash map for lowercase letters, on both speed and readability. - The problem says “in place” or “O(1) extra space”.
- You’re about to sort, because sorting unlocks two pointers and binary search.
7. The three classic mistakes
- Shifting in a loop. Deleting k elements one at a time from the middle is O(n·k). Build the result with a write pointer instead, in one pass.
- Off-by-one at the boundaries.
n-1vsn, and<vs<=. Write the invariant (see loops and index arithmetic) instead of guessing. - Assuming the input is sorted. Read the constraints. If it isn’t and you need order, sorting costs O(n log n) — and destroys the original indices, which matters when the answer is indices rather than values.
8. What to drill
Reverse in place, rotate by k, remove duplicates from a sorted array in place, move zeroes to the end, and merge two sorted arrays. All O(1) space, all with a written invariant. They take an hour and they de-risk the entire rest of the quarter.