Subarray Sum Equals K Using Hash Map in DSA Python

Mental Model

We keep track of sums of numbers from the start to each position and use a map to find if a previous sum allows a subarray to sum to k.

Analogy: Imagine walking along a path and counting steps. If you know the total steps at two points, subtracting them tells you how many steps you took between those points. The map remembers these totals to quickly find matching distances.

Array: [1, 2, 3, 4]
Prefix sums: 0 -> 1 -> 3 -> 6 -> 10
HashMap stores sums seen so far with their counts:
{0:1, 1:1, 3:1, 6:1, 10:1}
Looking for subarray sum k=6 means checking if current_sum - k exists in map.

Dry Run Walkthrough

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

Goal: Find how many continuous subarrays sum exactly to 3

Step 1: Start with sum=0, map={0:1} to count empty prefix

sum=0, map={0:1}

Why: We count empty prefix to handle subarrays starting at index 0

Step 2: Add first element 1 to sum -> sum=1; check if sum-k=1-3=-2 in map (no)

sum=1, map={0:1, 1:1}

Why: No subarray ending here sums to k, add sum to map

Step 3: Add second element 2 -> sum=3; check sum-k=3-3=0 in map (yes, count=1)

sum=3, map={0:1, 1:1, 3:1}, count=1

Why: Found subarray [1,2] sums to k, increment count

Step 4: Add third element 3 -> sum=6; check sum-k=6-3=3 in map (yes, count=1)

sum=6, map={0:1, 1:1, 3:1, 6:1}, count=2

Why: Found subarray [3] sums to k, increment count

Result:

Final count=2; subarrays are [1,2] and [3]

Annotated Code

DSA Python

class Solution:
    def subarraySum(self, nums: list[int], k: int) -> int:
        count = 0
        curr_sum = 0
        prefix_sums = {0: 1}  # sum 0 seen once
        for num in nums:
            curr_sum += num  # add current number to running sum
            if curr_sum - k in prefix_sums:
                count += prefix_sums[curr_sum - k]  # add count of prefix sums that match
            prefix_sums[curr_sum] = prefix_sums.get(curr_sum, 0) + 1  # record current sum
        return count

# Driver code
sol = Solution()
result = sol.subarraySum([1, 2, 3], 3)
print(result)

curr_sum += num # add current number to running sum

update running sum with current element

if curr_sum - k in prefix_sums:

check if a previous prefix sum allows subarray sum k

count += prefix_sums[curr_sum - k] # add count of prefix sums that match

increment count by number of matching prefix sums

prefix_sums[curr_sum] = prefix_sums.get(curr_sum, 0) + 1 # record current sum

record current prefix sum frequency

Output

2

Complexity Analysis

Time: O(n) because we traverse the array once and do constant time map operations

Space: O(n) because in worst case all prefix sums are unique and stored in the map

vs Alternative: Naive approach is O(n^2) by checking all subarrays; this method is much faster using prefix sums and a map

Edge Cases

empty array

returns 0 since no subarrays exist

DSA Python

for num in nums:

array with all zeros and k=0

counts all subarrays of zeros correctly using prefix sums

DSA Python

prefix_sums[curr_sum] = prefix_sums.get(curr_sum, 0) + 1

no subarray sums to k

returns 0 as count never increments

DSA Python

if curr_sum - k in prefix_sums:

When to Use This Pattern

When asked to find count of continuous subarrays with a target sum, use prefix sums with a hash map to track sums and find matches efficiently.

Common Mistakes

Mistake: Not initializing prefix_sums with {0:1}, missing subarrays starting at index 0
Fix: Initialize prefix_sums with {0:1} to count empty prefix sum

Mistake: Checking if curr_sum equals k instead of curr_sum - k in map
Fix: Check if curr_sum - k exists in prefix_sums to find valid subarrays

Summary

Counts how many continuous subarrays sum to a target k using prefix sums and a hash map.

Use when you need to find subarrays with a specific sum efficiently.

The key insight is that difference of prefix sums reveals subarray sums, and storing counts in a map lets you find matches fast.

Practice

1. What is the main purpose of using a hash map in the Subarray Sum Equals K problem?

easy

A. To sort the array elements before processing

B. To keep track of the maximum subarray length

C. To store the original array elements as keys

D. To store cumulative sums and their frequencies for quick lookup

Solution

1. Step 1: Understand the problem goal

   The problem requires finding the number of continuous subarrays whose sum equals a target value k.

2. Step 2: Role of hash map in solution

   A hash map stores cumulative sums encountered so far and their counts. This allows quick checking if a previous cumulative sum exists that can form a subarray summing to k.

3. Final Answer:

   To store cumulative sums and their frequencies for quick lookup -> Option D

4. Quick Check:

   Hash map stores sums [OK]

Hint: Hash map tracks sums to find subarrays fast [OK]

Common Mistakes:

• Thinking hash map stores array elements as keys
• Assuming sorting is needed
• Using hash map to track max length instead of sums

2. Which of the following is the correct way to initialize the hash map for cumulative sums in Python?

easy

A. hash_map = {0: 1}

B. hash_map = {}

C. hash_map = {k: 0}

D. hash_map = {None: 0}

Solution

1. Step 1: Understand initialization role

   We initialize the hash map with cumulative sum 0 having count 1 to handle subarrays starting from index 0.

2. Step 2: Check each option

   hash_map = {0: 1} correctly initializes with {0: 1}. hash_map = {} is empty, missing initial sum. hash_map = {k: 0} uses undefined k. hash_map = {None: 0} uses None key which is incorrect.

3. Final Answer:

   hash_map = {0: 1} -> Option A

4. Quick Check:

   Start with sum 0 count 1 [OK]

Hint: Start hash map with {0:1} for empty prefix sum [OK]

Common Mistakes:

• Not initializing with {0:1}
• Using empty dictionary without base case
• Using invalid keys like None or undefined variables

3. What is the output of the following code?

def subarray_sum(nums, k):
    count = 0
    cum_sum = 0
    hash_map = {0: 1}
    for num in nums:
        cum_sum += num
        if cum_sum - k in hash_map:
            count += hash_map[cum_sum - k]
        hash_map[cum_sum] = hash_map.get(cum_sum, 0) + 1
    return count

print(subarray_sum([1, 2, 3], 3))

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Trace cumulative sums and hash map updates

   nums = [1,2,3], k=3 - cum_sum=1, hash_map={0:1,1:1}, cum_sum-k= -2 not in map - cum_sum=3, hash_map={0:1,1:1,3:1}, cum_sum-k=0 in map count=1 - cum_sum=6, hash_map={0:1,1:1,3:1,6:1}, cum_sum-k=3 in map count=1+1=2

2. Step 2: Final count of subarrays

   Two subarrays sum to 3: [1,2] and [3].

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Subarrays [1,2], [3] = 2 [OK]

Hint: Count increments when cum_sum-k found in map [OK]

Common Mistakes:

• Not updating count correctly
• Ignoring initial hash_map entry
• Miscounting subarrays overlapping

4. Find the error in this code snippet for counting subarrays with sum k:

def subarray_sum(nums, k):
    count = 0
    cum_sum = 0
    hash_map = {0: 0}
    for num in nums:
        cum_sum += num
        if cum_sum - k in hash_map:
            count += hash_map[cum_sum - k]
        hash_map[cum_sum] = hash_map.get(cum_sum, 0) + 1
    return count

print(subarray_sum([1, 1, 1], 2))

medium

A. hash_map initialized with {0: 0} instead of {0: 1}

B. cum_sum should be reset inside the loop

C. count should be incremented by 1 instead of hash_map value

D. hash_map update line is missing

Solution

1. Step 1: Check hash_map initialization

   hash_map is initialized as {0: 0}, but it should be {0: 1} to count subarrays starting at index 0.

2. Step 2: Effect of wrong initialization

   With {0: 0}, the code misses counting subarrays that start from the beginning, leading to incorrect count.

3. Final Answer:

   hash_map initialized with {0: 0} instead of {0: 1} -> Option A

4. Quick Check:

   Initialize {0:1} to count empty prefix [OK]

Hint: Initialize hash_map with {0:1} to count prefix sums [OK]

Common Mistakes:

• Setting initial count to 0 instead of 1
• Resetting cum_sum inside loop incorrectly
• Ignoring hash_map update line

5. Given the array nums = [3, 4, 7, 2, -3, 1, 4, 2] and k = 7, how many subarrays sum to k? Use the hash map approach.

hard

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Calculate cumulative sums and track counts

   nums = [3,4,7,2,-3,1,4,2], k=7
   - cum=3, -4 not, map={0:1,3:1}, count=0
   - cum=7, 0 yes (+1), count=1, map={...,7:1}
   - cum=14, 7 yes (+1), count=2, map={...,14:1}
   - cum=16, 9 no, count=2, map={...,16:1}
   - cum=13, 6 no, count=2, map={...,13:1}
   - cum=14, 7 yes (+1), count=3, map={...,14:2}
   - cum=18, 11 no, count=3, map={...,18:1}
   - cum=20, 13 yes (+1), count=4, map={...,20:1}

2. Step 2: Count total subarrays

   Four subarrays sum to 7: [3,4], [7], [7,2,-3,1], [1,4,2].

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Count subarrays using cum_sum and map = 4 [OK]

Hint: Add counts when (cum_sum - k) found in map [OK]

Common Mistakes:

• Not counting repeated cumulative sums correctly
• Forgetting negative numbers affect sums
• Miscounting overlapping subarrays