Advanced Array Interview Patterns
Mastering a handful of array techniques unlocks dozens of LeetCode problems. This guide covers the six most important patterns tested at top companies in 2025.
1. Prefix Sum
Precompute prefix[i] = sum of arr[0..i-1] (with prefix[0] = 0). A range sum query [l, r] then answers in O(1):
prefix[r+1] - prefix[l]Build time: O(n). Query time: O(1). Space: O(n).
Python Implementation
def build_prefix(arr):
prefix = [0] * (len(arr) + 1)
for i, v in enumerate(arr):
prefix[i + 1] = prefix[i] + v
return prefix
def range_sum(prefix, l, r):
return prefix[r + 1] - prefix[l]
2D Prefix Sum
For rectangle sum queries on a matrix, extend to two dimensions:
def build_2d_prefix(matrix):
m, n = len(matrix), len(matrix[0])
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = (matrix[i-1][j-1]
+ dp[i-1][j]
+ dp[i][j-1]
- dp[i-1][j-1])
return dp
def rect_sum(dp, r1, c1, r2, c2):
return (dp[r2+1][c2+1]
- dp[r1][c2+1]
- dp[r2+1][c1]
+ dp[r1][c1])
Key problems: LC 303 (Range Sum Query – Immutable), LC 304 (2D Range Sum Query).
2. Difference Array
When you need many range-update operations (add val to arr[l..r]) followed by a read pass, the difference array gives O(1) per update and O(n) reconstruction.
def apply_range_updates(n, updates):
diff = [0] * (n + 1)
for l, r, val in updates:
diff[l] += val
diff[r + 1] -= val
# reconstruct
result = []
cur = 0
for i in range(n):
cur += diff[i]
result.append(cur)
return result
Key problem: LC 1109 (Corporate Flight Bookings).
3. Kadane’s Algorithm
Maximum subarray sum in O(n):
def max_subarray(nums):
max_sum = cur = nums[0]
for n in nums[1:]:
cur = max(n, cur + n)
max_sum = max(max_sum, cur)
return max_sum
Key problem: LC 53 (Maximum Subarray).
Variant: Maximum Circular Subarray (LC 918)
The answer is either the maximum subarray in the linear array, or the total sum minus the minimum subarray (wrapping case):
def max_circular_subarray(nums):
total = sum(nums)
max_sum = max_cur = nums[0]
min_sum = min_cur = nums[0]
for n in nums[1:]:
max_cur = max(n, max_cur + n)
max_sum = max(max_sum, max_cur)
min_cur = min(n, min_cur + n)
min_sum = min(min_sum, min_cur)
if max_sum < 0:
return max_sum # all negatives
return max(max_sum, total - min_sum)
Variant: Maximum Subarray Product (LC 152)
Track both max and min at each position because a negative times a negative flips to a large positive:
def max_product(nums):
res = max_p = min_p = nums[0]
for n in nums[1:]:
candidates = (n, max_p * n, min_p * n)
max_p, min_p = max(candidates), min(candidates)
res = max(res, max_p)
return res
4. Two-Pointer Techniques on Sorted Arrays
Two pointers starting from opposite ends solve several classic problems in O(n):
Container With Most Water (LC 11)
def max_area(height):
l, r = 0, len(height) - 1
best = 0
while l < r:
best = max(best, (r - l) * min(height[l], height[r]))
if height[l] < height[r]:
l += 1
else:
r -= 1
return best
Trapping Rain Water (LC 42)
def trap(height):
l, r = 0, len(height) - 1
left_max = right_max = water = 0
while l < r:
if height[l] <= height[r]:
left_max = max(left_max, height[l])
water += left_max - height[l]
l += 1
else:
right_max = max(right_max, height[r])
water += right_max - height[r]
r -= 1
return water
5. Dutch National Flag (3-Way Partition)
Sort an array of 0s, 1s, and 2s in one pass with O(1) space (LC 75 Sort Colors):
def sort_colors(nums):
lo = mid = 0
hi = 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], nums[hi] = nums[hi], nums[mid]
hi -= 1
Invariant: nums[0..lo-1] == 0, nums[lo..mid-1] == 1, nums[hi+1..n-1] == 2.
6. Jump Game Variants
LC 55 – Can Reach End?
Track the furthest reachable index greedily:
def can_jump(nums):
reach = 0
for i, v in enumerate(nums):
if i > reach:
return False
reach = max(reach, i + v)
return True
LC 45 – Minimum Jumps
def jump(nums):
jumps = cur_end = cur_far = 0
for i in range(len(nums) - 1):
cur_far = max(cur_far, i + nums[i])
if i == cur_end:
jumps += 1
cur_end = cur_far
return jumps
Complexity Summary
| Pattern | Build | Query/Update | Space |
|---|---|---|---|
| Prefix Sum | O(n) | O(1) query | O(n) |
| 2D Prefix Sum | O(mn) | O(1) query | O(mn) |
| Difference Array | O(n) | O(1) update, O(n) reconstruct | O(n) |
| Kadane | – | O(n) | O(1) |
| Two Pointer | – | O(n) | O(1) |
| Dutch National Flag | – | O(n) | O(1) |
| Jump Game Greedy | – | O(n) | O(1) |
Interview Tips
- Prefix sum is the default tool any time you see repeated range sum queries – build it before the loop.
- Difference array pairs with prefix sum: use it when updates are more frequent than reads.
- For Kadane variants, draw out the recurrence explicitly before coding – interviewers want to see you derive it.
- Dutch National Flag invariant is easy to mess up at boundaries; state the invariant out loud before coding.
- Jump Game greedy: the key insight is that you only increment jumps when you exhaust the current jump range.