Array Algorithms and Techniques
One block of memory, indexed from zero, and everything that follows from that.
Array: Visit every slot
An array is a run of equally sized slots laid next to each other in memory. That one decision is why reading a[i] costs the same whatever i is, and why inserting in the middle does not: the slots after it all have to move up by one.
Most array technique is about avoiding that move, or about reading the array fewer times. Two pointers walk in from the ends instead of trying every pair. A sliding window keeps a running answer instead of recomputing it. A prefix sum pays once so every range query afterwards is a subtraction.
Because the layout is so simple, arrays are also where complexity first becomes visible: you can watch a nested loop touch n squared cells, and watch a single pass touch n.
After this you can
- Say what an index costs, and what an insert in the middle costs, and why
- Choose between a second pass, a second array, and an in-place rearrangement
- Recognise when two pointers or a sliding window replaces a nested loop
- Use a prefix sum to turn repeated range questions into one subtraction
In this order
Also in this category
Where people go wrong
Off by one at the ends
The last index is n - 1, and a range that includes both ends has to - from + 1 elements. Most array bugs are one of these two, not the algorithm.
Growing an array inside a loop
A dynamic array doubles its capacity and copies, so appending is cheap on average but not every time. Building a result by repeatedly inserting at the front is quadratic. Build it backwards or push and reverse.