Arrays

Prefix Sum

TimeO(n) SpaceO(n)

Think of a running odometer. If you want to know the distance between mile marker 30 and mile marker 50, you don’t re-drive it — you just subtract: 50 - 30 = 20 miles. A prefix sum array is your odometer reading at every point.

When to use it: You need to answer multiple range-sum queries, or you need to find subarrays with a specific sum efficiently.

Key insight: The sum of any subarray arr[i..j] equals prefix[j+1] - prefix[i]. One subtraction replaces a full scan.

Common trap: Off-by-one errors. The prefix array has length n+1, with prefix[0] = 0. The sum of arr[i..j] inclusive is prefix[j+1] - prefix[i].

# Build prefix sum array
function buildPrefixSum(arr):
    prefix = array of length(arr) + 1
    prefix[0] = 0
    for i = 0 to length(arr) - 1:
        prefix[i + 1] = prefix[i] + arr[i]
    return prefix

# Query: sum of arr[left..right] inclusive
function rangeSum(prefix, left, right):
    return prefix[right + 1] - prefix[left]

# Count subarrays with sum equal to target
function subarraySum(arr, target):
    prefixCount = {0: 1}            # how many times each prefix sum occurred
    currentSum = 0
    count = 0

    for num in arr:
        currentSum = currentSum + num
        # If (currentSum - target) was a previous prefix sum,
        # then the subarray between them sums to target
        if (currentSum - target) in prefixCount:
            count = count + prefixCount[currentSum - target]
        prefixCount[currentSum] = prefixCount.get(currentSum, 0) + 1

    return count

def build_prefix_sum(arr: list[int]) -> list[int]:
    prefix = [0] * (len(arr) + 1)
    for i in range(len(arr)):
        prefix[i + 1] = prefix[i] + arr[i]
    return prefix


def range_sum(prefix: list[int], left: int, right: int) -> int:
    """Sum of arr[left..right] inclusive."""
    return prefix[right + 1] - prefix[left]


def subarray_sum(arr: list[int], target: int) -> int:
    """Count subarrays whose elements sum to target."""
    prefix_count = {0: 1}
    current_sum = 0
    count = 0

    for num in arr:
        current_sum += num
        count += prefix_count.get(current_sum - target, 0)
        prefix_count[current_sum] = prefix_count.get(current_sum, 0) + 1

    return count

Problem: Given an array of integers and a target integer k, find the total number of contiguous subarrays whose sum equals k.

How would you approach this?

Answer: This is a prefix sum with hash map problem. As you build the running sum, check if currentSum - k has been seen before. If so, there is a subarray ending here that sums to k. This is the classic "subarray sum equals k" pattern.

Problem: You are given an array and will receive many queries, each asking for the sum of elements between indices i and j. Preprocess the array to answer each query in O(1).

How would you approach this?

Answer: This is a prefix sum problem. Build a prefix sum array in O(n), then answer each query as prefix[j+1] - prefix[i] in O(1).

Time: O(n) to build the prefix sum array (one pass). Each subsequent range query is O(1) — just one subtraction. For the subarray-sum-equals-k variant, it is O(n) total with a single pass using a hash map.

Space: O(n) to store the prefix sum array. For the hash map variant, O(n) in the worst case to store all distinct prefix sums.