Subarray Sum Equals K Using Hash Map in DSA Go - Build from Scratch

Subarray Sum Equals K Using Hash Map

📖 Scenario: You are analyzing daily sales data for a small shop. You want to find how many continuous days had sales that add up exactly to a target number k. This helps the shop owner understand sales patterns.

🎯 Goal: Build a Go program that counts the number of continuous subarrays whose sum equals k using a hash map for efficient lookup.

📋 What You'll Learn

Create a slice called sales with the exact values: 1, 2, 3, 4, 2

Create an integer variable called k and set it to 5

Use a hash map (map[int]int) called prefixSums to store prefix sums and their counts

Implement a loop to calculate prefix sums and count subarrays summing to k

Print the final count of subarrays that sum to k

💡 Why This Matters

🌍 Real World

Finding continuous periods where sales meet a target helps businesses analyze trends and plan promotions.

💼 Career

This technique is useful in software engineering roles involving data analysis, algorithm design, and performance optimization.

1

Create the sales data slice

Create a slice called sales with the exact values 1, 2, 3, 4, 2.

DSA Go

# Create the sales slice with values 1, 2, 3, 4, 2
// Your code here

Hint

Use sales := []int{1, 2, 3, 4, 2} to create the slice.

2

Set the target sum variable

Create an integer variable called k and set it to 5.

DSA Go

package main

func main() {
    sales := []int{1, 2, 3, 4, 2}
    // Create variable k and set it to 5
    // Your code here
}

Hint

Use k := 5 to create the target sum variable.

3

Implement the subarray sum counting logic

Create a map called prefixSums of type map[int]int and initialize it with 0:1. Then create variables count and currentSum set to 0. Use a for loop with variable num to iterate over sales. Inside the loop, add num to currentSum. Check if currentSum - k exists in prefixSums and if yes, add its value to count. Then increment the count of currentSum in prefixSums by 1.

DSA Go

package main

func main() {
    sales := []int{1, 2, 3, 4, 2}
    k := 5
    // Create prefixSums map with 0:1
    // Create count and currentSum variables set to 0
    // Use for loop with num to iterate sales
    // Update currentSum, check prefixSums for currentSum-k, update count
    // Update prefixSums for currentSum
    // Your code here
}

Hint

Use a map to store prefix sums and their counts. Update count when currentSum - k is found.

4

Print the count of subarrays summing to k

Use fmt.Println(count) to print the number of continuous subarrays in sales whose sum equals k. Remember to import the fmt package.

DSA Go

package main

import "fmt"

func main() {
    sales := []int{1, 2, 3, 4, 2}
    k := 5

    prefixSums := map[int]int{0: 1}
    count := 0
    currentSum := 0

    for _, num := range sales {
        currentSum += num
        if val, found := prefixSums[currentSum-k]; found {
            count += val
        }
        prefixSums[currentSum]++
    }

    // Print the count
    // Your code here
}

Hint

Use fmt.Println(count) to display the result.

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