Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Subarray Sum Equals K

MEDIUMProblemSolveExternal Links

Description

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

A subarray is a contiguous, non-empty sequence of elements within the array. For example, in the array [1, 2, 3], the subarrays are [1], [2], [3], [1, 2], [2, 3], and [1, 2, 3].

Note that the array can contain negative numbers, which means that the sum of a subarray does not necessarily increase as the subarray grows longer. This rules out techniques like sliding window that rely on monotonically increasing sums.

Examples

Example 1

Input: nums = [1, 1, 1], k = 2

Output: 2

Explanation: There are two subarrays that sum to 2:

  • The subarray [1, 1] starting at index 0 and ending at index 1 (sum = 1 + 1 = 2)
  • The subarray [1, 1] starting at index 1 and ending at index 2 (sum = 1 + 1 = 2)

Note that these are two distinct subarrays even though they contain the same values, because they occupy different positions in the array.

Example 2

Input: nums = [1, 2, 3], k = 3

Output: 2

Explanation: There are two subarrays that sum to 3:

  • The subarray [1, 2] starting at index 0 and ending at index 1 (sum = 1 + 2 = 3)
  • The single element [3] at index 2 (sum = 3)

Note that [1, 2, 3] sums to 6, not 3, so it does not count.

Example 3

Input: nums = [1, -1, 0], k = 0

Output: 3

Explanation: Three subarrays sum to 0:

  • [1, -1] at indices 0-1 (sum = 1 + (-1) = 0)
  • [-1, 0] at indices 1-2 (sum = -1 + 0 = 0, wait — this actually sums to -1, so let me reconsider).

Actually the three subarrays are:

  • [1, -1] at indices 0-1 (sum = 0)
  • [0] at index 2 (sum = 0)
  • [1, -1, 0] at indices 0-2 (sum = 0)

This example shows that negative numbers and zeros create multiple overlapping subarrays with the same target sum.

Constraints

  • 1 ≤ nums.length ≤ 2 × 10^4
  • -1000 ≤ nums[i] ≤ 1000
  • -10^7 ≤ k ≤ 10^7

Editorial

Brute Force

Intuition

The most natural approach is to consider every possible subarray and compute its sum. If the sum equals k, we increment our count.

Think of it like reading a book and looking for paragraphs of a certain word count. You start from the first word, count forward to every possible stopping point, and check the word count. Then you move to the second word and repeat. You try every possible starting and ending position.

For each starting index i, we extend the subarray one element at a time to every ending index j ≥ i, maintaining a running sum. Whenever this running sum equals k, we have found a valid subarray.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3], k = 3:

Step 1: Fix starting index i = 0. Initialize running sum = 0.

Step 2: Extend to j = 0: sum = 0 + nums[0] = 0 + 1 = 1. Is 1 == 3? No.

Step 3: Extend to j = 1: sum = 1 + nums[1] = 1 + 2 = 3. Is 3 == 3? YES. Count = 1.

Step 4: Extend to j = 2: sum = 3 + nums[2] = 3 + 3 = 6. Is 6 == 3? No.

Step 5: Move to starting index i = 1. Reset running sum = 0.

Step 6: Extend to j = 1: sum = 0 + nums[1] = 0 + 2 = 2. Is 2 == 3? No.

Step 7: Extend to j = 2: sum = 2 + nums[2] = 2 + 3 = 5. Is 5 == 3? No.

Step 8: Move to starting index i = 2. Reset running sum = 0.

Step 9: Extend to j = 2: sum = 0 + nums[2] = 0 + 3 = 3. Is 3 == 3? YES. Count = 2.

Result: 2 subarrays found: [1,2] and [3].

Brute Force — Enumerate All Subarrays — For each starting index i, extend the subarray one element at a time, maintaining a running sum and checking if it equals k.

Algorithm

  1. Initialize count = 0
  2. For each starting index i from 0 to n-1:
    • Initialize sum = 0
    • For each ending index j from i to n-1:
      • Add nums[j] to sum
      • If sum == k, increment count
  3. Return count

Code

#include <vector>
using namespace std;

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum == k) {
                    count++;
                }
            }
        }
        
        return count;
    }
};
class Solution:
    def subarraySum(self, nums: list[int], k: int) -> int:
        n = len(nums)
        count = 0
        
        for i in range(n):
            running_sum = 0
            for j in range(i, n):
                running_sum += nums[j]
                if running_sum == k:
                    count += 1
        
        return count
class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum == k) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times. For each starting index i, the inner loop runs up to n - i times. The total number of iterations is n + (n-1) + (n-2) + ... + 1 = n(n+1)/2, which simplifies to O(n²). Each inner iteration performs a constant amount of work (one addition and one comparison).

Space Complexity: O(1)

We only use a few integer variables (count, sum, i, j). No additional data structures that grow with input size are needed.

Why This Approach Is Not Efficient

The brute force takes O(n²) time. With n up to 2 × 10^4, that means up to 4 × 10^8 operations — likely too slow for typical time limits.

The fundamental problem is that we recompute overlapping subarray sums from scratch. When we compute the sum of [1, 2, 3] after already computing [1, 2], we could have just added 3 to the previous sum. While our optimized brute force already does this with a running sum, we still iterate over all O(n²) subarrays.

The deeper insight is about prefix sums: the sum of any subarray nums[i..j] equals prefix[j+1] - prefix[i], where prefix[m] is the sum of the first m elements. So finding subarrays with sum k is equivalent to finding pairs of prefix sums whose difference is k. We can find such pairs in O(n) time using a hash map — the same idea as the Two Sum problem applied to prefix sums.

Optimal Approach - Prefix Sum with Hash Map

Intuition

This approach combines two powerful ideas: prefix sums and hash map lookups.

A prefix sum at position i is the sum of all elements from the start of the array up to index i. If we denote the prefix sum at position j as P[j], then the sum of any subarray nums[i+1..j] is simply P[j] - P[i].

So the question "how many subarrays ending at position j have sum k?" becomes: "how many earlier prefix sums P[i] satisfy P[j] - P[i] = k?" — which rearranges to: "how many earlier prefix sums equal P[j] - k?"

This is essentially the Two Sum problem applied to prefix sums! Instead of finding two numbers that add to a target, we find two prefix sums whose difference is k.

We maintain a hash map that counts how many times each prefix sum value has occurred so far. As we compute each new prefix sum, we check how many times (current_prefix_sum - k) has appeared before — each such occurrence represents one valid subarray ending at the current position.

The map is initialized with {0: 1} because a prefix sum of 0 exists before we start (representing the empty prefix). This handles the case where a subarray from the very beginning has sum k.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3], k = 3:

Step 1: Initialize: prefix_count = {0: 1}, prefix_sum = 0, count = 0.

Step 2: Process nums[0] = 1.

  • Update prefix_sum = 0 + 1 = 1
  • Need = prefix_sum - k = 1 - 3 = -2
  • Is -2 in prefix_count? NO → 0 new subarrays
  • Store prefix_sum: prefix_count = {0: 1, 1: 1}

Step 3: Process nums[1] = 2.

  • Update prefix_sum = 1 + 2 = 3
  • Need = prefix_sum - k = 3 - 3 = 0
  • Is 0 in prefix_count? YES, with count 1 → 1 new subarray (the subarray [1, 2] from index 0 to 1)
  • count = 0 + 1 = 1
  • Store prefix_sum: prefix_count = {0: 1, 1: 1, 3: 1}

Step 4: Process nums[2] = 3.

  • Update prefix_sum = 3 + 3 = 6
  • Need = prefix_sum - k = 6 - 3 = 3
  • Is 3 in prefix_count? YES, with count 1 → 1 new subarray (the subarray [3] at index 2)
  • count = 1 + 1 = 2
  • Store prefix_sum: prefix_count = {0: 1, 1: 1, 3: 1, 6: 1}

Result: count = 2. The two valid subarrays are [1, 2] and [3].

Prefix Sum + Hash Map — One-Pass Subarray Counting — Watch how we maintain a running prefix sum and use a hash map of prefix sum frequencies to instantly count how many valid subarrays end at each position.

Algorithm

  1. Initialize a hash map prefix_count with {0: 1} (the empty prefix has sum 0)
  2. Initialize prefix_sum = 0 and count = 0
  3. For each element num in the array:
    a. Update prefix_sum += num
    b. Calculate need = prefix_sum - k
    c. If need exists in prefix_count, add prefix_count[need] to count
    d. Increment prefix_count[prefix_sum] by 1
  4. Return count

Critical detail: Step 3c (checking the map) must happen BEFORE step 3d (updating the map). If we update first, we might count the current prefix sum against itself, which would correspond to an empty subarray.

Code

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> prefixCount;
        prefixCount[0] = 1;  // Empty prefix has sum 0
        
        int prefixSum = 0;
        int count = 0;
        
        for (int num : nums) {
            prefixSum += num;
            
            // Check if (prefixSum - k) was seen before
            int need = prefixSum - k;
            if (prefixCount.count(need)) {
                count += prefixCount[need];
            }
            
            // Record current prefix sum
            prefixCount[prefixSum]++;
        }
        
        return count;
    }
};
from collections import defaultdict

class Solution:
    def subarraySum(self, nums: list[int], k: int) -> int:
        prefix_count = defaultdict(int)
        prefix_count[0] = 1  # Empty prefix has sum 0
        
        prefix_sum = 0
        count = 0
        
        for num in nums:
            prefix_sum += num
            
            # Check if (prefix_sum - k) was seen before
            need = prefix_sum - k
            count += prefix_count[need]
            
            # Record current prefix sum
            prefix_count[prefix_sum] += 1
        
        return count
import java.util.*;

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> prefixCount = new HashMap<>();
        prefixCount.put(0, 1);  // Empty prefix has sum 0
        
        int prefixSum = 0;
        int count = 0;
        
        for (int num : nums) {
            prefixSum += num;
            
            // Check if (prefixSum - k) was seen before
            int need = prefixSum - k;
            count += prefixCount.getOrDefault(need, 0);
            
            // Record current prefix sum
            prefixCount.put(prefixSum, 
                prefixCount.getOrDefault(prefixSum, 0) + 1);
        }
        
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make a single pass through the array of n elements. At each step, we perform one addition (updating prefix sum), one hash map lookup (checking if prefix_sum - k exists), and one hash map update (recording the current prefix sum). Each of these operations takes O(1) average time. Total: n × O(1) = O(n).

Space Complexity: O(n)

In the worst case (all distinct prefix sums), the hash map stores up to n + 1 entries (including the initial prefix sum 0). Each entry is a key-value pair of integers, so the total extra space is O(n). This is the same space as the hash map counting approach, but the time improved from O(n²) to O(n) — a significant improvement for large inputs.