Subarray Sum Equals K Using Hash Map in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of subarray sum count with k=5

What is the output of the following Go code that counts subarrays summing to k=5?

DSA Go

package main
import "fmt"
func subarraySum(nums []int, k int) int {
    count := 0
    sum := 0
    prefixSums := map[int]int{0: 1}
    for _, num := range nums {
        sum += num
        if v, ok := prefixSums[sum-k]; ok {
            count += v
        }
        prefixSums[sum]++
    }
    return count
}
func main() {
    nums := []int{1, 2, 3, 2, 1}
    k := 5
    fmt.Println(subarraySum(nums, k))
}

A 3

B 2

C 1

D 4

💡 Hint

Think about all continuous subarrays that sum exactly to 5.

The subarrays that sum to 5 are [2,3] (indices 1-2) and [3,2] (indices 2-3). The code correctly counts 2 such subarrays.

🧠 Conceptual

intermediate

Why use a hash map in subarray sum problem?

Why is a hash map used in the subarray sum equals k problem?

A To keep track of the maximum subarray sum found so far

B To sort the array elements for faster sum calculation

C To store all subarrays explicitly for checking sums

D To store counts of prefix sums for quick lookup of needed sums

💡 Hint

Think about how to find if a previous sum exists that helps form k.

The hash map stores how many times each prefix sum has appeared. This allows quick checks if sum-k exists, indicating a subarray summing to k.

🔧 Debug

advanced

Identify the error in subarray sum code snippet

What error will this Go code produce when counting subarrays summing to k=3?

DSA Go

package main
import "fmt"
func subarraySum(nums []int, k int) int {
    count := 0
    sum := 0
    prefixSums := map[int]int{}
    for _, num := range nums {
        sum += num
        if v, ok := prefixSums[sum-k]; ok {
            count += v
        }
        prefixSums[sum]++
    }
    return count
}
func main() {
    nums := []int{1, 2, 1, 2, 1}
    k := 3
    fmt.Println(subarraySum(nums, k))
}

A runtime error: assignment to entry in nil map

B 0

C 3

D 1

💡 Hint

Check how prefixSums map is initialized.

The map prefixSums is initialized empty without the base case 0:1, so subarrays starting at index 0 are not counted. For nums=[1,2,1,2,1], k=3, there are 4 subarrays summing to 3, but the code returns 3.

❓ Predict Output

advanced

Output of subarray sum count with negative numbers

What is the output of this Go code counting subarrays summing to k=0 with negative numbers?

DSA Go

package main
import "fmt"
func subarraySum(nums []int, k int) int {
    count := 0
    sum := 0
    prefixSums := map[int]int{0: 1}
    for _, num := range nums {
        sum += num
        if v, ok := prefixSums[sum-k]; ok {
            count += v
        }
        prefixSums[sum]++
    }
    return count
}
func main() {
    nums := []int{1, -1, 0, 0}
    k := 0
    fmt.Println(subarraySum(nums, k))
}

A 6

B 4

C 5

D 3

💡 Hint

Consider subarrays including zeros and negative numbers.

The subarrays summing to 0 are [1,-1], [1,-1,0], [1,-1,0,0], [0] (index 2), [0] (index 3), [0,0] (indices 2-3). There are 6 such subarrays.

🚀 Application

expert

Number of subarrays summing to k in large input

Given an array of 100000 elements all equal to 1, and k=2, how many subarrays sum to k?

A 99999

B 99998

C 100000

D 99997

💡 Hint

Count how many continuous pairs sum to 2 in a large array of ones.

Each pair of consecutive 1s sums to 2. There are n-1 such pairs in an array of length n=100000.

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