Subarray Sum Equals K DSA Solution

Learning Outcome

After this lesson, you should be able to convert subarray sum questions into prefix sum difference lookups.

Problem Statement

Given nums and k, return the number of continuous subarrays whose sum equals k.

Input	Output	Why
`nums = [1,1,1], k = 2`	`2`	The subarrays at indexes 0..1 and 1..2 both sum to 2.

Brute Force Approach

Check every start and end index and compute each subarray sum. This is quadratic.

Optimized Approach

Maintain a running prefix sum. If currentSum - k appeared before, each occurrence forms a valid subarray ending here.

Exact Pseudocode

freq[0] = 1
sum = 0
answer = 0
for x in nums:
  sum += x
  answer += freq[sum - k]
  freq[sum] += 1
return answer

Reference Code

from collections import defaultdict

class Solution:
    def subarraySum(self, nums, k):
        freq = defaultdict(int)
        freq[0] = 1
        total = 0
        answer = 0

        for x in nums:
            total += x
            answer += freq[total - k]
            freq[total] += 1

        return answer

Sample Dry Run

Step	State	Result
Start	freq[0] = 1	Subarrays from index 0 are counted
First 1	sum = 1, need -1	answer = 0
Second 1	sum = 2, need 0	answer = 1
Third 1	sum = 3, need 1	answer = 2

Complexity

Measure	Value	Reason
Time	O(n)	Each number updates the running sum and hash map once.
Space	O(n)	The map can store many distinct prefix sums.

Edge Cases

Negative numbers make sliding window unreliable.
freq[0] is required for subarrays starting at index 0.
Multiple equal prefix sums must be counted, not just stored as true or false.

Interview Checklist

Use prefix sum difference currentSum - k.
Add existing frequency before incrementing current sum frequency.
Store counts, not just a set.

FAQs

Why does currentSum - k matter?

If an earlier prefix equals currentSum - k, the subarray after that prefix sums to k.

Why not use sliding window?

Sliding window fails when negative numbers can shrink or grow sums unpredictably.

What is the core pattern?

Prefix sum with hash map frequency.

Subarray Sum Equals K: Prefix Sum Hashmap Pattern