Autocoder

Prefix sum interview questions with worked solutions

Last updated 2026-11-19

A prefix sum array stores the running total up to each index, so the sum of any range is one subtraction: sum(l..r) = P[r+1] - P[l]. You pay O(n) once to build it and then answer each range query in O(1). The idea extends to hash maps of prefix values, which count subarrays with a target sum even when the numbers are negative.

The ten problems below move from a plain range-sum class to the remainder tricks used for divisibility questions, a 2D version, and a difference array that applies range updates in O(1) each. If a problem has only positive numbers and asks for a window, sliding window is also an option; with negatives, prefix sums are the safer choice. For test strategy, see the DSA coding round guide.

Problems10, easy to hard
LanguagesPython and Java
Core ideaRange sum = prefix[r+1] - prefix[l]

The two core tricks

First, a prefix array turns a range sum into a subtraction. Second, "a subarray from i+1 to j has sum k" is the same as "P[j] - P[i] = k", so while scanning you look up how many earlier prefix values equal P[j] - k in a hash map.

Always seed the map with prefix 0 occurring once (index -1 for position problems), otherwise subarrays that start at index 0 are missed.

Pitfalls

Negative remainders differ by language: in Python -3 % 5 is 2, in Java it is -3. Normalise with ((x % k) + k) % k in Java. Large sums need long. Off-by-one errors in the prefix array (length n + 1) cause most wrong answers.

Prefix sum interview questions with worked solutions: questions with worked answers

  1. 1

    Range sum query (immutable): answer many sum(l, r) queries on a fixed array.

    easy

    Build prefix sums with an extra leading zero so that P[i] is the sum of the first i elements. Then sum(l, r) = P[r + 1] - P[l]. Construction is linear and every query is constant time, versus O(n) per query when summing directly. Time O(n) build, O(1) per query; space O(n).. Edge cases: query over the whole array, l equal to r, an empty-array build.

    python
    class NumArray:
        def __init__(self, a):
            self.p = [0]
            for x in a:
                self.p.append(self.p[-1] + x)
    
        def sum_range(self, l, r):
            return self.p[r + 1] - self.p[l]
    java
    class NumArray {
        private final long[] p;
    
        NumArray(int[] a) {
            p = new long[a.length + 1];
            for (int i = 0; i < a.length; i++) p[i + 1] = p[i] + a[i];
        }
        long sumRange(int l, int r) { return p[r + 1] - p[l]; }
    }
  2. 2

    Find the pivot index: the index where the sum on its left equals the sum on its right.

    easy

    Compute the total once. Walk the array keeping the sum to the left of the current index; the right sum is total - left - a[i]. Return the first index where the two match. The element itself is excluded from both sides. Time O(n), space O(1).. Edge cases: index 0 (left sum is 0), last index, no pivot (-1), negative values.

    python
    def pivot_index(a):
        total, left = sum(a), 0
        for i, x in enumerate(a):
            if left == total - left - x:
                return i
            left += x
        return -1
    java
    import java.util.*;
    
    class Solution {
        static int pivotIndex(int[] a) {
            int total = 0, left = 0;
            for (int x : a) total += x;
            for (int i = 0; i < a.length; i++) {
                if (left == total - left - a[i]) return i;
                left += a[i];
            }
            return -1;
        }
    }
  3. 3

    Subarray sum equals K: count subarrays with sum exactly k (negatives allowed).

    medium

    Maintain the running sum and a map from prefix sum to how many times it occurred. At each element, add map[sum - k] to the answer, then record the current sum. Seed the map with {0: 1}. Windows fail here because negatives break monotonicity, but this method does not care. Time O(n), space O(n).. Edge cases: k = 0 with zero runs, negative numbers, all elements equal to k.

    python
    def subarray_sum(a, k):
        cnt = {0: 1}
        s = res = 0
        for x in a:
            s += x
            res += cnt.get(s - k, 0)
            cnt[s] = cnt.get(s, 0) + 1
        return res
    java
    import java.util.*;
    
    class Solution {
        static int subarraySum(int[] a, int k) {
            Map<Integer, Integer> cnt = new HashMap<>();
            cnt.put(0, 1);
            int s = 0, res = 0;
            for (int x : a) {
                s += x;
                res += cnt.getOrDefault(s - k, 0);
                cnt.merge(s, 1, Integer::sum);
            }
            return res;
        }
    }
  4. 4

    Contiguous array: longest subarray with equal numbers of 0s and 1s.

    medium

    Treat each 0 as -1. Then a balanced subarray has sum zero. Store the first index at which each running sum appears; when a sum repeats, the subarray between the two indices has sum zero, so its length is the difference. Seed with sum 0 at index -1. Time O(n), space O(n).. Edge cases: no balanced pair (0), all the same bit, the whole array balanced.

    python
    def find_max_length(a):
        first = {0: -1}
        s = best = 0
        for i, x in enumerate(a):
            s += 1 if x == 1 else -1
            if s in first:
                best = max(best, i - first[s])
            else:
                first[s] = i
        return best
    java
    import java.util.*;
    
    class Solution {
        static int findMaxLength(int[] a) {
            Map<Integer, Integer> first = new HashMap<>();
            first.put(0, -1);
            int s = 0, best = 0;
            for (int i = 0; i < a.length; i++) {
                s += a[i] == 1 ? 1 : -1;
                if (first.containsKey(s)) best = Math.max(best, i - first.get(s));
                else first.put(s, i);
            }
            return best;
        }
    }
  5. 5

    Maximum size subarray sum equals k, with negative numbers allowed.

    medium

    Map each prefix sum to its earliest index. At index i with running sum s, if s - k was seen at index j, the subarray (j, i] has sum k and length i - j. Only insert a sum the first time, so each match is as long as possible. Time O(n), space O(n).. Edge cases: no such subarray (0), k = 0, the subarray starting at index 0.

    python
    def max_subarray_len(a, k):
        first = {0: -1}
        s = best = 0
        for i, x in enumerate(a):
            s += x
            if s - k in first:
                best = max(best, i - first[s - k])
            if s not in first:
                first[s] = i
        return best
    java
    import java.util.*;
    
    class Solution {
        static int maxSubArrayLen(int[] a, int k) {
            Map<Long, Integer> first = new HashMap<>();
            first.put(0L, -1);
            long s = 0;
            int best = 0;
            for (int i = 0; i < a.length; i++) {
                s += a[i];
                if (first.containsKey(s - k)) best = Math.max(best, i - first.get(s - k));
                first.putIfAbsent(s, i);
            }
            return best;
        }
    }
  6. 6

    Subarray sums divisible by K: count subarrays whose sum is a multiple of k.

    medium

    Two prefixes with the same remainder modulo k give a subarray whose sum is divisible by k. Count remainders: each new prefix adds count[remainder] to the answer. Normalise negative remainders into 0..k-1, and seed count[0] = 1. Time O(n), space O(k).. Edge cases: negative numbers (normalise the remainder), k = 1 (all subarrays), zero values.

    python
    def subarrays_div_by_k(a, k):
        cnt = [0] * k
        cnt[0] = 1
        s = res = 0
        for x in a:
            s = (s + x) % k
            res += cnt[s]
            cnt[s] += 1
        return res
    java
    import java.util.*;
    
    class Solution {
        static int subarraysDivByK(int[] a, int k) {
            int[] cnt = new int[k];
            cnt[0] = 1;
            int s = 0, res = 0;
            for (int x : a) {
                s = ((s + x) % k + k) % k;
                res += cnt[s];
                cnt[s]++;
            }
            return res;
        }
    }
  7. 7

    Continuous subarray sum: is there a subarray of length at least 2 whose sum is a multiple of k?

    medium

    Same remainder idea, but store the first index at which each remainder appeared and require the gap to be at least 2. Seed remainder 0 at index -1. Do not overwrite an earlier index, since the earliest gives the longest gap. Time O(n), space O(k).. Edge cases: length-1 subarrays must not count, k = 1 with two elements, zeroes such as [0, 0].

    python
    def check_subarray_sum(a, k):
        first = {0: -1}
        s = 0
        for i, x in enumerate(a):
            s = (s + x) % k
            if s in first:
                if i - first[s] >= 2:
                    return True
            else:
                first[s] = i
        return False
    java
    import java.util.*;
    
    class Solution {
        static boolean checkSubarraySum(int[] a, int k) {
            Map<Integer, Integer> first = new HashMap<>();
            first.put(0, -1);
            int s = 0;
            for (int i = 0; i < a.length; i++) {
                s = (s + a[i]) % k;
                if (first.containsKey(s)) {
                    if (i - first.get(s) >= 2) return true;
                } else first.put(s, i);
            }
            return false;
        }
    }
  8. 8

    2D range sum query: sum of any rectangle in a matrix, many queries.

    medium

    Build P[i][j] as the sum of the rectangle from (0,0) to (i-1,j-1). A rectangle sum is P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1], which is inclusion-exclusion: add the corner back because it was subtracted twice. Time O(m*n) build, O(1) per query; space O(m*n).. Edge cases: one cell, whole matrix, a rectangle touching the top or left edge.

    python
    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 sum_region(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]
    java
    class NumMatrix {
        private final int[][] p;
    
        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];
        }
        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];
        }
    }
  9. 9

    Range addition: apply many "add v to every element in [l, r]" updates to a zero array.

    hard

    A difference array makes each update O(1): add v at index l and subtract v at index r + 1. After all updates, one prefix-sum pass over the difference array gives the final values. Naive updating would cost O(n) each. The same idea solves car pooling and meeting-room occupancy problems. Time O(n + q) for q updates, space O(n).. Edge cases: update ending at the last index (skip the r + 1 write), overlapping updates, negative v.

    python
    def apply_updates(n, updates):
        d = [0] * (n + 1)
        for l, r, v in updates:
            d[l] += v
            d[r + 1] -= v
        out, run = [], 0
        for i in range(n):
            run += d[i]
            out.append(run)
        return out
    java
    import java.util.*;
    
    class Solution {
        static int[] applyUpdates(int n, int[][] updates) {
            int[] d = new int[n + 1];
            for (int[] u : updates) {
                d[u[0]] += u[2];
                d[u[1] + 1] -= u[2];
            }
            int[] out = new int[n];
            int run = 0;
            for (int i = 0; i < n; i++) {
                run += d[i];
                out[i] = run;
            }
            return out;
        }
    }
  10. 10

    Shortest subarray with sum at least K when numbers can be negative.

    hard

    A window fails because shrinking can increase the sum. Use prefix sums and a deque of indices with increasing prefix values. For each i, while P[i] - P[front] >= K, pop the front and record i - front. Also pop from the back while P[back] >= P[i], because a later index with a smaller prefix is always a better start. Time O(n), space O(n).. Edge cases: no valid subarray (-1), a single element already at least K, large sums (use long).

    python
    from collections import deque
    
    def shortest_subarray(a, k):
        n = len(a)
        p = [0] * (n + 1)
        for i in range(n):
            p[i + 1] = p[i] + a[i]
        dq, best = deque(), n + 1
        for i in range(n + 1):
            while dq and p[i] - p[dq[0]] >= k:
                best = min(best, i - dq.popleft())
            while dq and p[dq[-1]] >= p[i]:
                dq.pop()
            dq.append(i)
        return best if best <= n else -1
    java
    import java.util.*;
    
    class Solution {
        static int shortestSubarray(int[] a, int k) {
            int n = a.length;
            long[] p = new long[n + 1];
            for (int i = 0; i < n; i++) p[i + 1] = p[i] + a[i];
            Deque<Integer> dq = new ArrayDeque<>();
            int best = n + 1;
            for (int i = 0; i <= n; i++) {
                while (!dq.isEmpty() && p[i] - p[dq.peekFirst()] >= k) best = Math.min(best, i - dq.pollFirst());
                while (!dq.isEmpty() && p[dq.peekLast()] >= p[i]) dq.pollLast();
                dq.addLast(i);
            }
            return best <= n ? best : -1;
        }
    }

Frequently asked questions

When should I use prefix sums instead of a sliding window?

Use prefix sums when the array can hold negative numbers, or when you must answer many range queries. Use a window for positive numbers and contiguous conditions.

Why seed the hash map with prefix 0?

It represents the empty prefix, so a subarray that begins at index 0 is counted. Without it, those subarrays are silently missed.

Is a prefix sum the same as a cumulative sum?

Yes, it is the same idea under two names. Python offers itertools.accumulate and NumPy cumsum, but in interviews write the loop so the indexing is visible.

Can prefix techniques work for products or XOR?

XOR works the same way, since x ^ x = 0 undoes a prefix. Products work only without zeros, using division; see the product-except-self problem in arrays questions.

What is a difference array used for?

It is the inverse of a prefix sum, and turns many range updates into point updates. See also interval questions for sweep-line cousins.

Related guides

More in DSA Interview Questions

See all in this section