Prefix Sum & Difference Array: Interview Problems Explained

Prefix sums are probably the best return on investment among DSA patterns. The idea takes five minutes to learn, it turns O(n²) brute force into O(n) for a whole class of questions, and it sits underneath harder topics like Fenwick trees, 2D DP and sliding window on negative numbers. Its inverse, the difference array, handles range updates the same way.

Where candidates slip isn't the idea. It's the details: the off-by-one between P[r] and P[r+1], whether to put the current prefix in the map before or after the lookup, the negative modulo in Java, and recognising "subarray sum equals K" when it's dressed up as something else. This guide goes through those details problem by problem.

Prefix Sum Basics: Range Sum Queries in O(1)

Define P with one extra slot: P[0] = 0 and P[i+1] = P[i] + nums[i]. Then P[i] is the sum of the first i elements, and the sum of the inclusive range [l, r] is:

sum(l, r) = P[r + 1] − P[l]

Example with nums = [3, -1, 4, 1, 5]:

Sum of [1, 3] = P[4] − P[1] = 7 − 3 = 4, which is −1 + 4 + 1. The leading zero means a range starting at index 0 needs no special case: sum(0, r) = P[r+1] − P[0].

Range Sum Query: Immutable (LeetCode 303)

class NumArray:
    def __init__(self, nums):
        self.P = [0] * (len(nums) + 1)
        for i, x in enumerate(nums):
            self.P[i + 1] = self.P[i] + x

    def sumRange(self, left, right):
        return self.P[right + 1] - self.P[left]

class NumArray {
    private final long[] P;

    public NumArray(int[] nums) {
        P = new long[nums.length + 1];
        for (int i = 0; i < nums.length; i++) P[i + 1] = P[i] + nums[i];
    }

    public int sumRange(int left, int right) {
        return (int) (P[right + 1] - P[left]);
    }
}

Build is O(n), each query O(1), space O(n). The Java version uses long for P because prefix sums grow much faster than individual elements: 10⁵ elements of size 10⁵ already reach 10¹⁰, past int range. Individual range answers may fit in int even when intermediate prefixes don't.

Find Pivot Index (724) is the same idea from both sides: index i is a pivot when P[i] == total − P[i+1]. You don't even need the array; a running left sum and the total are enough.

Prefix Sum + Hash Map: Subarray Sum Equals K

This is the most important application, and it's the one that shows up in interviews constantly. The key rearrangement:

sum(i, j) = K  ⟺  P[j+1] − P[i] = K  ⟺  P[i] = P[j+1] − K

So as you sweep j from left to right, the number of subarrays ending at j with sum K equals the number of earlier prefixes with value current − K. Keep those counts in a hash map.

Subarray Sum Equals K (LeetCode 560)

def subarraySum(nums, k):
    seen = {0: 1}          # empty prefix: lets subarrays start at index 0
    prefix = count = 0
    for x in nums:
        prefix += x
        count += seen.get(prefix - k, 0)       # look up FIRST
        seen[prefix] = seen.get(prefix, 0) + 1  # then record
    return count

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> seen = new HashMap<>();
    seen.put(0, 1);
    int prefix = 0, count = 0;
    for (int x : nums) {
        prefix += x;
        count += seen.getOrDefault(prefix - k, 0);
        seen.merge(prefix, 1, Integer::sum);
    }
    return count;
}

Dry run with nums = [1, 2, 3, -2, 2], k = 3:

Four subarrays. The negative number didn't cause any trouble, which is exactly why this approach beats a sliding window here: the window needs monotonic sums, the hash map doesn't care.

Why lookup before insert? If you insert the current prefix first and k = 0, the current prefix matches itself and you'd count an empty subarray at every index. Lookup-then-insert guarantees that the matched prefix belongs to a strictly earlier index, so the subarray is non-empty.

Count vs. longest: what the map stores

Same skeleton, different payload:

Contiguous Array (LeetCode 525)

Longest subarray with equal 0s and 1s. Map 0 → −1 and 1 → +1; now "equal counts" means "sum is 0", and the longest zero-sum subarray is between the first and latest occurrence of the same prefix.

public int findMaxLength(int[] nums) {
    Map<Integer, Integer> first = new HashMap<>();
    first.put(0, -1);
    int sum = 0, best = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i] == 1 ? 1 : -1;
        Integer j = first.get(sum);
        if (j != null) best = Math.max(best, i - j);
        else first.put(sum, i);
    }
    return best;
}

def findMaxLength(nums):
    first = {0: -1}
    s = best = 0
    for i, x in enumerate(nums):
        s += 1 if x == 1 else -1
        if s in first:
            best = max(best, i - first[s])
        else:
            first[s] = i
    return best

The "replace 0 with −1" move is worth remembering as a general trick: any "equal number of A and B" condition becomes "sum equals zero".

Subarray Sums Divisible by K (LeetCode 974)

A subarray's sum is divisible by K when the two prefixes bounding it have the same remainder mod K. So bucket prefixes by remainder; each bucket with c entries contributes c·(c−1)/2 pairs, or, equivalently, add the current bucket count at each step.

def subarraysDivByK(nums, k):
    count = [0] * k
    count[0] = 1
    prefix = res = 0
    for x in nums:
        prefix = (prefix + x) % k       # Python: always in [0, k)
        res += count[prefix]
        count[prefix] += 1
    return res

public int subarraysDivByK(int[] nums, int k) {
    int[] count = new int[k];
    count[0] = 1;
    int prefix = 0, res = 0;
    for (int x : nums) {
        prefix = ((prefix + x) % k + k) % k;   // normalise negative remainders
        res += count[prefix];
        count[prefix]++;
    }
    return res;
}

Continuous Subarray Sum (523) is the "exists, length at least 2" version: store the first index for each remainder and check i − first[r] ≥ 2.

Beyond Sums: Prefix XOR, Prefix Products and Weighted Sampling

Prefix sums work for any operation that has an inverse. Subtraction undoes addition; XOR undoes itself. That's the whole requirement.

Prefix XOR: XOR Queries of a Subarray (LeetCode 1310)

def xorQueries(arr, queries):
    px = [0] * (len(arr) + 1)
    for i, x in enumerate(arr):
        px[i + 1] = px[i] ^ x
    return [px[r + 1] ^ px[l] for l, r in queries]

Combine prefix XOR with a hash map and you get "count subarrays with XOR equal to K" in O(n), which is the same as 560 with ^ in place of + and −. It's a common question in Indian product company OAs.

Prefix and suffix products: Product of Array Except Self (238)

Multiplication has an inverse (division) only when nothing is zero, and the problem bans division anyway. The workaround is to keep a prefix product from the left and a suffix product from the right, and multiply them. The O(1)-extra-space version and its edge cases are in the Product of Array Except Self walkthrough.

Prefix sums + binary search: Random Pick with Weight (528)

Weights [1, 3, 2] become prefix sums [1, 4, 6]. Pick a uniform random integer in [1, 6] and binary search for the first prefix ≥ it: values 1 → index 0, 2–4 → index 1, 5–6 → index 2. Each index is picked in proportion to its weight.

import bisect
import random

class Solution:
    def __init__(self, w):
        self.prefix = []
        total = 0
        for x in w:
            total += x
            self.prefix.append(total)
        self.total = total

    def pickIndex(self):
        target = random.randint(1, self.total)        # inclusive
        return bisect.bisect_left(self.prefix, target)

Prefix sums of positive numbers are strictly increasing, which is what makes the binary search valid. The same observation gives an O(n log n) solution to Minimum Size Subarray Sum.

2D Prefix Sums: Submatrix Sums in O(1)

Let P[i][j] be the sum of the rectangle from (0, 0) to (i−1, j−1), again with a padding row and column of zeros. Building it uses inclusion-exclusion: take the cell, add the rectangle above and the rectangle to the left, and subtract their overlap, which was counted twice.

Worked example with

M = 1 2 3        P = 0  0  0  0
    4 5 6            0  1  3  6
    7 8 9            0  5 12 21
                     0 12 27 45

The sum of the 2×2 block from (1, 1) to (2, 2) is 5 + 6 + 8 + 9 = 28, and the formula gives P[3][3] − P[1][3] − P[3][1] + P[1][1] = 45 − 6 − 12 + 1 = 28.

Range Sum Query 2D: Immutable (LeetCode 304)

class NumMatrix {
    private final int[][] P;

    public NumMatrix(int[][] m) {
        int R = m.length, C = m[0].length;
        P = new int[R + 1][C + 1];
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                P[i + 1][j + 1] = m[i][j] + P[i][j + 1] + P[i + 1][j] - P[i][j];
    }

    public int sumRegion(int r1, int c1, int r2, int c2) {
        return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1];
    }
}

class NumMatrix:
    def __init__(self, m):
        R, C = len(m), len(m[0])
        self.P = [[0] * (C + 1) for _ in range(R + 1)]
        for i in range(R):
            for j in range(C):
                self.P[i + 1][j + 1] = (m[i][j] + self.P[i][j + 1]
                                        + self.P[i + 1][j] - self.P[i][j])

    def sumRegion(self, r1, c1, r2, c2):
        P = self.P
        return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]

Matrix Block Sum (1314) is this with clamped boundaries: for each cell, query the rectangle (i−k, j−k) to (i+k, j+k) after clamping to the grid. Maximal Square problems can also use it to check "is this k×k block all ones" in O(1), though DP is the usual answer.

Number of Submatrices That Sum to Target (LeetCode 1074)

This hard problem combines everything. Fix a top row and a bottom row; collapse the rows between them into a 1D array of column sums; then count subarrays of that array summing to target with the 560 technique. That's O(R²·C) instead of O(R²·C²).

def numSubmatrixSumTarget(matrix, target):
    R, C = len(matrix), len(matrix[0])
    total = 0
    for top in range(R):
        col = [0] * C
        for bottom in range(top, R):
            for c in range(C):
                col[c] += matrix[bottom][c]     # column sums for rows top..bottom
            seen = {0: 1}
            prefix = 0
            for v in col:                       # 1D subarray sum equals target
                prefix += v
                total += seen.get(prefix - target, 0)
                seen[prefix] = seen.get(prefix, 0) + 1
    return total

If R is much larger than C, iterate over pairs of columns instead, so the squared term is the smaller dimension. Saying that out loud is a nice signal. "Fix two boundaries and reduce to 1D" also solves maximum sum rectangle (Kadane in place of the hash map) and is a pattern worth knowing for matrix and grid problems.

Difference Arrays: O(1) Range Updates

A difference array is the inverse of a prefix sum. Define D[0] = A[0] and D[i] = A[i] − A[i−1]. Taking the prefix sum of D gives back A. The useful property: adding v to every element of A in [l, r] changes only two entries of D.

D[l] += v    D[r + 1] −= v

The +v at l raises everything from l onward once you take prefix sums; the −v at r+1 cancels it after r. With q updates on an array of n, you pay O(q + n) total instead of O(q·n).

Corporate Flight Bookings (LeetCode 1109)

Each booking [first, last, seats] adds seats to flights first..last (1-indexed). Return the total per flight.

def corpFlightBookings(bookings, n):
    diff = [0] * (n + 1)              # extra slot absorbs r + 1 = n
    for first, last, seats in bookings:
        diff[first - 1] += seats
        diff[last] -= seats           # (last - 1) + 1
    res, running = [], 0
    for i in range(n):
        running += diff[i]
        res.append(running)
    return res

public int[] corpFlightBookings(int[][] bookings, int n) {
    int[] diff = new int[n + 1];
    for (int[] b : bookings) {
        diff[b[0] - 1] += b[2];
        diff[b[1]] -= b[2];
    }
    int[] res = new int[n];
    int running = 0;
    for (int i = 0; i < n; i++) {
        running += diff[i];
        res[i] = running;
    }
    return res;
}

Dry run: bookings [[1,2,10], [2,3,20], [2,5,25]], n = 5. The diff array becomes [10, 45, −10, −20, 0, −25]. Running sums: 10, 55, 45, 25, 25. That's the expected output.

Car Pooling (LeetCode 1094)

Trips [passengers, from, to]; passengers leave at to, so they occupy [from, to − 1]. Add with a difference array over locations and check that the running load never exceeds capacity.

def carPooling(trips, capacity):
    diff = [0] * 1001                 # locations are 0..1000
    for p, start, end in trips:
        diff[start] += p
        diff[end] -= p                # drop-off frees the seat at 'end'
    load = 0
    for change in diff:
        load += change
        if load > capacity:
            return False
    return True

This is the same "sweep line" idea used for meeting rooms: +1 at a start, −1 at an end, and the running sum is the number of overlapping intervals. When coordinates are huge (10⁹), you can't allocate the array, so you sort the events instead, or keep a TreeMap of coordinate → delta. The interval problems guide covers that version.

2D difference arrays

To add v to every cell in the rectangle (r1, c1)–(r2, c2), mark four corners and then take a 2D prefix sum at the end:

D[r1][c1]         += v
D[r1][c2 + 1]     -= v
D[r2 + 1][c1]     -= v
D[r2 + 1][c2 + 1] += v

That's LeetCode 2536 (Increment Submatrices by One) and the core of "stamp" or "paint the grid" problems in contests. Allocate D with one extra row and column so the r2+1 and c2+1 writes stay in bounds.

Static vs. Dynamic: When to Upgrade to a Fenwick or Segment Tree

Prefix sums and difference arrays assume a clean split between "all updates" and "all queries". When those interleave, the costs flip.

Note that a Fenwick tree is literally "a prefix sum that tolerates updates", and a Fenwick tree over a difference array gives range update + point query. Both are built step by step in segment tree and Fenwick tree explained. Mentioning this table when an interviewer adds "now the array changes" is one of the easiest ways to stand out.

Prefix Sum Interview Playbook

Recognition signals

• "Sum / count / XOR of a subarray" with negatives allowed → prefix + hash map.
• Many range-sum queries on a fixed array → prefix array.
• "Equal number of X and Y" → map to ±1, find zero-sum subarray.
• "Divisible by K" or "modulo K" over subarrays → bucket prefixes by remainder.
• Many "add v to range [l, r]" operations → difference array.
• 2D grid + rectangle sums → 2D prefix; "count submatrices" → fix two rows, reduce to 1D.

The checklist I run before saying "done"

1. Sizing. Prefix and difference arrays have n + 1 slots. Am I reading P[r + 1] and writing D[r + 1]?
2. Seed. Is the map seeded with the empty prefix (count 1 or index −1)?
3. Order. Lookup before insert, so subarrays are non-empty.
4. Overflow. In Java/C++, do prefixes need long?
5. Modulo. Are remainders normalised to [0, k)?
6. Edge cases. Empty array, single element, k = 0, all negatives, target equal to the total.

Follow-ups to expect

• "What if the array is updated?" Fenwick tree, as above.
• "Return the subarray, not the count." Store indices instead of counts; the subarray is (map[prefix − k] + 1, j).
• "Can you avoid the hash map?" Only when values are non-negative (then a sliding window works) or the prefix range is small (then an array indexed by prefix value works).
• "What's the space?" O(n) for the map in the worst case, when all prefixes are distinct.

Prefix sums also lean heavily on hashing; if the map-based variants feel shaky, the hashing and hash map problems guide is the natural companion.

Prefix Sum and Difference Array Problem List

Work through them in that order. By the time you reach 862, you'll recognise it as "prefix sums, but the hash map can't answer 'at least K', so keep candidate prefixes in a monotonic deque instead". That kind of reasoning from known pieces, rather than recalling a memorised solution, is what interviewers are actually scoring.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.