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

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.