Array Techniques
Seven small, sharp tools — prefix sums, Kadane's, cyclic sort, Dutch flag, Boyer‑Moore, difference arrays, matrix walks. Each turns a quadratic brute force into a linear pass with O(1) tricks, usually by using the array's own indices as free storage.
Seven tools, one lookup table
| Technique | Use case | Time / Space |
|---|---|---|
| Prefix Sum | Range sum queries, subarray sums | O(n) / O(n) |
| Difference Array | Efficient range updates | O(n) / O(n) |
| Kadane's | Maximum subarray | O(n) / O(1) |
| Cyclic Sort | Arrays with values in [1, n] | O(n) / O(1) |
| Dutch National Flag | Three-way partition | O(n) / O(1) |
| Boyer-Moore Vote | Majority element | O(n) / O(1) |
| Matrix Operations | Rotate, spiral, set zeroes | varies |
How to recognize which tool
- "Subarray sum equals K" → prefix sum + hash map
- "Range sum query" → prefix sum
- "Product of array except self" → left/right products
- "Maximum subarray" → Kadane's
- Values are in range 1 to n → cyclic sort
- "Rotate matrix 90 degrees" → transpose + reverse
- "Spiral order" → boundary tracking
Precompute once, query in O(1)
Store cumulative sums so any range sum becomes a subtraction. The convention
prefix[i] = sum of the first i elements (with prefix[0] = 0)
makes the range formula clean.
class PrefixSum:
def __init__(self, nums):
self.prefix = [0]
for num in nums:
self.prefix.append(self.prefix[-1] + num)
def range_sum(self, i, j):
"""Sum of nums[i..j] inclusive."""
return self.prefix[j + 1] - self.prefix[i]LC 560Subarray Sum Equals K
Key insight: if prefix[j] - prefix[i] == k, then sum(i..j-1) == k.
So while scanning, count how many earlier prefixes equal
curr_sum - k — a hash map makes that O(1).
def subarray_sum(nums, k):
count = 0
curr_sum = 0
prefix_counts = {0: 1} # Empty prefix has sum 0
for num in nums:
curr_sum += num
# How many previous prefixes had sum = curr_sum - k?
count += prefix_counts.get(curr_sum - k, 0)
prefix_counts[curr_sum] = prefix_counts.get(curr_sum, 0) + 1
return countLC 238Product of Array Except Self
Same prefix idea, multiplicative: build left products and right products, multiply them. No division needed.
def product_except_self(nums):
n = len(nums)
result = [1] * n
# Left pass
left = 1
for i in range(n):
result[i] = left
left *= nums[i]
# Right pass
right = 1
for i in range(n - 1, -1, -1):
result[i] *= right
right *= nums[i]
return resultInverseDifference array — O(1) range updates
The prefix sum's mirror image: to add a value to a whole range, bump the start, debit one past the end, and reconstruct with a single prefix-sum pass at the end. Perfect when there are many range updates and one final read.
def range_update(n, updates):
"""updates = list of (start, end, value)"""
diff = [0] * (n + 1)
for start, end, val in updates:
diff[start] += val
diff[end + 1] -= val
# Reconstruct
result = []
curr = 0
for i in range(n):
curr += diff[i]
result.append(curr)
return resultExtend or start fresh
Maximum-sum subarray in O(n). At each element there is exactly one decision: extend the running subarray, or restart at this element — whichever gives the bigger sum. A negative running sum can only hurt you, so drop it.
def max_subarray(nums):
curr_sum = max_sum = nums[0]
for num in nums[1:]:
curr_sum = max(num, curr_sum + num)
max_sum = max(max_sum, curr_sum)
return max_sumVariant — track the indices too
def max_subarray_with_indices(nums):
curr_sum = max_sum = nums[0]
start = end = temp_start = 0
for i in range(1, len(nums)):
if nums[i] > curr_sum + nums[i]:
curr_sum = nums[i]
temp_start = i # Restart here
else:
curr_sum += nums[i]
if curr_sum > max_sum:
max_sum = curr_sum
start = temp_start
end = i
return max_sum, start, endCyclic sort — the array is its own hash map
When values are in range [1, n] (or [0, n−1]), each value has a "home" index:
value − 1. Swap every element to its home and anomalies — duplicates, missing
numbers — reveal themselves. O(n) time, zero extra space.
def cyclic_sort(nums):
i = 0
while i < len(nums):
correct = nums[i] - 1 # Where this value belongs
if nums[i] != nums[correct]:
nums[i], nums[correct] = nums[correct], nums[i]
else:
i += 1
return numsi that refuses to advance is amortized away.
LC 268Find Missing Number
def missing_number(nums):
"""Values in [0, n], one missing. Use math: expected - actual."""
n = len(nums)
return n * (n + 1) // 2 - sum(nums)LC 442Find All Duplicates — sign as a visited bit
Same family: use the sign at a value's home index as a free "seen it" marker.
def find_duplicates(nums):
"""Values in [1, n], some appear twice. Mark visited by negating."""
result = []
for num in nums:
idx = abs(num) - 1
if nums[idx] < 0:
result.append(abs(num)) # Seen before
else:
nums[idx] = -nums[idx] # Mark visited
return resultDutch flag & Boyer-Moore
LC 75Dutch National Flag — three-way partition
Sort an array of 0s, 1s, 2s in one pass with three pointers. Invariant: everything left of
lo is 0, everything right of hi is 2, and mid scans
the unknown middle.
def sort_colors(nums):
lo, mid, hi = 0, 0, len(nums) - 1
while mid <= hi:
if nums[mid] == 0:
nums[lo], nums[mid] = nums[mid], nums[lo]
lo += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else: # nums[mid] == 2
nums[mid], nums[hi] = nums[hi], nums[mid]
hi -= 1
# Don't advance mid -- swapped element needs checkingLC 169Boyer-Moore voting — majority element
The element that appears more than n/2 times survives a pairwise cancellation war. Keep a candidate and a count: matches vote +1, mismatches vote −1, and at count 0 a new candidate takes over. O(n) time, O(1) space.
def majority_element(nums):
candidate = count = 0
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
return candidateRotate, spiral, zero out
LC 48Rotate Image 90° clockwise
Two mechanical steps: transpose, then reverse each row. No cell-by-cell index juggling required.
def rotate(matrix):
n = len(matrix)
# Transpose
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Reverse each row
for row in matrix:
row.reverse()LC 54Spiral Matrix — four shrinking boundaries
Track top, bottom, left, right. Walk one edge,
shrink that boundary, repeat until the boundaries cross.
def spiral_order(matrix):
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
# Right
for col in range(left, right + 1):
result.append(matrix[top][col])
top += 1
# Down
for row in range(top, bottom + 1):
result.append(matrix[row][right])
right -= 1
# Left
if top <= bottom:
for col in range(right, left - 1, -1):
result.append(matrix[bottom][col])
bottom -= 1
# Up
if left <= right:
for row in range(bottom, top - 1, -1):
result.append(matrix[row][left])
left += 1
return resultLC 73Set Matrix Zeroes — first row/col as scratch space
Instead of an O(m + n) marker set, reuse the matrix's own first row and first column as the markers — after first recording whether they themselves contained a zero.
def set_zeroes(matrix):
m, n = len(matrix), len(matrix[0])
first_row_zero = any(matrix[0][j] == 0 for j in range(n))
first_col_zero = any(matrix[i][0] == 0 for i in range(m))
# Mark zeroes in first row/col
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# Zero out cells based on markers
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# Handle first row and column
if first_row_zero:
for j in range(n):
matrix[0][j] = 0
if first_col_zero:
for i in range(m):
matrix[i][0] = 0The four-step index dance
LC 31. Find the next lexicographic arrangement in place: locate the rightmost ascent, swap in the smallest larger element from the suffix, then reverse the suffix (which is descending, so reversing sorts it ascending — the smallest possible tail).
def next_permutation(nums):
n = len(nums)
# Step 1: find rightmost ascent
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
# Step 2: find rightmost element > nums[i]
j = n - 1
while nums[j] <= nums[i]:
j -= 1
# Step 3: swap
nums[i], nums[j] = nums[j], nums[i]
# Step 4: reverse suffix
left, right = i + 1, n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1Complexity reference
| Problem / Technique | Time | Space |
|---|---|---|
| Prefix Sum (build) | O(n) | O(n) |
| Prefix Sum (query) | O(1) | — |
| Subarray Sum Equals K | O(n) | O(n) |
| Product Except Self | O(n) | O(1)* |
| Kadane's Algorithm | O(n) | O(1) |
| Cyclic Sort | O(n) | O(1) |
| Dutch National Flag | O(n) | O(1) |
| Boyer-Moore Voting | O(n) | O(1) |
| Rotate Matrix | O(n²) | O(1) |
| Spiral Matrix | O(m·n) | O(1)* |
| Set Matrix Zeroes | O(m·n) | O(1) |
| Next Permutation | O(n) | O(1) |
* excluding the output array.
Where arrays bite back
prefix[j+1] - prefix[i], not prefix[j] - prefix[i].
The leading 0 in the prefix array exists precisely to make this work.
nums[0], not 0. Otherwise [-3, -1, -2]
returns 0 for a subarray that doesn't exist.
hi is unknown —
do NOT advance mid after that swap; inspect it again.
if top <= bottom, if left <= right)
or single-row / single-column matrices get double-visited.
Practice ladder
In this order — easiest first. Tick each one as you solve it, and re-solve anything that took more than 25 minutes two days later.