Subarray Sum Equals K Using Hash Map in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the count of subarrays to zero.

DSA Python

count = [1]

Drag options to blanks, or click blank then click option'

ANone

B1

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Starting count from 1 or None instead of 0.

We start counting subarrays from zero because initially we have found none.

2fill in blank

medium

Complete the code to update the cumulative sum with the current number.

DSA Python

cumulative_sum [1] num

Drag options to blanks, or click blank then click option'

A+=

B/=

C*=

D-=

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition.

We add the current number to the cumulative sum to keep track of the total so far.

3fill in blank

hard

Fix the error in checking if (cumulative_sum - k) exists in the hash map.

DSA Python

if (cumulative_sum [1] k) in prefix_sums:

Drag options to blanks, or click blank then click option'

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition or multiplication instead of subtraction.

We subtract k from cumulative_sum to find if a previous prefix sum exists that forms a subarray summing to k.

4fill in blank

hard

Fill both blanks to update the hash map with the current cumulative sum count.

DSA Python

prefix_sums[cumulative_sum] = prefix_sums.get([1], 0) [2] 1

Drag options to blanks, or click blank then click option'

Acumulative_sum

B+

C-

Dcount

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong key or subtracting instead of adding.

We get the current count of cumulative_sum in the map and add 1 to update it.

5fill in blank

hard

Fill all three blanks to complete the function that returns the count of subarrays summing to k.

DSA Python

def subarray_sum(nums, k):
    count = 0
    cumulative_sum = 0
    prefix_sums = [1]
    prefix_sums[0] = 1
    for num in nums:
        cumulative_sum [2] num
        if (cumulative_sum - k) in prefix_sums:
            count += prefix_sums[cumulative_sum - k]
        prefix_sums[cumulative_sum] = prefix_sums.get(cumulative_sum, 0) [3] 1
    return count

Drag options to blanks, or click blank then click option'

A{}

B+=

Cdefaultdict(int)

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using defaultdict without import, wrong operators, or wrong dictionary initialization.

We use a normal dictionary to store prefix sums, add current number to cumulative_sum, and add 1 to the count in the dictionary.

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