Prefix Sum

Prefix sum is a powerful pre-processing/caching technique for algorithm problems. The idea is to calculate/store the consecutive totals of the elements in an array in O(n).

1
2
3
4
5
def prefix_sum(arr):
    result = [arr[0]]
    for num in arr[1:]:
        result.append(result[-1] + num)
    return result

Using the prefix_sum array, we can access the sum of a subarray defined by indexes start and end in O(1):

1
subarray_sum = prefix[end] - prefix[start]

Practice Problems

Median Leetcode 560. Subarray Sum Equals K
Hard Lintcode 1139. the kth subarray