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

↓

Add map[sum-k

↓

Update map with current sum count

↓

Repeat for next element

↓

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 was seen before to find subarrays summing to k.

Execution Sample

DSA Go

nums := []int{1, 2, 3}
k := 3
count := 0
sum := 0
m := map[int]int{0:1}
for _, num := range nums {
  sum += num
  if val, ok := m[sum-k]; ok {
    count += val
  }
  m[sum]++
}

This code counts subarrays in nums that sum to k using a running sum and a map to track sums.

Execution Table

Step	Operation	Current Element	Running Sum	Check sum-k in map	Map State	Count	Visual State
0	Initialize	N/A	0	sum-k=0-3=-3 not in map	{0:1}	0	[]
1	Add element	1	1	sum-k=1-3=-2 not in map	{0:1,1:1}	0	[1]
2	Add element	2	3	sum-k=3-3=0 in map with count=1	{0:1,1:1,3:1}	1	[1,2]
3	Add element	3	6	sum-k=6-3=3 in map with count=1	{0:1,1:1,3:1,6:1}	2	[1,2,3]
4	End	N/A	6	No further elements	{0:1,1:1,3:1,6:1}	2	[1,2,3]

💡 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 is detected by sum-k=0 existing in the map. This is shown in step 2 where sum=3 and sum-k=0 is found in the map, increasing count.

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. For example, at step 3 sum=6, sum-k=3 is in the map, meaning subarray after that prefix sums to k.

Why do we increment the count by map[sum-k] instead of just 1?

Because multiple previous prefix sums could have the same value sum-k, each representing a different subarray ending at current index that sums to k. The map stores counts of prefix sums, so we add all occurrences.

Visual Quiz - 3 Questions

Look at the execution table at step 2. What is the value of count after processing element 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 1

B Step 2

C Step 3

D Step 4

💡 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 0

B 1

C 2

D 3

💡 Hint

Refer to the key moment about why map starts with {0:1} and how it affects count increments.

Concept Snapshot

Subarray Sum Equals K Using Hash Map:
- Use running sum to track cumulative sums.
- Use map to store counts of prefix sums.
- For each element, check if (sum-k) exists in map.
- Add map[sum-k] to count to find subarrays ending here.
- Initialize map with {0:1} to handle subarrays from start.

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 sum count as one. For each element, we add it to the running sum. Then we 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 count of that prefix sum to our total count. 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 summing to k.

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 store cumulative sums and their frequencies for quick lookup

D. To keep track of the maximum subarray length

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

   A hash map stores cumulative sums seen so far and their counts, enabling quick checks 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 C

4. Quick Check:

   Hash map = cumulative sums storage [OK]

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

Common Mistakes:

• Thinking hash map stores array elements as keys
• Assuming sorting is needed
• Confusing hash map with array for sums

2. Which of the following Go code snippets correctly initializes a hash map to store integer keys and values for the subarray sum problem?

easy

A. m := make([]int, 0)

B. m := make(map[int]int)

C. m := map[int]string{}

D. m := map[string]int{}

Solution

1. Step 1: Identify correct map type for keys and values

   We need a map with integer keys and integer values to store sums and counts.

2. Step 2: Check Go syntax for map initialization

   make(map[int]int) correctly creates a map with int keys and int values.

3. Final Answer:

   m := make(map[int]int) -> Option B

4. Quick Check:

   map[int]int = correct map type [OK]

Hint: Use make(map[int]int) for int keys and values [OK]

Common Mistakes:

• Using slice instead of map
• Wrong key or value types in map
• Using map with string keys incorrectly

3. What is the output of the following Go code snippet?

nums := []int{1, 2, 3}
k := 3
count := 0
sum := 0
m := make(map[int]int)
m[0] = 1
for _, v := range nums {
    sum += v
    if val, ok := m[sum-k]; ok {
        count += val
    }
    m[sum]++
}
fmt.Println(count)

medium

A. 1

B. 0

C. 3

D. 2

Solution

1. Step 1: Trace cumulative sums and map updates

   Iteration 1: sum=1, m[1]=1, sum-k=-2 not in map, count=0 Iteration 2: sum=3, sum-k=0 in map with count 1, count=1, m[3]=1 Iteration 3: sum=6, sum-k=3 in map with count 1, count=2, m[6]=1

2. Step 2: Final count after loop

   Count is 2 because two subarrays sum to k=3: [1,2] and [3].

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Subarrays summing to 3 = 2 [OK]

Hint: Count increments when (sum-k) found in map [OK]

Common Mistakes:

• Not initializing m[0] = 1
• Forgetting to increment map count
• Miscounting subarrays

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

nums := []int{1, 1, 1}
k := 2
count := 0
sum := 0
m := make(map[int]int)
for _, v := range nums {
    sum += v
    if val, ok := m[sum-k]; ok {
        count += val
    }
    m[sum]++
}
fmt.Println(count)

medium

A. Missing initialization m[0] = 1 before loop

B. Incorrect increment of count variable

C. Wrong loop variable used

D. Using map with wrong key type

Solution

1. Step 1: Check map initialization

   The map m is used to store cumulative sums, but m[0] is not initialized to 1 before the loop.

2. Step 2: Effect of missing m[0] = 1

   Without m[0] = 1, subarrays starting from index 0 that sum to k are not counted, causing incorrect count.

3. Final Answer:

   Missing initialization m[0] = 1 before loop -> Option A

4. Quick Check:

   Initialize m[0]=1 to count subarrays from start [OK]

Hint: Always set m[0] = 1 before loop [OK]

Common Mistakes:

• Not initializing m[0]
• Incrementing count incorrectly
• Using wrong map key type

5. Given the array nums = []int{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. 4

B. 3

C. 6

D. 5

Solution

1. Step 1: Calculate cumulative sums and track counts

   Initialize m[0]=1, sum=0, count=0 Iterate nums: - sum=3, sum-k=-4 not in m, m[3]=1 - sum=7, sum-k=0 in m=1, count=1, m[7]=1 - sum=14, sum-k=7 in m=1, count=2, m[14]=1 - sum=16, sum-k=9 not in m, m[16]=1 - sum=13, sum-k=6 not in m, m[13]=1 - sum=14, sum-k=7 in m=1, count=3, m[14]=2 - sum=18, sum-k=11 not in m, m[18]=1 - sum=20, sum-k=13 in m=1, count=4, m[20]=1

2. Step 2: Verify subarrays

   The subarrays summing to 7 are: [3,4], [7], [7,2,-3,1], [1,4,2]. Total count = 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Count subarrays with sum k = 4 [OK]

Hint: Track cumulative sums and counts carefully [OK]

Common Mistakes:

• Missing m[0] initialization
• Miscounting overlapping subarrays
• Not updating map counts correctly