Prefix Sum Interview Patterns

By /
⏱ 5 min read

Core Idea

Build a prefix array where prefix[i] = arr[0] + arr[1] + ... + arr[i-1]. Then any range sum arr[l..r] = prefix[r+1] - prefix[l] in O(1). Build is O(n), queries are O(1).

def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i, v in enumerate(arr):
        prefix[i+1] = prefix[i] + v
    return prefix

# Range sum arr[l..r] (inclusive, 0-indexed)
def range_sum(prefix, l, r):
    return prefix[r+1] - prefix[l]

Subarray Sum Equals K (LC 560)

Count subarrays whose sum equals k. Key insight: subarray_sum(i,j) = prefix[j] - prefix[i-1] = k iff prefix[i-1] = prefix[j] - k. Store prefix sum frequencies in a hashmap.

def subarray_sum(nums, k):
    count = 0
    curr = 0
    freq = {0: 1}  # empty prefix has sum 0
    for n in nums:
        curr += n
        count += freq.get(curr - k, 0)
        freq[curr] = freq.get(curr, 0) + 1
    return count

Time O(n), Space O(n). The {0: 1} initialization handles the case where a prefix itself equals k.

Subarray Sum Divisible by K (LC 974)

Count subarrays whose sum is divisible by k. Two prefix sums with the same remainder mod k form a valid subarray. Use ((curr % k) + k) % k to handle negative remainders in Python.

def subarraysDivByK(nums, k):
    count = 0
    curr = 0
    freq = {0: 1}
    for n in nums:
        curr = (curr + n) % k
        rem = (curr % k + k) % k
        count += freq.get(rem, 0)
        freq[rem] = freq.get(rem, 0) + 1
    return count

Continuous Subarray Sum (LC 523)

Check if any subarray of length ≥ 2 has a sum divisible by k. Store remainder → earliest index. If the same remainder appears at index j and previously at index i with j – i ≥ 2, the subarray nums[i+1..j] has sum divisible by k.

def checkSubarraySum(nums, k):
    seen = {0: -1}  # remainder -> first index
    curr = 0
    for i, n in enumerate(nums):
        curr = (curr + n) % k
        if curr in seen:
            if i - seen[curr] >= 2:
                return True
        else:
            seen[curr] = i
    return False

2D Prefix Sum (LC 304)

For rectangle sum queries on a matrix, build a 2D prefix array. prefix[i][j] = sum of all elements in the rectangle from (0,0) to (i-1,j-1).

# Build
for i in range(1, rows+1):
    for j in range(1, cols+1):
        prefix[i][j] = (matrix[i-1][j-1]
                        + prefix[i-1][j]
                        + prefix[i][j-1]
                        - prefix[i-1][j-1])

# Query rectangle (r1,c1) to (r2,c2)
def query(r1, c1, r2, c2):
    return (prefix[r2+1][c2+1]
            - prefix[r1][c2+1]
            - prefix[r2+1][c1]
            + prefix[r1][c1])

Inclusion-exclusion: add top-left corner back to undo double-subtraction.

Difference Array (Range Update)

For problems with many range updates (add val to arr[l..r]) and a single final read, use a difference array: diff[l] += val; diff[r+1] -= val. Apply prefix sum once to reconstruct the final array. O(1) per update, O(n) to reconstruct.

# LC 1094 Car Pooling / LC 1109 Corporate Flight Bookings
diff = [0] * (n + 1)
for val, l, r in trips:
    diff[l] += val
    diff[r+1] -= val  # r+1 because range is inclusive

result = list(itertools.accumulate(diff))

When to Reach for Prefix Sum

  • “Subarray with sum equal to k” → prefix sum + hashmap
  • “Range sum query, multiple queries” → 1D or 2D prefix array
  • “Count subarrays with property” → prefix sum + frequency map
  • “Range update then read all values” → difference array
  • “Divisibility by k” → prefix sum mod k + frequency map

Meta coding interviews frequently test prefix sum and subarray patterns. See common questions for Meta interview: prefix sum and subarray problems.

Google coding interviews test prefix sum and range query patterns. Review problems for Google interview: prefix sum and range query problems.

Atlassian coding rounds include prefix sum and range problems. See patterns for Atlassian interview: prefix sum and array manipulation problems.

Scroll to Top