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.

Practice

1. What is the main purpose of using a hash map in the Subarray Sum Equals K problem?

easy

A. To store the original array elements as keys

B. To sort the array elements before processing

C. To keep track of the maximum subarray length

D. To store cumulative sums and their frequencies for quick lookup

Solution

1. Step 1: Understand the problem requirement

   The problem requires finding subarrays whose sums equal a target value k.

2. Step 2: Role of hash map in the solution

   The hash map stores cumulative sums seen so far and their counts to quickly check if a subarray sum equals k exists.

3. Final Answer:

   To store cumulative sums and their frequencies for quick lookup -> Option D

4. Quick Check:

   Hash map stores sums for fast subarray sum checks [OK]

Hint: Hash map tracks sums to find subarrays fast [OK]

Common Mistakes:

• Thinking hash map sorts elements
• Using hash map to store array elements directly
• Confusing hash map with array for indexing

2. Which of the following is the correct way to initialize a hash map in C for storing integer keys and values?

easy

A. map map;

B. HashMap map = new HashMap<>();

C. int map[1000] = {0};

D. unordered_map map;

Solution

1. Step 1: Identify C language syntax

   In C, hash maps are not built-in; arrays can be used as simple maps for small ranges.

2. Step 2: Check options for C syntax

   int map[1000] = {0}; uses an integer array initialized to zero, suitable as a simple map in C.

3. Final Answer:

   int map[1000] = {0}; -> Option C

4. Quick Check:

   Array initialization is valid C syntax [OK]

Hint: Use arrays for maps in C, no built-in hash map [OK]

Common Mistakes:

• Using C++ or Java syntax in C code
• Trying to declare hash maps directly in C
• Not initializing arrays before use

3. What will be the output of the following code snippet in C that counts subarrays summing to k=5?

int arr[] = {1, 2, 3, 2, 1};
int k = 5;
// Assume correct hash map logic implemented
int result = subarraySum(arr, 5, k);
printf("%d", result);

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Identify subarrays summing to 5

   Subarrays: [2,3] (indices 1-2), [3,2] (indices 2-3), [2,3] (indices 3-4); total 3 subarrays.

2. Step 2: Count valid subarrays

   Counting carefully, the subarrays summing to 5 are three in total.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count of subarrays with sum 5 = 3 [OK]

Hint: Count all subarrays with sum k using prefix sums [OK]

Common Mistakes:

• Counting only non-overlapping subarrays
• Missing subarrays starting at index 0
• Incorrectly summing elements

4. Identify the bug in this C code snippet for counting subarrays with sum k using a hash map:

int subarraySum(int* nums, int numsSize, int k) {
    int count = 0, sum = 0;
    int map[10000] = {0};
    map[0] = 1;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
        if (map[sum - k])
            count += map[sum - k];
        map[sum]++;
    }
    return count;
}

medium

A. Array map size is too small for negative sums

B. Missing initialization of count variable

C. Incorrect loop range causing out-of-bounds access

D. Using map as pointer without allocation

Solution

1. Step 1: Analyze map usage for sums

   The map array uses indices as sums, but sums can be negative, causing invalid indexing.

2. Step 2: Identify impact of negative sums

   Negative sums cause out-of-bound access or wrong counts since array indices can't be negative.

3. Final Answer:

   Array map size is too small for negative sums -> Option A

4. Quick Check:

   Negative sums need offset or different data structure [OK]

Hint: Handle negative sums with offset or hash map [OK]

Common Mistakes:

• Ignoring negative sums in indexing
• Assuming sums are always positive
• Not initializing map for sum 0

5. Given an array arr = {3, 4, 7, 2, -3, 1, 4, 2} and k = 7, how many subarrays sum to k? Use the hash map approach to find the answer.

hard

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Calculate prefix sums and track counts

   Prefix sums: 3,7,14,16,13,14,18,20. Check sums - k in map to count subarrays.

2. Step 2: Count subarrays with sum k=7

   Subarrays: [3,4], [7], [7,2,-3,1], [1,4,2], [4,2, -3,1,4] total 5 subarrays.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Count subarrays summing to 7 = 5 [OK]

Hint: Use prefix sums and hash map to count subarrays fast [OK]

Common Mistakes:

• Missing subarrays with negative numbers
• Counting overlapping subarrays incorrectly
• Not updating hash map counts properly