Prefix Sum

At a glance

The instinct

A prefix sum array turns a range question into a difference of two points. Define P[0] = 0 and P[i+1] = P[i] + a[i]. Then the sum of a[l..r] is P[r+1] - P[l], answered in O(1) after O(n) preprocessing.

The bigger interview idea is the prefix + hash map combo: "a subarray ending here has sum k" is the same as "some earlier prefix equals current - k". So while scanning, you ask a map how many earlier prefixes had that value. This works with negative numbers, which is exactly where sliding window breaks down.

Recognise it

Not this pattern if...

• All numbers are non-negative and you want the shortest/longest window meeting a threshold: a Sliding Window uses O(1) space.
• You want the maximum subarray sum with no target: Kadane's Running Best is simpler.
• The array changes between queries (point updates + range queries): use a Fenwick tree or segment tree.

Memory hack

Say it out loud in the interview:

1. "Range sum = current prefix minus an earlier prefix."
2. "So I need an earlier prefix equal to current - target (or with the same remainder)."
3. "Seed the map with prefix 0, query first, then record the current prefix."

How it works

For counting subarrays with sum k, scan once with a running sum. At each index, the number of subarrays ending here with sum k equals how many times sum - k appeared among earlier prefixes.

Trace for Subarray Sum Equals K on [1, 2, 3], k = 3:

The two subarrays are [1, 2] and [3]. Notice that [1, 2] was found only because the map was seeded with {0: 1}.

Remainder trick: if P[j] % k == P[i] % k, then (P[j] - P[i]) is divisible by k. Subarray Sums Divisible by K counts equal remainders; Continuous Subarray Sum stores the first index of each remainder and checks the length is at least 2.

Balance trick: Contiguous Array replaces 0 with -1, then looks for the longest gap between two equal prefix values.

Java template

import java.util.HashMap;
import java.util.Map;

class PrefixSumToolkit {
    // 1) Static range queries: build once, query in O(1).
    static long[] buildPrefix(int[] a) {
        long[] p = new long[a.length + 1];               // p[0] = 0 sentinel
        for (int i = 0; i < a.length; i++) p[i + 1] = p[i] + a[i];
        return p;
    }

    static long rangeSum(long[] p, int l, int r) {       // inclusive l..r
        return p[r + 1] - p[l];
    }

    // 2) Count subarrays whose key matches (sum == k here).
    static int countSubarrays(int[] a, int k) {
        Map<Long, Integer> seen = new HashMap<>();
        seen.put(0L, 1);                                 // empty prefix
        long sum = 0;
        int count = 0;
        for (int x : a) {
            sum += x;                                    // problem-specific transform of x
            count += seen.getOrDefault(sum - k, 0);      // query first
            seen.merge(sum, 1, Integer::sum);            // then record
        }
        return count;
    }

    // 3) Longest subarray with a property: store FIRST index of each key.
    static int longestBalanced(int[] bits) {
        Map<Integer, Integer> firstAt = new HashMap<>();
        firstAt.put(0, -1);                              // prefix before index 0
        int bal = 0, best = 0;
        for (int i = 0; i < bits.length; i++) {
            bal += bits[i] == 1 ? 1 : -1;                // or ((sum % k) + k) % k for remainders
            Integer j = firstAt.putIfAbsent(bal, i);
            if (j != null) best = Math.max(best, i - j);
        }
        return best;
    }
}

Complexity

Variations

• Immutable range queries: Range Sum Query - Immutable; the 2D version uses inclusion-exclusion on a matrix.
• Count by target difference: Subarray Sum Equals K.
• Count by equal remainder: Subarray Sums Divisible by K.
• Existence by remainder with a length constraint: Continuous Subarray Sum (first index per remainder).
• Longest by balance: Contiguous Array (0 becomes -1).
• Prefix XOR / prefix parity: same idea with XOR, or with bitmasks of odd/even counts.
• Difference array: apply many range increments with two point updates, then prefix-sum once.

Common mistakes

• Forgetting the seed ({0: 1} for counting, {0: -1} for longest length), which misses subarrays that start at index 0.
• Recording the current prefix before querying, which can match an empty subarray (wrong when k = 0).
• Overwriting the first index of a key when you want the longest subarray; use putIfAbsent.
• Integer overflow in long arrays of large values; accumulate in long.
• Off-by-one between P[r+1] - P[l] and P[r] - P[l-1]; pick one convention and stick to it.

All practice problems

5 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.