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 and map={0:1}

↓

Iterate over array elements

↓

Add current element to sum

↓

Check if (sum-k) exists in map?

Yes→Add map[sum-k

↓

Update count

↓

Add/update sum in map

↓

Repeat for next element

↓

End: return count

We keep a running sum and use a map to find how many previous sums allow a subarray summing to k.

Execution Sample

DSA C++

int subarraySum(vector<int>& nums, int k) {
  unordered_map<int,int> map{{0,1}};
  int sum=0, count=0;
  for(int n : nums) {
    sum += n;
    if(map.count(sum-k)) count += map[sum-k];
    map[sum]++;
  }
  return count;
}

This code counts subarrays summing to k by tracking prefix sums and their frequencies.

Execution Table

Step	Operation	Current Element	Running Sum (sum)	Check sum-k in map	Map State	Count	Visual State
1	Initialize	N/A	0	sum-k=0-3=-3 not in map	{0:1}	0	Map={0:1}, count=0
2	Add element	1	1	1-3=-2 not in map	{0:1,1:1}	0	sum=1, map updated with 1
3	Add element	2	3	3-3=0 in map with count=1	{0:1,1:1,3:1}	1	sum=3, count=1, map updated with 3
4	Add element	3	6	6-3=3 in map with count=1	{0:1,1:1,3:1,6:1}	2	sum=6, count=2, map updated with 6
5	Add element	4	10	10-3=7 not in map	{0:1,1:1,3:1,6:1,10:1}	2	sum=10, map updated with 10
6	Add element	5	15	15-3=12 not in map	{0:1,1:1,3:1,6:1,10:1,15:1}	2	sum=15, map updated with 15
7	End	N/A	15	No more elements	{0:1,1:1,3:1,6:1,10:1,15:1}	2	Final count=2

💡 All elements processed, final count of subarrays summing to k=3 is 2

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
sum	0	1	3	6	10	15	15
count	0	0	1	2	2	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,10:1}	{0:1,1:1,3:1,6:1,10:1,15:1}	{0:1,1:1,3:1,6:1,10:1,15:1}

Key Moments - 3 Insights

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

Because a subarray starting from index 0 can sum to k. The map entry {0:1} means sum 0 has occurred once, allowing detection of subarrays starting at the beginning (see Step 1 in execution_table).

Why do we check if (sum-k) exists in the map?

Because if (sum-k) was seen before, the subarray between that previous sum and current sum equals k. This is shown in Steps 3 and 4 where sum-k is found in the map and count increases.

Why do we increment map[sum] after checking?

We increment after checking to count the current sum occurrence for future subarrays. This ensures we don't count the current sum before processing it, as seen in all steps updating map.

Visual Quiz - 3 Questions

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

A 2

B 0

C 1

D 3

💡 Hint

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

At which step does the running sum first equal 6?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the 'Running Sum (sum)' column in the execution_table.

If the target k was changed to 6, what would happen to the count at Step 4?

A Count would increase by 1

B Count would stay the same

C Count would decrease

D Count would reset to 0

💡 Hint

Consider the check 'sum-k' in map at Step 4 and how it affects count.

Concept Snapshot

Subarray Sum Equals K Using Hash Map:
- Use a running sum to track prefix sums.
- Store counts of prefix sums in a map (sum -> frequency).
- For each element, check if (sum-k) exists in map to find subarrays summing to k.
- Initialize map with {0:1} to handle subarrays starting at index 0.
- Time complexity: O(n), Space complexity: O(n).

Full Transcript

This concept uses a running sum and a hash map to count how many subarrays sum to a target k. We start with sum=0 and map containing {0:1} to handle subarrays from the start. For each element, we add it to sum, then check if (sum-k) exists in the map. If yes, we add the frequency of (sum-k) to our count because it means a subarray summing to k ends here. Then we update the map with the current sum. This process continues for all elements. The final count is the total number of subarrays summing to k. The execution table shows step-by-step how sum, map, and count change. Key moments clarify why map starts with {0:1}, why we check (sum-k), and why map updates happen after counting. The visual quiz tests understanding of these steps.

Practice

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

easy

A. To keep track of the maximum subarray length

B. To sort the array elements before processing

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 subarrays whose sums equal a target value k.

2. Step 2: Role of hash map in solution

   The hash map stores cumulative sums and their counts to quickly check if a previous sum exists that forms 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 = D [OK]

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

Common Mistakes:

• Using hash map to sort elements
• Storing array elements as keys instead of sums
• Trying to track max length instead of counts

2. Which of the following is the correct C++ syntax to declare a hash map for storing int keys and values?

easy

A. std::unordered_map map;

B. std::map<int> map;

C. unordered_map map;

D. std::hash_map map;

Solution

1. Step 1: Identify correct hash map declaration

   In C++, std::unordered_map<Key, Value> is used for hash maps.

2. Step 2: Check syntax correctness

   std::unordered_map map; uses correct template syntax and namespace. Others have syntax errors or wrong types.

3. Final Answer:

   std::unordered_map map; -> Option A

4. Quick Check:

   Correct unordered_map syntax = A [OK]

Hint: Use std::unordered_map for hash maps [OK]

Common Mistakes:

• Missing template brackets <>
• Using std::map instead of unordered_map for hash map
• Wrong order of template parameters

3. What will be the output of the following C++ code snippet?

std::vector<int> nums = {1, 2, 3};
int k = 3;
int count = 0;
std::unordered_map prefixSumCount;
prefixSumCount[0] = 1;
int sum = 0;
for (int num : nums) {
    sum += num;
    if (prefixSumCount.find(sum - k) != prefixSumCount.end()) {
        count += prefixSumCount[sum - k];
    }
    prefixSumCount[sum]++;
}
std::cout << count << std::endl;

medium

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Calculate prefix sums and counts

   Prefix sums: 1, 3, 6. Check if (sum - k) exists in map: - sum=1: 1-3=-2 not found - sum=3: 3-3=0 found, count=1 - sum=6: 6-3=3 found, count=1+1=2

2. Step 2: Final count of subarrays with sum k

   Count is 2 because subarrays [1,2] and [3] sum to 3.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Subarrays summing to 3 = 2 [OK]

Hint: Track prefix sums and check sum-k in map [OK]

Common Mistakes:

• Not initializing prefixSumCount[0] = 1
• Incorrectly updating count
• Confusing sum and sum-k keys

4. Identify the bug in the following code snippet for counting subarrays summing to k:

int subarraySum(std::vector<int>& nums, int k) {
    std::unordered_map map;
    int count = 0, sum = 0;
    for (int num : nums) {
        sum += num;
        if (map.find(sum - k) != map.end()) {
            count += map[sum - k];
        }
        map[sum] = 1;
    }
    return count;
}

medium

A. count should be incremented by 1 only

B. sum should be reset to 0 inside the loop

C. map[sum] should be incremented, not set to 1

D. map should be a vector instead of unordered_map

Solution

1. Step 1: Analyze map update logic

   Setting map[sum] = 1 overwrites previous counts, losing frequency data.

2. Step 2: Correct way to update map

   We must increment map[sum] to count all occurrences of the prefix sum.

3. Final Answer:

   map[sum] should be incremented, not set to 1 -> Option C

4. Quick Check:

   Increment map[sum] to track frequencies [OK]

Hint: Increment map[sum] to count frequencies, not overwrite [OK]

Common Mistakes:

• Overwriting map[sum] instead of incrementing
• Resetting sum inside loop incorrectly
• Using wrong data structure for map

5. Given an array nums = {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 count.

hard

A. 3

B. 5

C. 4

D. 6

Solution

1. Step 1: Calculate prefix sums and track counts

   Prefix sums: 3,7,14,16,13,14,18,20.
   Map checks (sum-k found):
   - sum=7: 0 (+1) -> count=1
   - sum=14: 7 (+1) -> count=2
   - sum=14 (2nd): 7 (+1) -> count=3
   - sum=20: 13 (+1) -> count=4
   - sum=18: 11 (+1) -> count=5 (Note: 11 is sum-k for k=7 at sum=18, check if 11 exists in map)

2. Step 2: Final count of subarrays

   Total 5 subarrays: [3,4], [7], [7,2,-3,1], [1,4,2], and [4,7,2,-3,-3].

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Count of subarrays with sum 7 = 5 [OK]

Hint: Track prefix sums and count matches for sum-k [OK]

Common Mistakes:

• Not incrementing count for multiple occurrences
• Missing negative numbers effect on sums
• Incorrect prefix sum updates