Prefix Sum | Engineering Interview Kit

Concept

A Prefix Sum (or Cumulative Sum) is an array where every element at index i stores the sum of all elements from index 0 up to i.

It is a powerful pre-processing technique. By spending $O(N)$ time and $O(N)$ space upfront to build the Prefix Sum array, you can answer any subsequent “Range Sum Query” (e.g., “What is the sum of items between index 2 and index 6?”) in blazing-fast $O(1)$ time.

Mental Model

Original Array: [2, 4, 1, 3]

Index 0: 2
Index 1: 2 + 4 = 6
Index 2: 6 + 1 = 7
Index 3: 7 + 3 = 10

Prefix Sum Array: [2, 6, 7, 10]

The Magic Math:
If an interviewer asks: “What is the sum of the original array from Index 1 to Index 3?”

Naive loop: 4 + 1 + 3 = 8. (Takes $O(N)$ time).
Prefix Sum math: Prefix[3] - Prefix[0].
10 - 2 = 8. (Takes $O(1)$ instant time).

We simply took the total running sum up to the end boundary (10), and mathematically chopped off the running sum of the items we didn’t want from the beginning (2).

Implementation

class RangeQuery {
    private prefix: number[];

    // O(N) Pre-processing
    constructor(nums: number[]) {
        this.prefix = new Array(nums.length);
        let currentSum = 0;
        
        for (let i = 0; i < nums.length; i++) {
            currentSum += nums[i];
            this.prefix[i] = currentSum;
        }
    }

    // O(1) Instant Query
    query(left: number, right: number): number {
        // If left is 0, we don't chop anything off
        if (left === 0) return this.prefix[right];
        
        // Chop off the prefix right before the 'left' boundary
        return this.prefix[right] - this.prefix[left - 1];
    }
}

(Note: Many implementations create the Prefix array with a size of N + 1, initializing index 0 as 0. This elegantly avoids the if (left === 0) bounds-checking logic).

Subarray Sum Equals K

The absolute most famous Prefix Sum interview question is “Subarray Sum Equals K”: “Given an unsorted array of positive and negative numbers, find the total number of continuous subarrays whose sum equals K.”

Because there are negative numbers, the Sliding Window technique fails entirely (moving the Right pointer might shrink the sum if it hits a negative number, breaking the monotonic rule).

We must use a Prefix Sum + Hash Map.

function subarraySum(nums: number[], k: number): number {
    let count = 0;
    let currentSum = 0;
    // Map stores: { prefix_sum : frequency_of_that_sum }
    const prefixMap = new Map<number, number>();
    
    // Base case: A sum of 0 has occurred 1 time (an empty subarray)
    prefixMap.set(0, 1);

    for (let num of nums) {
        currentSum += num;

        // If currentSum - K exists in our map, it means there is a prefix 
        // we can chop off to leave exactly K remaining!
        if (prefixMap.has(currentSum - k)) {
            count += prefixMap.get(currentSum - k)!;
        }

        // Add the current prefix sum to the map
        prefixMap.set(currentSum, (prefixMap.get(currentSum) || 0) + 1);
    }

    return count;
}

Interview Questions

Q: You are given an array of 1s and 0s. How can you use a Prefix Sum to find the longest contiguous subarray that contains an equal number of 1s and 0s?
A: This is a classic trick. First, you replace all the 0s in the array with -1.
Now, if a subarray has an equal number of 1s and -1s, its total mathematical sum will be exactly 0.
As you iterate through the array, you maintain a running Prefix Sum. You store the [Prefix Sum : Index] in a Hash Map. If you ever encounter a running sum that already exists in the Hash Map, it mathematically means all the numbers between that previous index and your current index sum perfectly to 0. You calculate the length (currentIndex - previousIndex) and keep track of the maximum length.