Coding Prep
Arrays
The most fundamental data structure - contiguous memory, O(1) access, and the three patterns (two pointers, sliding window, prefix sums) that unlock most array interview problems.
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.
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.
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.
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.Canonical examples
Two Sum
Given an array of integers and a target, return indices of the two numbers that add up to the target. As you scan left to right, for each element you need its complement (target minus current). A hash map of values seen so far gives that O(1) lookup - no nested loop needed.
Maximum subarray (Kadane's)
Find the contiguous subarray with the largest sum. Kadane's insight: at each position, either extend the running subarray or abandon it and start fresh here. Extending is better only when the running sum is positive. A single global max tracks the best seen.
current_sum + num < num - that means the running subarray has become a net negative drag. Restarting at num alone is always better than extending a negative-sum prefix.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.
Practice problems
- Two Sum - Complement lookup via hash map; the gateway array problem.
- Maximum Subarray - Kadane's in its purest form.
- Best Time to Buy and Sell Stock - Single-pass running minimum; a sliding window variant.
- Product of Array Except Self - Prefix and suffix products; O(1) extra space.
- Container With Most Water - Opposite-ends two pointers; move the shorter side.
Done reading? Mark it so it sticks in your dashboard.