Prefix Sum
Given an array of integers arr and a target value, find a subarray that sums to the target. Return the start and end indices of the subarray.
Input: arr = [1, -20, -3, 30, 5, 4], target = 7
Output: [1, 4]
Explanation: The subarray [-20, -3, 30] from index 1 (inclusive) to 4 (exclusive) sums to 7.
Try it yourself
Solution
Understanding the problem
Consider finding a subarray that sums to 7 in [1, -20, -3, 30, 5, 4]. A direct approach checks every possible subarray. Start at index 0, check subarrays of length 1, then length 2, and so on. Then start at index 1 and repeat. For an array with n elements, this creates roughly n²/2 subarrays to examine. Computing each sum by adding its elements takes O(n) time in the worst case, resulting in O(n³) total time.
We can improve to O(n²) by reusing partial sums. When checking subarray [1, 4], we've already computed the sum [1, 3]. Just add the element at index 4 instead of recalculating from scratch. This optimization helps but still requires checking every possible subarray pair.
The prefix sum transformation
The sum of elements from index i to j equals the sum from 0 to j minus the sum from 0 to (i-1). Consider the array [1, -20, -3, 30, 5, 4]. The sum from index 1 to 3 is -20 + (-3) + 30 = 7. We can compute this as: (sum from 0 to 3) - (sum from 0 to 0) = 8 - 1 = 7. The sum from 0 to 3 includes all four elements 1 + (-20) + (-3) + 30 = 8. The sum from 0 to 0 is just 1. Subtracting removes the first element, leaving the sum of indices 1 to 3.
This observation lets us precompute cumulative sums—called prefix sums—for each position. The prefix sum at index i represents the total of all elements from index 0 through i. With these precomputed values, we can calculate any range sum in constant time by subtracting two prefix sums.
Build the prefix sum array by maintaining a running total. Start with 0 to represent the sum before any elements:
prefix_sum = [0] for num in arr: prefix_sum.append(prefix_sum[-1] + num)
For [1, -20, -3, 30, 5, 4], this produces [0, 1, -19, -22, 8, 13, 17]. The value at prefix_sum[i] represents the sum of all elements from index 0 to i-1. So prefix_sum[4] contains the sum of elements at indices 0, 1, 2, and 3, which is 1 + (-20) + (-3) + 30 = 8.
To find the sum from index 1 to 3, calculate prefix_sum[4] - prefix_sum[1] = 8 - 1 = 7. This works because prefix_sum[4] includes indices 0-3, and subtracting prefix_sum[1] removes index 0, leaving indices 1-3.
Converting to a lookup problem
We need indices i and j where prefix_sum[j] - prefix_sum[i] = target. Rearranging: prefix_sum[i] = prefix_sum[j] - target. As we compute each prefix sum at position j, check whether prefix_sum[j] - target exists in a dictionary of previously seen prefix sums. If it does, we've found our subarray.
The dictionary maps each prefix sum value to the index where it occurred. Initialize with {0: 0} to handle subarrays starting at index 0. Consider arr = [7, 3, 5] with target = 7. At index 0, the running sum is 7. We check if 7 - 7 = 0 exists in the dictionary. It does at position 0, indicating the subarray from index 0 to 0 (the element [7]) sums to the target.
Walking through the algorithm
Start with arr = [1, -20, -3, 30, 5, 4] and target = 7. Initialize the dictionary prefix_map = {0: 0} and running sum current_sum = 0.
At index 0: current_sum = 1. Check if 1 - 7 = -6 exists in prefix_map. It doesn't. Add {1: 1} to the map (mapping sum to the next index after seeing this sum).
At index 1: current_sum = 1 + (-20) = -19. Check if -19 - 7 = -26 exists. It doesn't. Add {-19: 2}.
At index 2: current_sum = -19 + (-3) = -22. Check if -22 - 7 = -29 exists. It doesn't. Add {-22: 3}.
At index 3: current_sum = -22 + 30 = 8. Check if 8 - 7 = 1 exists. Yes, at position 1. This means the subarray from index 1 (inclusive) to 4 (exclusive) sums to 7. Return [1, 4].
The dictionary lookup replaced an O(n) scan for each position with an O(1) check, reducing the time from O(n²) to O(n).
Complexity
Time Complexity: O(n) where n is the length of the array. We make a single pass through the array, and each dictionary operation takes O(1) time.
Space Complexity: O(n) for the dictionary. In the worst case, all prefix sums are unique and we store n entries.
1def subarray_sum(arr: list[int], target: int) -> list[int]:
2 # prefix_sum 0 happens when we have an empty array
3 prefix_sums = {0: 0}
4 cur_sum = 0
5 for i in range(len(arr)):
6 cur_sum += arr[i]
7 complement = cur_sum - target
8 if complement in prefix_sums:
9 return [prefix_sums[complement], i + 1]
10 prefix_sums[cur_sum] = i + 1
11 return []
12
13if __name__ == "__main__":
14 arr = [int(x) for x in input().split()]
15 target = int(input())
16 res = subarray_sum(arr, target)
17 print(" ".join(map(str, res)))
181import java.util.Arrays;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Scanner;
5import java.util.stream.Collectors;
6
7class Solution {
8 public static List<Integer> subarraySum(List<Integer> arr, int target) {
9 HashMap<Integer, Integer> prefixSums = new HashMap<>();
10 // prefix_sum 0 happens when we have an empty array
11 prefixSums.put(0, 0);
12 int curSum = 0;
13 for (int i = 0; i < arr.size(); i++) {
14 curSum += arr.get(i);
15 int complement = curSum - target;
16 if (prefixSums.containsKey(complement)) {
17 return List.of(prefixSums.get(complement), i + 1);
18 }
19 prefixSums.put(curSum, i + 1);
20 }
21 return null;
22 }
23
24 public static List<String> splitWords(String s) {
25 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
26 }
27
28 public static void main(String[] args) {
29 Scanner scanner = new Scanner(System.in);
30 List<Integer> arr = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
31 int target = Integer.parseInt(scanner.nextLine());
32 scanner.close();
33 List<Integer> res = subarraySum(arr, target);
34 System.out.println(res.stream().map(String::valueOf).collect(Collectors.joining(" ")));
35 }
36}
371"use strict";
2
3function subarraySum(arr, target) {
4 // prefix_sum 0 happens when we have an empty array
5 const prefixSums = new Map([[0, 0]]);
6 let curSum = 0;
7 for (let i = 0; i < arr.length; i++) {
8 curSum += arr[i];
9 const complement = curSum - target;
10 if (prefixSums.has(complement)) {
11 return [prefixSums.get(complement), i + 1];
12 }
13 prefixSums.set(curSum, i + 1);
14 }
15 return [];
16}
17
18function splitWords(s) {
19 return s === "" ? [] : s.split(" ");
20}
21
22function* main() {
23 const arr = splitWords(yield).map((v) => parseInt(v));
24 const target = parseInt(yield);
25 const res = subarraySum(arr, target);
26 console.log(res.join(" "));
27}
28
29class EOFError extends Error {}
30{
31 const gen = main();
32 const next = (line) => gen.next(line).done && process.exit();
33 let buf = "";
34 next();
35 process.stdin.setEncoding("utf8");
36 process.stdin.on("data", (data) => {
37 const lines = (buf + data).split("\n");
38 buf = lines.pop();
39 lines.forEach(next);
40 });
41 process.stdin.on("end", () => {
42 buf && next(buf);
43 gen.throw(new EOFError());
44 });
45}
461function subarraySum(arr: number[], target: number): number[] {
2 const prefixSums = new Map<number, number>([[0, 0]]);
3 let curSum = 0;
4 for (let i = 0; i < arr.length; i++) {
5 curSum += arr[i];
6 const complement = curSum - target;
7 if (prefixSums.has(complement)) {
8 return [prefixSums.get(complement)!, i + 1];
9 }
10 prefixSums.set(curSum, i + 1);
11 }
12 return [];
13}
14
15function splitWords(s: string): string[] {
16 return s === "" ? [] : s.split(" ");
17}
18
19function* main() {
20 const arr = splitWords(yield).map((v) => parseInt(v));
21 const target = parseInt(yield);
22 const res = subarraySum(arr, target);
23 console.log(res.join(" "));
24}
25
26class EOFError extends Error {}
27{
28 const gen = main();
29 const next = (line?: string) => gen.next(line ?? "").done && process.exit();
30 let buf = "";
31 next();
32 process.stdin.setEncoding("utf8");
33 process.stdin.on("data", (data) => {
34 const lines = (buf + data).split("\n");
35 buf = lines.pop() ?? "";
36 lines.forEach(next);
37 });
38 process.stdin.on("end", () => {
39 buf && next(buf);
40 gen.throw(new EOFError());
41 });
42}
431#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <limits>
5#include <sstream>
6#include <string>
7#include <unordered_map>
8#include <vector>
9
10std::vector<int> subarray_sum(std::vector<int> arr, int target) {
11 std::unordered_map<int, int> prefix_sums;
12 // an empty subarray has a sum of 0
13 prefix_sums[0] = 0;
14 int cur_sum = 0;
15 for (int i = 0; i < arr.size(); i++) {
16 cur_sum += arr[i];
17 int complement = cur_sum - target;
18 if (prefix_sums.count(complement)) {
19 return {prefix_sums[complement], i + 1};
20 }
21 prefix_sums[cur_sum] = i + 1;
22 }
23 // return no indices if arr is empty
24 return {};
25}
26
27template<typename T>
28std::vector<T> get_words() {
29 std::string line;
30 std::getline(std::cin, line);
31 std::istringstream ss{line};
32 ss >> std::boolalpha;
33 std::vector<T> v;
34 std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
35 return v;
36}
37
38void ignore_line() {
39 std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
40}
41
42template<typename T>
43void put_words(const std::vector<T>& v) {
44 if (!v.empty()) {
45 std::copy(v.begin(), std::prev(v.end()), std::ostream_iterator<T>{std::cout, " "});
46 std::cout << v.back();
47 }
48 std::cout << '\n';
49}
50
51int main() {
52 std::vector<int> arr = get_words<int>();
53 int target;
54 std::cin >> target;
55 ignore_line();
56 std::vector<int> res = subarray_sum(arr, target);
57 put_words(res);
58}
591def subarray_sum(arr, target)
2 # prefix_sum 0 happens when we have an empty array
3 prefix_sums = { 0 => 0 }
4 cur_sum = 0
5 arr.each_with_index do |num, i|
6 cur_sum += num
7 complement = cur_sum - target
8 if prefix_sums.key?(complement)
9 return [prefix_sums[complement], i + 1]
10 end
11 prefix_sums[cur_sum] = i + 1
12 end
13 []
14end
15
16if __FILE__ == $0
17 arr = gets.split.map { |v| Integer(v, 10) }
18 target = Integer(gets, 10)
19 res = subarray_sum(arr, target)
20 puts(res.join(' '))
21end
22Implementation notes
Many implementations define prefix_sum[i] as the sum of elements from index 0 to i-1 (not including element i). This makes prefix_sum[0] equal to 0, representing the sum of an empty array. This definition simplifies the code: when a subarray starting at index 0 sums to the target, we detect it by checking if current_sum - target = 0 exists in the dictionary.
The dictionary value can store either the index where the prefix sum was seen or the next index after it. Both approaches work, but you must be consistent about whether the returned indices are inclusive or exclusive.
Follow-up: Count all subarrays
Find the total number of subarrays that sum to the target.
Explanation for counting
Instead of returning the first matching subarray, count all subarrays that sum to the target. The core approach remains the same, but change what the dictionary stores. Map prefix_sum → frequency instead of prefix_sum → index. The frequency tracks how many times each prefix sum has appeared.
When the current sum is S and S - target has appeared F times previously, there are F different subarrays ending at the current position that sum to the target. Add F to the total count.
Consider [1, 2, 3] with target = 3. Initialize prefix_map = {0: 1} and count = 0.
At index 0: sum = 1. Check 1 - 3 = -2 (not in map, count stays 0). Store {0: 1, 1: 1}.
At index 1: sum = 3. Check 3 - 3 = 0 (found with frequency 1, so count += 1). Store {0: 1, 1: 1, 3: 1}.
At index 2: sum = 6. Check 6 - 3 = 3 (found with frequency 1, so count += 1). Store {0: 1, 1: 1, 3: 1, 6: 1}.
Final count: 2, representing subarrays [1, 2] (indices 0-1) and [3] (index 2).
The algorithm runs in O(n) time with O(n) space, processing each element once and updating counts in constant time.
1from collections import Counter
2
3def subarray_sum_total(arr: list[int], target: int) -> int:
4 prefix_sums: Counter[int] = Counter()
5 prefix_sums[0] = 1 # since empty array's sum is 0
6 cur_sum = 0
7 count = 0
8 for val in arr:
9 cur_sum += val
10 complement = cur_sum - target
11 if complement in prefix_sums:
12 count += prefix_sums[complement]
13 prefix_sums[cur_sum] += 1
14 return count
15
16if __name__ == "__main__":
17 arr = [int(x) for x in input().split()]
18 target = int(input())
19 res = subarray_sum_total(arr, target)
20 print(res)
211import java.util.Arrays;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Scanner;
5import java.util.stream.Collectors;
6
7class Solution {
8 public static int subarraySumTotal(List<Integer> arr, int target) {
9 HashMap<Integer, Integer> prefixSums = new HashMap<>();
10 prefixSums.put(0, 1); // since empty array's sum is 0
11 int curSum = 0;
12 int count = 0;
13 for (int val : arr) {
14 curSum += val;
15 int complement = curSum - target;
16 if (prefixSums.containsKey(complement)) {
17 count += prefixSums.get(complement);
18 }
19 if (prefixSums.containsKey(curSum)) {
20 prefixSums.replace(curSum, prefixSums.get(curSum) + 1);
21 } else {
22 prefixSums.put(curSum, 1);
23 }
24 }
25 return count;
26 }
27
28 public static List<String> splitWords(String s) {
29 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
30 }
31
32 public static void main(String[] args) {
33 Scanner scanner = new Scanner(System.in);
34 List<Integer> arr = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
35 int target = Integer.parseInt(scanner.nextLine());
36 scanner.close();
37 int res = subarraySumTotal(arr, target);
38 System.out.println(res);
39 }
40}
411"use strict";
2
3function subarraySumTotal(arr, target) {
4 const prefixSums = new Map();
5 prefixSums.set(0, 1); // since empty array's sum is 0
6 let curSum = 0;
7 let count = 0;
8 for (const val of arr) {
9 curSum += val;
10 const complement = curSum - target;
11 if (prefixSums.has(complement)) {
12 count += prefixSums.get(complement);
13 }
14 if (prefixSums.has(curSum)) {
15 prefixSums.set(curSum, prefixSums.get(curSum) + 1);
16 } else {
17 prefixSums.set(curSum, 1);
18 }
19 }
20 return count;
21}
22
23function splitWords(s) {
24 return s === "" ? [] : s.split(" ");
25}
26
27function* main() {
28 const arr = splitWords(yield).map((v) => parseInt(v));
29 const target = parseInt(yield);
30 const res = subarraySumTotal(arr, target);
31 console.log(res);
32}
33
34class EOFError extends Error {}
35{
36 const gen = main();
37 const next = (line) => gen.next(line).done && process.exit();
38 let buf = "";
39 next();
40 process.stdin.setEncoding("utf8");
41 process.stdin.on("data", (data) => {
42 const lines = (buf + data).split("\n");
43 buf = lines.pop();
44 lines.forEach(next);
45 });
46 process.stdin.on("end", () => {
47 buf && next(buf);
48 gen.throw(new EOFError());
49 });
50}
511function subarraySumTotal(arr: number[], target: number): number {
2 const prefixSums = new Map<number, number>();
3 prefixSums.set(0, 1);
4 let curSum = 0;
5 let count = 0;
6 for (const val of arr) {
7 curSum += val;
8 const complement = curSum - target;
9 if (prefixSums.has(complement)) {
10 count += prefixSums.get(complement)!;
11 }
12 if (prefixSums.has(curSum)) {
13 prefixSums.set(curSum, prefixSums.get(curSum)! + 1);
14 } else {
15 prefixSums.set(curSum, 1);
16 }
17 }
18 return count;
19}
20
21function splitWords(s: string): string[] {
22 return s === "" ? [] : s.split(" ");
23}
24
25function* main() {
26 const arr = splitWords(yield).map((v) => parseInt(v));
27 const target = parseInt(yield);
28 const res = subarraySumTotal(arr, target);
29 console.log(res);
30}
31
32class EOFError extends Error {}
33{
34 const gen = main();
35 const next = (line?: string) => gen.next(line ?? "").done && process.exit();
36 let buf = "";
37 next();
38 process.stdin.setEncoding("utf8");
39 process.stdin.on("data", (data) => {
40 const lines = (buf + data).split("\n");
41 buf = lines.pop() ?? "";
42 lines.forEach(next);
43 });
44 process.stdin.on("end", () => {
45 buf && next(buf);
46 gen.throw(new EOFError());
47 });
48}
491#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <limits>
5#include <sstream>
6#include <string>
7#include <unordered_map>
8#include <vector>
9
10int subarray_sum_total(std::vector<int>& arr, int target) {
11 std::unordered_map<int, int> prefix_sums;
12 prefix_sums[0] = 1; // an empty array has a sum of 0
13 int cur_sum = 0;
14 int count = 0;
15 for (int val : arr) {
16 cur_sum += val;
17 int complement = cur_sum - target;
18 if (prefix_sums.count(complement)) {
19 count += prefix_sums[complement];
20 }
21 prefix_sums[cur_sum] += 1;
22 }
23 return count;
24}
25
26template<typename T>
27std::vector<T> get_words() {
28 std::string line;
29 std::getline(std::cin, line);
30 std::istringstream ss{line};
31 ss >> std::boolalpha;
32 std::vector<T> v;
33 std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
34 return v;
35}
36
37void ignore_line() {
38 std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
39}
40
41int main() {
42 std::vector<int> arr = get_words<int>();
43 int target;
44 std::cin >> target;
45 ignore_line();
46 int res = subarray_sum_total(arr, target);
47 std::cout << res << '\n';
48}
491def subarray_sum_total(arr, target)
2 prefix_sums = Hash.new(0)
3 prefix_sums[0] = 1 # since empty array's sum is 0
4 cur_sum = 0
5 count = 0
6 arr.each do |val|
7 cur_sum += val
8 complement = cur_sum - target
9 if prefix_sums.key?(complement)
10 count += prefix_sums[complement]
11 end
12 prefix_sums[cur_sum] += 1
13 end
14 count
15end
16
17if __FILE__ == $0
18 arr = gets.split.map { |v| Integer(v, 10) }
19 target = Integer(gets, 10)
20 res = subarray_sum_total(arr, target)
21 puts(res)
22end
23