Subarray Sum Equals K Using Hash Map in DSA C - 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?

↓

Add map[sum-k

↓

Add/update sum in map

↓

Repeat for next element

↓

End

↓

Return total count of subarrays

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

Execution Sample

DSA C

int subarraySum(int* nums, int numsSize, int k) {
    int count = 0, sum = 0;
    unordered_map<int,int> map;
    map[0] = 1;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
        if (map.find(sum - k) != map.end()) count += map[sum - k];
        map[sum]++;
    }
    return count;
}

This code counts subarrays whose sum equals k using a hash map to track prefix sums.

Execution Table

Step	Operation	Current Element	Running Sum	Check sum-k in map	Map State	Count	Visual State
1	Initialize	N/A	0	N/A	{0:1}	0	[]
2	Add nums[0]	1	1	1-3=-2 not in map	{0:1,1:1}	0	[1]
3	Add nums[1]	2	3	3-3=0 in map with count=1	{0:1,1:1,3:1}	1	[1,2]
4	Add nums[2]	-1	2	2-3=-1 not in map	{0:1,1:1,3:1,2:1}	1	[1,2,-1]
5	Add nums[3]	1	3	3-3=0 in map with count=1	{0:1,1:1,3:2,2:1}	2	[1,2,-1,1]
6	Add nums[4]	2	5	5-3=2 in map with count=1	{0:1,1:1,3:2,2:1,5:1}	3	[1,2,-1,1,2]
7	Add nums[5]	-1	4	4-3=1 in map with count=1	{0:1,1:2,3:2,2:1,5:1,4:1}	4	[1,2,-1,1,2,-1]
8	End	N/A	N/A	N/A	Final map	4	Final array

💡 All elements processed, total count of subarrays with sum k is 4

Variable Tracker

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

Key Moments - 3 Insights

Why do we initialize 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 as one occurrence. This is shown in step 1 where map starts with {0:1}.

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. This is seen in steps 3, 5, 6, and 7 where count increases.

Why do we increment map[sum] after checking?

We increment map[sum] to record that this running sum has appeared one more time, so future subarrays can use it. This happens after count update in each step.

Visual Quiz - 3 Questions

Look at the execution table at step 5. What is the running sum and count?

A Running sum=3, count=2

B Running sum=5, count=3

C Running sum=3, count=1

D Running sum=2, count=1

💡 Hint

Check the 'Running Sum' and 'Count' columns in row 5 of the execution table.

At which step does the count first increase from 0 to 1?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Count' column in the execution table and find where it changes from 0 to 1.

If the target k was changed to 4, how would the count change at step 6?

A Count would increase by 1

B Count would remain the same

C Count would decrease by 1

D Count would reset to 0

💡 Hint

Check the 'Check sum-k in map' column at step 6 and consider if sum-k would be in the map for k=4.

Concept Snapshot

Subarray Sum Equals K Using Hash Map:
- Use running sum and hash map to store counts of prefix sums.
- Initialize map with {0:1} to count subarrays starting at index 0.
- For each element, update running sum.
- Check if (sum-k) exists in map; if yes, add its count to result.
- Update map with current sum count.
- Result is total count of subarrays summing to k.

Full Transcript

This concept uses a running sum and a hash map to find how many subarrays sum to a target k. We start with sum zero and map containing zero with count one. For each element, we add it to the running sum. We then check if sum minus k exists in the map. If yes, it means a subarray ending here sums to k, so we add the count from the map to our result. We then update the map with the current sum count. This process continues for all elements. The final count is the total number of subarrays with sum k. The execution table shows each step with current element, running sum, map state, and count updates. Key moments clarify why map starts with zero and why we check sum-k. The visual quiz tests understanding of running sum and count changes at specific steps.