Foundations
Arrays
The data structure you already know. Most array problems are really about picking the right traversal pattern.
What is an array?
An array is a collection of elements stored in contiguous memory locations. Every element sits right next to the previous one, which means the computer can jump directly to any position by calculating a single memory address: base_address + index * element_size. That calculation is O(1), making random access one of the fastest operations in computing.
In Python, the built-in list is a dynamic array. It starts with some capacity, and when it fills up, Python allocates a new block roughly twice as large and copies everything over. This resizing happens infrequently enough that the amortized cost of append is still O(1).
The core trade-off: arrays give O(1) access by index and pay for it with O(n) insert/delete at arbitrary positions (every element after the target must shift). For sequential, index-driven access, nothing beats an array.
Core operations
| Operation | Time | Notes |
|---|---|---|
| Access by index | O(1) | The defining superpower of arrays |
| Search (unsorted) | O(n) | Must check every element |
| Search (sorted) | O(log n) | Binary search |
| Append | O(1) amortized | Occasional resizing is O(n) but rare |
| Insert at position i | O(n) | Shifts all elements after i |
| Delete at position i | O(n) | Shifts all elements after i |
| Delete last | O(1) | No shifting needed |
Key patterns
Two pointers
Two indices start at opposite ends of a sorted array and converge, each step moving the one that pushes the running sum toward the target.
When to use - the array is sorted (or you can sort it) and you are hunting for a pair or triplet that meets a condition: a target sum, the widest container, a palindrome check. A brute-force double loop is O(n²), but sortedness lets a single comparison decide which pointer to move, collapsing it to O(n).
How it works - the loop runs while left < right (never <=, since a pair never reuses one element). Each step moves exactly one pointer inward, and the two only ever travel toward each other, so together they advance at most n times: O(n), not O(n²). The comparison is valid only because the array is sorted - moving left rightward can only grow the sum, moving right leftward can only shrink it.
Example: pair summing to a target in a sorted array. Given [3, 8, 12, 19] and target 11, left starts on 3 and right on 19. The first sum 3 + 19 = 22 overshoots, so right moves to 12 and the sum drops to 15, still too big; the next move puts right on 8, where 3 + 8 = 11 hits the target and the answer is indices [0, 1]. Three comparisons instead of up to twelve in a double loop - the visualizer below steps through each one.
Sliding window
A sliding window keeps a contiguous run of elements and updates it in O(1) - add the element entering on the right, drop the one leaving on the left - instead of recomputing the whole window each step.
When to use - a contiguous subarray or substring where you want the longest, shortest, or best window of a fixed size k. Fixed-size windows slide by exactly one position; variable windows grow from the right and shrink from the left when an invariant breaks.
How it works - seed the first size-k window with one sum(), then each step add nums[end] and subtract nums[end - k]. The element that falls off is always at end - k, so you never track a separate start. Because each index enters and leaves the window exactly once, the whole scan is O(n) even though it reads like a nested loop.
Example: max sum of any window of size k. Given [1, 5, 0, 3, 2] and k = 2, the first window [1, 5] sums to 6, and that is already the answer - the three later windows score 5, 3, and 5, so best never moves. Each slide still costs one add and one subtract rather than a fresh two-element sum; the visualizer below runs the full trace.
nums[end - k] not nums[start] - for a fixed window, the leaving element is always at end - k. Tracking start separately is equivalent but end - k is the simpler formula.Prefix sums
A prefix-sum array precomputes cumulative totals so any range sum is one subtraction away.
When to use - you answer many range-sum queries over an array that does not change, or you need the sum of an arbitrary range [l, r] in constant time. You build the table once in O(n); every query after that is O(1).
How it works - prefix[i + 1] holds the sum of the first i + 1 elements, so the sum of [l, r] is prefix[r + 1] - prefix[l]. The array has length n + 1, not n: prefix[0] = 0 is the empty-prefix base case that keeps the formula correct when l = 0.
Example: range sum queries on a fixed array. Building the prefix array for [3, 1, 4, 1, 5] fills [0, 3, 4, 8, 9, 14], each cell one addition from its neighbor. The query sum(1, 3) - elements 1 + 4 + 1 = 6 - is then a single subtraction: prefix[4] - prefix[1] = 9 - 3 = 6. Build once in O(n), answer every later query in O(1); the visualizer shows the build step by step.
prefix has length n+1, not n - prefix[0] = 0 represents the empty prefix. This is the base case that lets prefix[r+1] - prefix[l] work correctly when l = 0.When to reach for an array
- The problem talks about a contiguous subarray, window, or range - sliding window or prefix sums.
- You need to find a pair or triplet satisfying a property - two pointers (if sorted) or hash map.
- You need fast indexed access by position - arrays beat everything else here.
- The problem says "rotate", "reverse", or "rearrange in-place" - classic array manipulation.
- You see "maximum sum subarray" or "minimum length subarray" - Kadane's or variable sliding window.
Done reading? Mark it so it sticks in your dashboard.