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.