Prefix Sum Interview Patterns: Subarray Sum, 2D Range Query, Product

Prefix Sum Interview Patterns

Prefix sums transform range sum queries from O(n) to O(1) after O(n) preprocessing. They also underlie subarray sum problems, equilibrium index, and 2D range queries. A fundamental technique used in almost every array interview problem.

1D Prefix Sum

def build_prefix(nums: list[int]) -> list[int]:
    prefix = [0] * (len(nums) + 1)   # prefix[0] = 0
    for i, n in enumerate(nums):
        prefix[i + 1] = prefix[i] + n
    return prefix

def range_sum(prefix: list[int], l: int, r: int) -> int:
    """Sum of nums[l..r] inclusive (0-indexed)."""
    return prefix[r + 1] - prefix[l]
# Build O(n), query O(1)

Pattern 1: Subarray Sum Equals K (LeetCode 560)

from collections import defaultdict

def subarray_sum(nums: list[int], k: int) -> int:
    count   = 0
    prefix  = 0
    seen    = defaultdict(int)
    seen[0] = 1   # empty prefix sums to 0

    for n in nums:
        prefix += n
        count  += seen[prefix - k]   # how many times prefix - k appeared
        seen[prefix] += 1

    return count
# Key insight: sum(l..r) = prefix[r] - prefix[l-1] = k
#              => prefix[r] - k = prefix[l-1]
# O(n) time, O(n) space

Pattern 2: Continuous Subarray Sum (LeetCode 523)

def check_subarray_sum(nums: list[int], k: int) -> bool:
    """Does any subarray of length >= 2 have sum divisible by k?"""
    seen    = {0: -1}   # remainder -> first index
    prefix  = 0

    for i, n in enumerate(nums):
        prefix = (prefix + n) % k
        if prefix in seen:
            if i - seen[prefix] >= 2:
                return True
        else:
            seen[prefix] = i

    return False
# Insight: sum(l..r) % k == 0 iff prefix[r] % k == prefix[l-1] % k

Pattern 3: Longest Subarray with Sum <= K (Sliding Window + Prefix)

def longest_subarray_sum_at_most_k(nums: list[int], k: int) -> int:
    prefix = 0
    max_len = 0
    min_prefix = {0: -1}   # prefix_sum -> earliest index

    for i, n in enumerate(nums):
        prefix += n
        target  = prefix - k
        # Binary search on sorted prefix sums (or use monotone deque)
        # For non-negative nums: sliding window is cleaner
        for j, p in min_prefix.items():
            if p <= target:
                max_len = max(max_len, i - p)
        min_prefix[prefix] = min(min_prefix.get(prefix, i), i)

    return max_len

Pattern 4: Equilibrium Index

def equilibrium_index(nums: list[int]) -> int:
    total = sum(nums)
    left  = 0
    for i, n in enumerate(nums):
        # left sum = left; right sum = total - left - nums[i]
        if left == total - left - n:
            return i
        left += n
    return -1

Pattern 5: Product of Array Except Self (LeetCode 238)

def product_except_self(nums: list[int]) -> list[int]:
    n      = len(nums)
    result = [1] * n

    # Left prefix products
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix   *= nums[i]

    # Right suffix products (multiply into result in-place)
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix    *= nums[i]

    return result
# O(n) time, O(1) extra space (output array not counted)

Pattern 6: Subarray with Equal 0s and 1s (LeetCode 525)

def find_max_length(nums: list[int]) -> int:
    """Longest subarray with equal 0s and 1s."""
    # Replace 0 with -1; find longest subarray with sum = 0
    seen    = {0: -1}
    prefix  = 0
    max_len = 0

    for i, n in enumerate(nums):
        prefix += 1 if n else -1
        if prefix in seen:
            max_len = max(max_len, i - seen[prefix])
        else:
            seen[prefix] = i

    return max_len

2D Prefix Sum

def build_2d_prefix(matrix: list[list[int]]) -> list[list[int]]:
    rows, cols = len(matrix), len(matrix[0])
    prefix = [[0] * (cols + 1) for _ in range(rows + 1)]

    for r in range(1, rows + 1):
        for c in range(1, cols + 1):
            prefix[r][c] = (matrix[r-1][c-1]
                          + prefix[r-1][c]
                          + prefix[r][c-1]
                          - prefix[r-1][c-1])
    return prefix

def range_sum_2d(prefix, r1, c1, r2, c2) -> int:
    """Sum of matrix[r1..r2][c1..c2] (0-indexed)."""
    return (prefix[r2+1][c2+1]
          - prefix[r1][c2+1]
          - prefix[r2+1][c1]
          + prefix[r1][c1])

Prefix Sum Decision Guide

Problem signal	Technique
Range sum query (static array)	1D prefix sum, O(1) query
Subarray sum = K	Prefix sum + hashmap of seen sums
Subarray sum divisible by K	Prefix sum modulo K + hashmap
Longest subarray with property	Prefix sum + hashmap (earliest index per sum)
Equal 0s and 1s (or X and Y)	Map 0→-1, find subarray with sum=0
Product of array except self	Left prefix product × right suffix product
Matrix region sum query	2D prefix sum, O(1) query

Asked at: Meta Interview Guide

Asked at: Apple Interview Guide

Asked at: Coinbase Interview Guide

Asked at: Atlassian Interview Guide