Prefix Sum

Prefix sum is the pattern that picks up where sliding window stops. The moment an array can contain negative numbers, the window's shrink rule becomes unsound — and prefix sums plus a hash map is the replacement. It is also the answer to every "many range queries on a fixed array" question.

The idea

Build an array where prefix[i] is the sum of everything before index i:

Then the sum of any range [i, j] is one subtraction:

sum(i..j) = prefix[j + 1] - prefix[i]
sum(1..3) = prefix[4] - prefix[1] = 9 - 3 = 6   →  1 + 4 + 1 ✓

O(n) to build, O(1) per query, forever. The leading zero is not decoration — it is what makes ranges starting at index 0 work without a special case, and leaving it out is the most common bug in this pattern.

class NumArray:
    def __init__(self, nums):
        self.prefix = [0]
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)

    def sum_range(self, i, j):
        return self.prefix[j + 1] - self.prefix[i]

class NumArray {
    private final int[] prefix;

    NumArray(int[] nums) {
        prefix = new int[nums.length + 1];     // the leading zero
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }

    int sumRange(int i, int j) {
        return prefix[j + 1] - prefix[i];
    }
}

class NumArray {
    vector<int> prefix;
public:
    NumArray(const vector<int>& nums) : prefix(nums.size() + 1, 0) {
        for (size_t i = 0; i < nums.size(); i++) {
            prefix[i + 1] = prefix[i] + nums[i];   // the leading zero
        }
    }

    int sumRange(int i, int j) {
        return prefix[j + 1] - prefix[i];
    }
};

typedef struct { int* prefix; } NumArray;

NumArray* numArrayCreate(int* nums, int n) {
    NumArray* a = malloc(sizeof(NumArray));
    a->prefix = calloc(n + 1, sizeof(int));   /* index 0 stays the leading zero */
    for (int i = 0; i < n; i++) {
        a->prefix[i + 1] = a->prefix[i] + nums[i];
    }
    return a;
}

int numArraySumRange(NumArray* a, int i, int j) {
    return a->prefix[j + 1] - a->prefix[i];
}

class NumArray {
  constructor(nums) {
    this.prefix = [0];
    for (const x of nums) {
      this.prefix.push(this.prefix[this.prefix.length - 1] + x);
    }
  }

  sumRange(i, j) {
    return this.prefix[j + 1] - this.prefix[i];
  }
}

The counting trick

The version that actually gets asked: count the subarrays summing to k.

Rearrange the identity. A subarray ending at j sums to k exactly when prefix[j] - prefix[i] = k, i.e. when prefix[i] = prefix[j] - k. So while scanning, keep a count of every prefix seen so far and look up how many equal current - k:

def subarray_sum(nums, k):
    seen = {0: 1}          # the empty prefix — needed for subarrays starting at 0
    running = count = 0
    for x in nums:
        running += x
        count += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return count

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> seen = new HashMap<>();
    seen.put(0, 1);          // the empty prefix
    int running = 0, count = 0;

    for (int x : nums) {
        running += x;
        count += seen.getOrDefault(running - k, 0);
        seen.merge(running, 1, Integer::sum);
    }
    return count;
}

int subarraySum(const vector<int>& nums, int k) {
    unordered_map<int, int> seen{{0, 1}};   // the empty prefix
    int running = 0, count = 0;

    for (int x : nums) {
        running += x;
        auto it = seen.find(running - k);
        if (it != seen.end()) count += it->second;
        seen[running]++;
    }
    return count;
}

function subarraySum(nums, k) {
  const seen = new Map([[0, 1]]);   // the empty prefix
  let running = 0, count = 0;

  for (const x of nums) {
    running += x;
    count += seen.get(running - k) ?? 0;
    seen.set(running, (seen.get(running) ?? 0) + 1);
  }
  return count;
}

One pass, O(n) time and space, and it is correct with negative numbers — which is the whole reason to reach for it over a window.

The {0: 1} seed is the same leading zero as before, wearing a different hat. Without it a subarray that starts at index 0 and sums to k is never counted.

The variants worth knowing

The same skeleton solves problems that look unrelated, by changing what you accumulate:

Note the second row: when the question asks for the longest such subarray rather than the count, store the earliest index each key was seen at and never overwrite it.

Product of Array Except Self is the same idea with multiplication: a prefix pass and a

suffix pass, multiplied, giving every element the product of everything but itself without division and in O(1) extra space.

Complexity

O(n) to build, O(1) per range query, O(n) space. The hash-map variants are one O(n) pass with O(n) space. Two-dimensional prefix sums generalise this to O(1) rectangle queries on a matrix with inclusion–exclusion, which is worth a look once the 1-D version is solid.

Mistakes that cost the round

• Dropping the leading zero — or the {0: 1} seed. Both are the same off-by-one and

both produce answers that are correct except when the subarray starts at index 0.

• Overwriting the first index when the question wants the longest subarray. For

counting you increment; for longest you keep the earliest.

• Reaching for sliding window on an array with negatives. It looks like a window

problem and quietly returns wrong answers on inputs the samples do not cover.

• Building the prefix array when you only need the running value. The counting variant

needs one integer, not an array.

What to drill

1. Range Sum Query — Immutable — the bare prefix array.
2. Subarray Sum Equals K — the hash-map trick.
3. Product of Array Except Self — prefix and suffix, no division.
4. Contiguous Array — the +1/−1 reframe.
5. Subarray Sums Divisible by K — the same map keyed on a remainder.
6. Number of Ways to Split Array — prefix against total.

All on the 22 DSA Patterns sheet.