Prefix Sum
Given an integer array arr and a target value, return a subarray whose sum equals the target. Return the answer as [start, end), where start is inclusive and end is exclusive.
Input: arr = [1, -20, -3, 30, 5, 4], target = 7
Output: [1, 4]
The subarray arr[1:4] = [-20, -3, 30] sums to 7.
Try it yourself
Solution
Understanding the problem
A brute-force approach checks every subarray and computes each sum directly. With n numbers, there are about n(n+1)/2 candidate subarrays. If each sum takes up to O(n) time to compute, total time is O(n^3).
You can improve this to O(n^2) by extending ranges and reusing partial sums, but that still scans too many start and end pairs. We need to avoid searching all pairs.
Prefix sum transformation
Define prefix[k] as the sum of the first k elements, so prefix[0] = 0 and prefix[k] = arr[0] + ... + arr[k-1].
For any subarray arr[i:j], its sum is:
prefix[j] - prefix[i]
This turns the goal into finding indices i < j such that:
prefix[j] - prefix[i] = target
Rearranged:
prefix[i] = prefix[j] - target
Once you fix j, you only need to know whether prefix[j] - target appeared earlier.
Turn it into hash table lookup
Scan the array once while keeping a running prefix sum called current_sum. Also keep a hash table from prefix sum value to the index where it first appeared in prefix coordinates.
Start with prefix_map = {0: 0}. This means before reading any element, the sum is 0 at prefix index 0. This initialization is what lets us find subarrays that start at index 0.
At each array index idx, update current_sum += arr[idx]. Let j = idx + 1, because prefix[j] is the sum after consuming arr[idx]. Now check whether current_sum - target exists in prefix_map. If it does and equals i, then arr[i:j] sums to target, so return [i, j].
If it does not exist, store current_sum with value j and continue.
Walkthrough
Use arr = [1, -20, -3, 30, 5, 4], target = 7.
Start: current_sum = 0, prefix_map = {0: 0}.
At index 0, current_sum = 1, so we need 1 - 7 = -6. Not found. Store 1 -> 1.
At index 1, current_sum = -19, so we need -19 - 7 = -26. Not found. Store -19 -> 2.
At index 2, current_sum = -22, so we need -22 - 7 = -29. Not found. Store -22 -> 3.
At index 3, current_sum = 8, so we need 8 - 7 = 1. Found at prefix index 1, so answer is [1, 4].
One hash lookup per element gives linear time.
Complexity
Time complexity is O(n) because we scan once and each hash table operation is O(1) on average.
Space complexity is O(n) in the worst case when all prefix sums are distinct.
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
The article uses half-open ranges [start, end). If you return inclusive end indices instead, adjust by subtracting 1 from end.
You can store either the first or latest index for each prefix sum. For this problem, either works because any valid subarray is acceptable, but your index convention must stay consistent with how you compute j = idx + 1.
Follow-up: Count all subarrays
Return the number of subarrays whose sum equals target.
Explanation for counting
The prefix-sum equation stays the same, but the hash table now stores frequencies instead of one index.
Let freq[p] be how many times prefix sum p has appeared so far. Initialize freq = {0: 1} and count = 0.
While scanning, when current prefix sum is S, every earlier prefix sum equal to S - target forms one valid subarray ending at the current position. So add freq[S - target] to count, then increment freq[S].
Example: arr = [1, 2, 3], target = 3.
After reading 1, S = 1, S - target = -2, no match.
After reading 2, S = 3, S - target = 0, and freq[0] = 1, so count = 1.
After reading 3, S = 6, S - target = 3, and freq[3] = 1, so count = 2.
The two subarrays are [1, 2] and [3]. Time is O(n) and space is O(n).
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