Data Structures & Algorithms (Prefix Sum): Subarray Sum Equals K

January 20, 2026

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

Example 1:

Input: nums = [1, -1, 1, -1, 2, 3, 3, 4, 1, 5, 2], k = 8
Output: 5
Explanation: [1, -1, 1, -1, 2, 3, 3], [1,-1, 2, 3, 3], [2, 3, 3], [3, 4, 1] and [1, 5, 2] 
             are all possible subarrays whose sum = 8.

Playground: Leetcode 560

Naive Approach - Nested Loops

Iterate over all possible subarrays while maintaining a running sum for each subarray. Whenever the sum becomes equal to k, increment the count of eligible subarrays.

Algorithm

1. Initialize a variable: "count" to track the number of eligible subarrays.

2. Iterate over each index in "nums", treating it as the starting index of the current subarray.
    3. Initialize a variable: "currentSubarraySum = 0" to store the cumulative sum of the current subarray.

    4. Starting from the current index, expand the subarray one element at a time.
        5. Add the current element to "currentSubarraySum".
        6. If "currentSubarraySum" equals "k", increment "count" by 1.

7. Return "count".

Implementation

Sample inputs
1public int subarraySum(int[] nums, int k) {
2
3 //1. Initialize a variable to track the number of eligible subarrays.
4 int count = 0;
5
6 // 2. Iterate over each index in "nums", treating it as the starting index of the current subarray.
7 for (int i = 0; i < nums.length; i++) {
8 // 3. Initialize a variable to store the cumulative sum of the current subarray.
9 int currentSubarraySum = 0;
10
11 // 4. Starting from the current index, expand the subarray one element at a time.
12 for (int j = i; j < nums.length; j++) {
13 // 5. Add the current element to the current subarray sum.
14 currentSubarraySum += nums[j];
15 // 6. Check if the current current subarray sum is equal to "k"
16 if (currentSubarraySum == k) {
17 // 7. Increment count of eligible subarrays.
18 count++;
19 }
20 }
21
22 }
23
24 // 7. Return the count of eligible subarrays.
25 return count;
26
27}
k8
nums
j
j
j
j
j
j
j
j
j
j
j
1
-1
1
-1
2
3
3
4
1
5
2
i
i
i
i
i
i
i
i
i
i
i
0
1
2
3
4
5
6
7
8
9
10
Current subarray—
nums[i..j]
i = —
j = —
currentSubarraySum = —
Eligible subarrays
None yet
count
—
Ready
Press Play or Step. Highlighted lines, including the comments, are the ones executing.
0/227

Time Complexity

Updating and comparing currentSubarraySum are constant-time operations, O(1). Therefore, the time complexity depends on the total number of times these operations are performed.

The outer loop iterates over all n indices. For each starting index i, the inner loop traverses n - i elements.

Therefore, the total number of operations is:

(n - 0) + (n - 1) + (n - 2) + ... + + (n - (n-1))
= 1 + 2 + 3 + ... + n
= n(n + 1) / 2

Since n(n + 1) / 2 grows proportionally to n², the overall time complexity is O(n²).

Space Complexity

Since we are not using any additional data structures and only a few variables (count, currentSum), the extra space used does not grow with the input size.

Therefore, the overall space complexity is O(1).

Key Optimizations

Although we maintain a running sum within one iteration of the outer loop, we discard that information when the starting index changes. For every starting index, we restart currentSubarraySum from 0 and traverse the remaining elements.

Let's walk through the key intuition behind reducing this redundant work:

  1. The sum of any subarray can be obtained by subtracting two prefix sums. For example, in nums = [1, -1, 1, -1, 2, 3, 3, 4, 1, 5, 2], we have subarray [3, 4, 1] ending at index 8 whose sum can be obtained by subtracting prefixSum[5] from prefixSum[8].

key-observation-1

  1. There can be multiple subarrays ending at i whose sum equals k. For example, in nums = [1, -1, 1, -1, 2, 3, 3, 4, 1, 5, 2], the subarrays [1, -1, 1, -1, 2, 3, 3], [1,-1, 2, 3, 3], and [2, 3, 3] all end at index 6 and have a sum of 8.

key-observation-2

Suitable Approach - Prefix Sum

Instead of exploring every possible subarray, maintain a running prefix sum while traversing the array. At each index, check whether currentPrefixSum - k has appeared before.

Each occurrence represents a subarray ending at the current index whose sum is k.

Algorithm

1. Initialize 
    a. A variable: "count" to track the number of eligible subarrays.
    a. A variable: "currentPrefixSum" to track the cumulative sum observed so far.
    b. A frequency map: "prefixSumFrequencyMap" to track the frequencies of prefix sums 
       observed so far.

2. Add "{0: 1}" to handle the edge case where a subarray starting at index "0" has a sum 
   equal to "k".

3. Iterate over each element in "nums".
    4. Add the current element to "currentPrefixSum".
    5. If "prefixSumFrequencyMap" contains "currentPrefixSum - k", increment the "count" by 
       the frequency of "currentPrefixSum - k".
    6. Add or update the frequency of "currentPrefixSum" in "prefixSumFrequencyMap".

7. Return "count".

Implementation

Sample inputs
1public int subarraySum(int[] nums, int k) {
2
3 //1. Initialize a variable to track the number of eligible subarrays.
4 int count = 0;
5 // 2. Initialize a variable to track the cumulative sum observed so far.
6 int currentPrefixSum = 0;
7 // 3. Initialize a frequency map to track the frequencies of prefix sums observed so far.
8 Map<Integer, Integer> prefixSumFrequencyMap = new HashMap<>();
9
10 // 4. Add "{0: 1}" to handle the edge case where a subarray starting at index "0" has a sum equal to "k".
11 prefixSumFrequencyMap.put(0, 1);
12
13 // 5. Iterate over each element in "nums".
14 for (int num : nums) {
15 // 6. Add the current element to the current prefix sum.
16 currentPrefixSum += num;
17 // 7. Check if the prefix sum frequency map contains (current prefix sum - k).
18 if (prefixSumFrequencyMap.containsKey(currentPrefixSum - k)) {
19 // 8. Increment the count of eligible subarrays by the frequency of (current prefix sum - k).
20 int frequency = prefixSumFrequencyMap.get(currentPrefixSum - k);
21 count += frequency;
22 }
23 // 9. Add or update the frequency of the current prefix sum in the prefix sum frequency map.
24 prefixSumFrequencyMap.put(currentPrefixSum,
25 prefixSumFrequencyMap.getOrDefault(currentPrefixSum, 0) + 1
26 );
27
28 }
29
30 // 10. Return the count of eligible subarrays.
31 return count;
32
33}
k8
nums
num
num
num
num
num
num
num
num
num
num
num
1
-1
1
-1
2
3
3
4
1
5
2
0
1
2
3
4
5
6
7
8
9
10
num = —
currentPrefixSum = —
currentPrefixSum − k = —
prefixSumFrequencyMap
Empty
Eligible subarrays
None yet
count
—
Ready
Press Play or Step. Highlighted lines, including the comments, are the ones executing.
0/52

Time Complexity

Each iteration performs only constant-time operations, such as updating the prefix sum and performing HashMap lookups and updates. We traverse the array exactly once, so the loop runs n times.

Therefore, the overall time complexity is O(n) on average.

Space Complexity

In the worst case, all prefix sums are unique. Since we store each prefix sum in the HashMap, the map can contain up to n entries.

Therefore, the overall space complexity is O(n).