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

↓

Update map with current sum count

↓

Repeat for all elements

↓

Return count

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 C#

int count = 0;
int sum = 0;
Dictionary<int,int> map = new Dictionary<int,int>{{0,1}};
foreach (int num in nums) {
  sum += num;
  if (map.ContainsKey(sum - k)) count += map[sum - k];
  map[sum] = (map.ContainsKey(sum) ? map[sum] : 0) + 1;
}
return count;

This code counts subarrays whose sum equals k by tracking cumulative sums and their frequencies in a map.

Execution Table

Step	Operation	Current Num	Running Sum	Check sum-k in map	Count Updated	Map State	Subarrays Found
1	Initialize	N/A	0	N/A	0	{0:1}	[]
2	Add num	1	1	sum-k=1-3=-2 not in map	0	{0:1,1:1}	[]
3	Add num	2	3	sum-k=3-3=0 in map with count=1	1	{0:1,1:1,3:1}	[[1,2]]
4	Add num	-1	2	sum-k=2-3=-1 not in map	1	{0:1,1:1,3:1,2:1}	[[1,2]]
5	Add num	1	3	sum-k=3-3=0 in map with count=1	2	{0:1,1:1,3:2,2:1}	[[1,2],[1,2,-1,1]]
6	Add num	2	5	sum-k=5-3=2 in map with count=1	3	{0:1,1:1,3:2,2:1,5:1}	[[1,2],[1,2,-1,1],[1,2]]
7	Add num	-2	3	sum-k=3-3=0 in map with count=1	4	{0:1,1:1,3:3,2:1,5:1}	[[1,2],[1,2,-1,1],[1,2],[1,2,-1,1,2,-2]]
8	End	N/A	N/A	N/A	4	{0:1,1:1,3:3,2:1,5:1}	[All subarrays counted]

💡 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	3	3
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:1,3:3,2:1,5:1}	{0:1,1:1,3:3,2:1,5:1}

Key Moments - 3 Insights

Why do we initialize the map with {0:1} at the start?

Because a subarray starting from index 0 can have sum equal to k. The initial sum 0 with count 1 helps detect this in the first iteration (see Step 3 in execution_table).

Why do we check for sum-k in the map instead of just sum?

Checking sum-k helps find if there was a previous prefix sum that, when removed, leaves a subarray summing to k. This is shown in Steps 3, 5, 6, and 7 where sum-k is found in the map.

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

We update after checking to avoid counting the current element's sum before considering subarrays ending at this element. This order ensures correct counting as seen in all steps.

Visual Quiz - 3 Questions

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

A 1

B 2

C 0

D 3

💡 Hint

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

At which step does the running sum first equal 3?

A Step 2

B Step 3

C Step 5

D Step 6

💡 Hint

Look at the 'Running Sum' column in execution_table to find when sum becomes 3.

If the initial map did not contain {0:1}, what would be the count after Step 3?

A 2

B 1

C 0

D 3

💡 Hint

Refer to key_moments about why map starts with {0:1} and check Step 3 in execution_table.

Concept Snapshot

Subarray Sum Equals K Using Hash Map:
- Use running sum and a map to store frequencies of sums.
- Initialize map with {0:1} to handle subarrays from start.
- For each element, add to sum, check if sum-k exists in map.
- Add map[sum-k] to count for subarrays ending here.
- Update map with current sum count.
- Return total count after processing all elements.

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 zero and map containing zero with count one. For each number, 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 at current index sums to k, so we add the frequency to our count. We then update the map with the current sum's frequency. This process continues for all elements. The final count is the total number of subarrays with sum k. The map helps us quickly find how many prefix sums match sum-k, enabling efficient counting.

Practice

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

easy

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

B. To sort the array elements before processing

C. To store the original array elements as keys

D. To reverse the array for easier traversal

Solution

1. Step 1: Understand the problem goal

   The problem wants to find subarrays whose sums equal a target value k.

2. Step 2: Role of hash map in solution

   The hash map stores cumulative sums seen so far and how many times they occurred, enabling quick checks for needed sums.

3. Final Answer:

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

4. Quick Check:

   Hash map stores sums = A [OK]

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

Common Mistakes:

• Thinking hash map stores array elements directly
• Assuming sorting is needed
• Using hash map to reverse array

2. Which of the following is the correct way to declare a hash map (Dictionary) in C# to store cumulative sums and their counts?

easy

A. Dictionary sumCounts = new Dictionary();

B. HashMap sumCounts = new HashMap();

C. Map sumCounts = new Map();

D. Dictionary sumCounts = new Dictionary();

Solution

1. Step 1: Identify correct C# dictionary syntax

   C# uses Dictionary<TKey, TValue> with new Dictionary<TKey, TValue>() to declare hash maps.

2. Step 2: Check each option

   Dictionary sumCounts = new Dictionary(); uses correct generic syntax. Options B and C use Java-like syntax. Dictionary sumCounts = new Dictionary(); misses generic types.

3. Final Answer:

   Dictionary sumCounts = new Dictionary(); -> Option A

4. Quick Check:

   C# Dictionary syntax = A [OK]

Hint: Use Dictionary in C# for hash maps [OK]

Common Mistakes:

• Using Java HashMap syntax in C#
• Omitting generic type parameters
• Using non-existent Map type in C#

3. What is the output of the following C# code snippet?

int[] nums = {1, 2, 3};
int k = 3;
int count = 0;
Dictionary sumCounts = new Dictionary();
sumCounts[0] = 1;
int sum = 0;
foreach (int num in nums) {
    sum += num;
    if (sumCounts.ContainsKey(sum - k)) {
        count += sumCounts[sum - k];
    }
    if (sumCounts.ContainsKey(sum)) {
        sumCounts[sum]++;
    } else {
        sumCounts[sum] = 1;
    }
}
Console.WriteLine(count);

medium

A. 1

B. 0

C. 3

D. 2

Solution

1. Step 1: Calculate cumulative sums and check counts

   nums = [1,2,3], k=3. sumCounts starts with {0:1}. - sum=1: sum-k= -2 (not in sumCounts), count=0, sumCounts={0:1,1:1} - sum=3: sum-k=0 (in sumCounts=1), count=1, sumCounts={0:1,1:1,3:1} - sum=6: sum-k=3 (in sumCounts=1), count=2, sumCounts={0:1,1:1,3:1,6:1}

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 D

4. Quick Check:

   Subarrays count = 2 [OK]

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

Common Mistakes:

• Not initializing sumCounts with {0:1}
• Forgetting to update count correctly
• Misunderstanding sum-k lookup

4. Identify the bug in this C# code snippet for counting subarrays summing to k:

int[] nums = {1, 1, 1};
int k = 2;
int count = 0;
Dictionary sumCounts = new Dictionary();
int sum = 0;
foreach (int num in nums) {
    sum += num;
    if (sumCounts.ContainsKey(sum - k)) {
        count += sumCounts[sum - k];
    }
    sumCounts[sum] = 1;
}
Console.WriteLine(count);

medium

A. nums array is empty

B. sumCounts is not initialized with sum 0 count 1

C. count is not incremented correctly

D. sum variable is not updated inside the loop

Solution

1. Step 1: Check initialization of sumCounts

   sumCounts should start with {0:1} to count subarrays starting at index 0, but here it is empty.

2. Step 2: Check updating sumCounts inside loop

   sumCounts[sum] = 1 overwrites counts instead of incrementing, but main bug is missing initial {0:1}.

3. Final Answer:

   sumCounts is not initialized with sum 0 count 1 -> Option B

4. Quick Check:

   Initialize sumCounts[0] = 1 [OK]

Hint: Always initialize sumCounts with {0:1} before loop [OK]

Common Mistakes:

• Not initializing sumCounts with {0:1}
• Overwriting counts instead of incrementing
• Ignoring sum-k lookup logic

5. Given the array nums = {3, 4, 7, 2, -3, 1, 4, 2} and k = 7, how many subarrays sum to k using the hash map approach?

hard

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Calculate cumulative sums and track counts

   Initialize sumCounts = {0:1}, sum=0, count=0. - i=0: sum=3, sum-k=-4(not found), count=0, sumCounts={0:1,3:1} - i=1: sum=7, sum-k=0(found=1), count=1, sumCounts={0:1,3:1,7:1} - i=2: sum=14, sum-k=7(found=1), count=2, sumCounts={0:1,3:1,7:1,14:1} - i=3: sum=16, sum-k=9(not found), count=2, sumCounts={0:1,3:1,7:1,14:1,16:1} - i=4: sum=13, sum-k=6(not found), count=2, sumCounts={0:1,3:1,7:1,14:1,16:1,13:1} - i=5: sum=14, sum-k=7(found=1), count=3, sumCounts[14]=2 - i=6: sum=18, sum-k=11(not found), count=3, sumCounts={0:1,3:1,7:1,14:2,16:1,13:1,18:1} - i=7: sum=20, sum-k=13(found=1), count=4, sumCounts={0:1,3:1,7:1,14:2,16:1,13:1,18:1,20:1}

2. Step 2: Verify the counted subarrays

   Subarrays summing to 7 are: - [3,4] - [7] - [7,2,-3,1] - [1,4,2] Count is 4 total.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Count subarrays with sum k = 4 [OK]

Hint: Track sums and counts carefully to find all subarrays [OK]

Common Mistakes:

• Missing subarrays with negative numbers
• Not updating counts when sum repeats
• Forgetting to initialize sumCounts with {0:1}