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.
| Problems | 10, easy to hard |
|---|---|
| Languages | Python and Java |
| Core idea | Range 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.
- Count of subarrays: map from prefix value to count.
- Longest subarray: map from prefix value to first index.
- Divisibility by k: store remainders instead of sums.
- Range updates: difference array, then one prefix pass.
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 Range sum query (immutable): answer many sum(l, r) queries on a fixed array.
easyBuild 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.
pythonclass 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]javaclass 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 Find the pivot index: the index where the sum on its left equals the sum on its right.
easyCompute 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.
pythondef pivot_index(a): total, left = sum(a), 0 for i, x in enumerate(a): if left == total - left - x: return i left += x return -1javaimport 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 Subarray sum equals K: count subarrays with sum exactly k (negatives allowed).
mediumMaintain 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.
pythondef 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 resjavaimport 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 Contiguous array: longest subarray with equal numbers of 0s and 1s.
mediumTreat 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.
pythondef 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 bestjavaimport 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 Maximum size subarray sum equals k, with negative numbers allowed.
mediumMap 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.
pythondef 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 bestjavaimport 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 Subarray sums divisible by K: count subarrays whose sum is a multiple of k.
mediumTwo 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.
pythondef 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 resjavaimport 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 Continuous subarray sum: is there a subarray of length at least 2 whose sum is a multiple of k?
mediumSame 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].
pythondef 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 Falsejavaimport 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 2D range sum query: sum of any rectangle in a matrix, many queries.
mediumBuild 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.
pythonclass 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]javaclass 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 Range addition: apply many "add v to every element in [l, r]" updates to a zero array.
hardA 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.
pythondef 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 outjavaimport 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 Shortest subarray with sum at least K when numbers can be negative.
hardA 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).
pythonfrom 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 -1javaimport 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
- Array interview questions with worked solutions
- Hashing interview questions with worked solutions
- Sliding window interview questions with worked solutions
- Kadane algorithm interview questions with worked solutions
- Matrix interview questions with worked solutions
- Interval interview questions with worked solutions
More in DSA Interview Questions
- Queue and deque interview questions with worked solutions
- Recursion interview questions with worked solutions
- Segment Tree Interview Questions
- Sliding window interview questions with worked solutions
- Sorting algorithm interview questions with worked solutions
- Stack interview questions with worked solutions
- String interview questions with worked solutions
- Top K elements interview questions with worked solutions
- Topological Sort Interview Questions
- Tree DP Interview Questions
- Tree Traversal Interview Questions
- Trie (Prefix Tree) Interview Questions