DSA · Chapter 5 of 40
Common Array Problems
A handful of array patterns cover a large share of interview questions: running a single pass to accumulate something, using a hash map to remember what you have seen, and using two pointers on a sorted array.
Recognising the pattern is the real skill — the code is usually short once you know which pattern applies.
Two Sum with a hash map
Store each number's index as you scan. For every number check whether target - number was already seen. This turns O(n^2) into O(n).
Kadane's algorithm
For the maximum subarray sum, keep a running sum and reset it to the current element whenever it becomes worse than starting fresh.
Example 1 (python)
def two_sum(nums, target):
seen = {}
for i, n in enumerate(nums):
if target - n in seen:
return [seen[target - n], i]
seen[n] = i
return []
print(two_sum([2, 7, 11, 15], 9))Output
[0, 1]One pass with a hash map gives O(n) time.
Example 2 (python)
def max_subarray(nums):
best = cur = nums[0]
for n in nums[1:]:
cur = max(n, cur + n)
best = max(best, cur)
return best
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))Output
6Kadane's algorithm solves maximum subarray in O(n).
Key points
- Hash maps remove nested loops in many array problems.
- Kadane's algorithm solves maximum subarray in O(n).
- Sorted input hints at two pointers or binary search.
- Always confirm whether duplicates are allowed.
💡 Note: State your brute-force idea first, then improve it — interviewers value that progression.