Subarray Sum Equals K Using Hash Map in DSA Python - Execution Trace

Concept Flow - Subarray Sum Equals K Using Hash Map

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

↓

Iterate over array elements

↓

Add current element to sum

↓

Check if (sum-k) in map?

Yes No↓

Add map[sum-k

↓

Update map with current sum count

↓

Repeat for all elements

↓

Return count of subarrays

We keep a running sum and use a map to count how many times each sum appears. For each new sum, we check if sum-k exists to find subarrays summing to k.

Execution Sample

DSA Python

nums = [1, 2, 3]
k = 3
count = 0
sum = 0
map = {0:1}
for num in nums:
    sum += num
    if sum - k in map:
        count += map[sum - k]
    map[sum] = map.get(sum, 0) + 1
print(count)

This code counts how many subarrays sum to k by tracking cumulative sums and their frequencies.

Execution Table

Step	Operation	Current Num	Running Sum	Check sum-k in map	Map Update	Count	Visual State
0	Initialize	-	0	sum-k=0-3=-3 not in map	map={0:1}	0	{0:1}
1	Add num	1	1	1-3=-2 not in map	map={0:1,1:1}	0	{0:1,1:1}
2	Add num	2	3	3-3=0 in map with count=1	map={0:1,1:1,3:1}	1	{0:1,1:1,3:1}
3	Add num	3	6	6-3=3 in map with count=1	map={0:1,1:1,3:1,6:1}	2	{0:1,1:1,3:1,6:1}
4	End	-	-	-	-	2	Final count=2

💡 All elements processed, total count of subarrays summing to k is 2

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
sum	0	1	3	6	6
count	0	0	1	2	2
map	{0:1}	{0:1,1:1}	{0:1,1:1,3:1}	{0:1,1:1,3:1,6:1}	{0:1,1:1,3:1,6:1}

Key Moments - 3 Insights

Why do we initialize the map with {0:1} before starting?

Because a subarray starting from index 0 that sums to k means sum-k=0, so we count that initial zero sum once (see Step 0 in execution_table).

Why do we check if sum-k is in the map?

Because if sum-k exists, it means there is a previous prefix sum that allows the subarray between that point and current index to sum to k (see Steps 2 and 3 in execution_table).

Why do we update the map with the current sum after checking?

To include the current prefix sum for future subarray checks, ensuring we count all possible subarrays (see map updates in execution_table rows).

Visual Quiz - 3 Questions

Look at the execution_table at Step 2, what is the count value after processing the number 2?

A 0

B 1

C 2

D 3

💡 Hint

Check the 'Count' column at Step 2 in the execution_table.

At which step does the running sum first equal 3?

A Step 2

B Step 1

C Step 3

D Step 0

💡 Hint

Look at the 'Running Sum' column in the execution_table.

If the initial map did not contain {0:1}, what would be the count after processing all elements?

A 2

B 0

C 1

D 3

💡 Hint

Refer to the key_moments about why map starts with {0:1} and the count updates in execution_table.

Concept Snapshot

Subarray Sum Equals K Using Hash Map:
- Use a running sum to track cumulative sums.
- Store counts of sums in a map starting with {0:1}.
- For each element, add to sum, check if sum-k in map.
- Add map[sum-k] to count for subarrays ending here.
- Update map with current sum count.
- Return total count after full iteration.

Full Transcript

This concept uses a hash map to count how many subarrays sum to a target k. We keep a running sum of elements as we move through the array. The map stores how many times each sum has appeared. For each new sum, we check if sum minus k exists in the map. If yes, it means a subarray ending at the current index sums to k. We add the count of that sum-k to our total count. We then update the map with the current sum. We start the map with {0:1} to handle subarrays starting at index 0. The final count after processing all elements is the number of subarrays summing to 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