Overview
An array stores elements in one contiguous block of memory, so the address of element i is simply start + i × size. That arithmetic is why indexing is O(1) and why arrays are cache-friendly and fast in practice. The cost is rigidity: inserting or deleting in the middle shifts every element after it, which is O(n).
Most array problems are not about the array itself but about traversing it cleverly — keeping a running best, overwriting in place with a second index, or noticing that a matrix is just an array of arrays. Master the handful of moves below and a large share of "Easy" and "Medium" problems become routine.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| Access by index | O(1) |
| Search (unsorted) | O(n) |
| Append at end | O(1) amortised |
| Insert / delete in the middle | O(n) |
| Copy or slice of length k | O(k) |
Patterns to recognise
Running best
Use it for: Max profit, max subarray, running minimum.
Track the best answer so far and the best "state" ending at the current index in one pass.
Write pointer
Use it for: Remove elements, move zeroes, deduplicate.
Read every element; copy the keepers to position w and increment w.
Index as hash
Use it for: Values are in the range 1..n.
Use the sign or position of nums[v − 1] to mark that v was seen — O(1) extra space (first missing positive).
Code template
def max_subarray(nums):
best = current = nums[0]
for x in nums[1:]:
current = max(x, current + x) # extend or restart
best = max(best, current)
return best
int maxSubArray(const vector<int>& nums) {
int best = nums[0], current = nums[0];
for (size_t i = 1; i < nums.size(); ++i) {
current = max(nums[i], current + nums[i]); // extend or restart
best = max(best, current);
}
return best;
}
Common mistakes
- Off-by-one errors on loop bounds — test with arrays of length 0, 1 and 2.
- Removing items from a list while iterating over it skips elements; iterate over a copy or use a write pointer.
- Sums of large arrays overflow 32-bit integers.
- Python slicing (
a[1:]) copies the data — fine for clarity, but it costs O(n) memory.
Quick check
Three questions on Arrays. Get all three right to earn +15 XP.
-
What does it cost to insert a value at the front of an array of n elements?
Every existing element has to shift one place to the right.
-
Kadane's algorithm finds the maximum subarray sum. What does it decide at each element?
current = max(x, current + x): a negative running sum is never worth carrying forward.
-
What makes reading arr[i] an O(1) operation?
Address = base + i x element size. No searching is needed.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Best Time to Buy and Sell StockLeetCode Easy +20
- Move ZeroesLeetCode Easy +20
- Maximum SubarrayLeetCode Medium +40
- Rotate ArrayLeetCode Medium +40
- Spiral MatrixLeetCode Medium +40
- Set Matrix ZeroesLeetCode Medium +40
- First Missing PositiveLeetCode Hard +70
Stuck on Arrays?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor