Subarray Sum Equals K

Difficulty: Medium

Problem

Count the contiguous stretches of nums whose elements add up to exactly k, and return that count. Stretches at different positions are counted separately even when their values look the same.

Example

Input: nums = [2, 1, 2, 1, 2], k = 3
Output: 4
Explanation: Four stretches sum to 3: [2,1] at indices 0..1, [1,2] at 1..2, [2,1] at 2..3 and [1,2] at 3..4.

Brute-force approach

Try every start index and compute sums for every end index.

Steps

  1. For each start i, initialize sum = 0
  2. For each end j >= i, add nums[j] to sum
  3. If sum == k, increment answer

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • Too slow for large inputs (n can be up to 20,000)
  • Repeatedly recomputes overlapping sums

Optimal approach

Key insight: A subarray ending at index j sums to k if there exists a previous prefix sum equal to (currentPrefix - k).

Maintain a running prefix sum and a hash map of how many times each prefix sum has appeared.

Steps

  1. Initialize freq[0] = 1 (empty prefix)
  2. Scan array, updating prefixSum
  3. Add freq[prefixSum - k] to answer
  4. Increment freq[prefixSum]

Time complexity: O(n) · Space complexity: O(n)

Pseudocode

function subarraySum(nums, k):
    count = 0
    prefixSum = 0
    freq = hashmap with {0: 1}
    for each x in nums:
        prefixSum += x
        needed = prefixSum - k
        if needed in freq:
            count += freq[needed]
        freq[prefixSum] = freq.get(prefixSum, 0) + 1
    return count

Hints

  • Think prefix sums: sum(i..j) = prefix[j] - prefix[i-1]
  • You want prefix[i-1] = prefix[j] - k
  • Store counts of prefix sums in a hash map

Complexity questions

What is the time complexity of checking all subarrays?

O(n²). There are O(n²) subarrays, and we can compute each sum incrementally in the inner loop.

Time complexity of prefix sum + hash map?

O(n). Single pass, with O(1) average hash operations.

Why is the space complexity O(n)?

We store frequency for prefix sums. In the worst case, each prefix sum is different and stored in the hash map.

Check your understanding of Subarray Sum Equals K

What does 'continuous subarray' mean?

Elements that appear next to each other. A subarray is a contiguous block of elements.

For nums = [1, 2, 3] and k = 3, how many subarrays sum to 3?

2 (subarrays [1,2] and [3]). The subarrays that sum to 3 are [1,2] (indices 0..1) and [3] (index 2). That's 2 subarrays.

Related problems

Keep practising