Subarray Sum Equals K Using Hash Map in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of subarray sum count with negative numbers

What is the output of the following code that counts subarrays summing to k using a hash map?

DSA Python

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

print(subarray_sum([1, -1, 0], 0))

A 3

B 2

C 1

D 0

💡 Hint

Think about all subarrays that sum to zero, including those with negative numbers.

The subarrays that sum to 0 are: [1, -1], [-1, 0], and [0]. So total count is 3.

❓ Predict Output

intermediate

Count subarrays summing to k with repeated elements

What does this code print when counting subarrays summing to 3?

DSA Python

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

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

A 4

B 3

C 5

D 2

💡 Hint

Count all subarrays that sum exactly to 3, including overlapping ones.

The subarrays summing to 3 are: [1,2], [2,1], [1,2], [2,1]. Total 4.

🔧 Debug

advanced

Identify the error in subarray sum code

What error does this code raise when run?

DSA Python

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

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

A 0

B KeyError

C 3

D TypeError

💡 Hint

Check if the initial sum_map contains the prefix sum 0.

sum_map is empty initially, so checking current_sum - k for 0 fails with KeyError.

❓ Predict Output

advanced

Output of subarray sum count with zeros and k=0

What is the output of this code counting subarrays summing to 0?

DSA Python

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

print(subarray_sum([0, 0, 0], 0))

A 1

B 3

C 6

D 0

💡 Hint

Count all subarrays of zeros that sum to zero.

All subarrays of zeros sum to zero: [0], [0], [0], [0,0], [0,0], [0,0,0] total 6.

🧠 Conceptual

expert

Why use a hash map for subarray sum equals k?

Which reason best explains why a hash map is used in the subarray sum equals k problem?

A To reverse the array for easier traversal

B To sort the array elements for binary search

C To store all subarrays explicitly for counting

D To store counts of prefix sums for quick lookup of needed sums

💡 Hint

Think about how prefix sums help find subarrays quickly.

The hash map stores counts of prefix sums to quickly find how many previous sums match current_sum - k.

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