Arrays
Contiguous memory with instant indexing — the structure almost every other one is built on.
Big idea
An array keeps items side by side in one block, so reaching any index is instant — the default for scans, windows, and two pointers, while inserting or deleting in the middle shifts everything after it.
Think of it like
A school hallway lined with numbered lockers bolted together in one continuous row. If you know a locker's number, you walk straight to it without opening any of the others. Walking the row end to end, or sending two friends inward from opposite ends, is just as easy. But squeezing a new locker in between numbers 12 and 13 means unbolting every locker after it and sliding each one down a place.
Spotting an array problem
| Clue in the problem | Usually means |
|---|---|
| "subarray", "contiguous", "consecutive" | a window or a running sum — see sliding window, prefix sums |
| "sorted array", "pair that sums to" | two pointers or binary search |
| "in place", "O(1) extra space" | swap and overwrite with indices (lesson 3) |
| "maximum subarray sum" | Kadane's algorithm (lesson 4) |
| "find by value quickly" | an array alone is O(n) — add a hash map |
The array techniques with their own topics — two pointers, sliding window, prefix sums — come right after strings and hashing.
Lessons
- 1How arrays workOne block of memory, fixed-size slots, and the arithmetic that makes arr[i] instant.
- 2Inserting, deleting, and growingWhy the end of an array is cheap, the middle is expensive, and how dynamic arrays grow.
- 3In-place techniquesReverse, filter, and rotate an array using only a couple of indices — O(1) extra space.
- 4Maximum subarray (Kadane's algorithm)Find the best contiguous sum in one pass by deciding, at each item, whether to extend or restart.