# Advanced Array Interview Patterns: Prefix Sum, Difference Array, and Kadane’s Algorithm (2025)

Source: https://www.techinterview.org/post/3233466767/array-advanced-patterns/
Updated: 2026-04-17 · techinterview.org

## 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.