Subarray Sum Equals K Using Hash Map in DSA Go

Mental Model

We keep track of sums of elements from the start to each position and use a map to find if a subarray sums to k quickly.

Analogy: Imagine walking along a path and noting your total steps at each point. If you want to find a segment where you walked exactly k steps, you check if the difference between your current steps and some earlier steps equals k.

Array: [1, 2, 3, 4, 5]
Prefix sums: [0, 1, 3, 6, 10, 15]
HashMap stores sums seen so far with their counts.
Example: sum 3 seen at index 2 -> map[3] = 1

Dry Run Walkthrough

Input: array: [1, 2, 3], k = 3

Goal: Find how many continuous subarrays sum to 3

Step 1: Initialize sum = 0, map = {0:1} to count empty prefix

sum=0, map={0:1}

Why: Start with sum zero counted once to handle subarrays starting at index 0

Step 2: Add first element 1 to sum -> sum=1; check if sum-k=1-3=-2 in map (no)

sum=1, map={0:1, 1:1}

Why: No subarray ending here sums to k, record sum 1

Step 3: Add second element 2 -> sum=3; check sum-k=3-3=0 in map (yes, count=1)

sum=3, map={0:1, 1:1, 3:1}, count=1

Why: Found subarray [1,2] sums to k because prefix sum 0 was seen before

Step 4: Add third element 3 -> sum=6; check sum-k=6-3=3 in map (yes, count=1)

sum=6, map={0:1, 1:1, 3:1, 6:1}, count=2

Why: Found subarray [3] sums to k because prefix sum 3 was seen before

Result:

Final count = 2
Subarrays: [1,2], [3]

Annotated Code

DSA Go

package main

import "fmt"

func subarraySum(nums []int, k int) int {
    count := 0
    sum := 0
    prefixSums := map[int]int{0: 1} // sum 0 seen once

    for _, num := range nums {
        sum += num // add current number to running sum
        if c, found := prefixSums[sum-k]; found {
            count += c // add count of prefix sums that match sum-k
        }
        prefixSums[sum]++ // record current sum count
    }

    return count
}

func main() {
    nums := []int{1, 2, 3}
    k := 3
    result := subarraySum(nums, k)
    fmt.Println(result)
}

sum += num // add current number to running sum

update running sum with current element

if c, found := prefixSums[sum-k]; found { count += c }

check if a prefix sum exists that would form subarray sum k

prefixSums[sum]++

record current prefix sum count for future matches

Output

2

Complexity Analysis

Time: O(n) because we traverse the array once and do constant time map operations per element

Space: O(n) because in worst case all prefix sums are unique and stored in the map

vs Alternative: Naive approach is O(n^2) by checking all subarrays; this method uses prefix sums and a map to reduce to O(n)

Edge Cases

empty array

returns 0 since no subarrays exist

DSA Go

prefixSums := map[int]int{0: 1} // sum 0 seen once

array with all zeros and k=0

counts all subarrays of zeros correctly

DSA Go

count += c // add count of prefix sums that match sum-k

no subarray sums to k

returns 0 as count

DSA Go

if c, found := prefixSums[sum-k]; found { count += c }

When to Use This Pattern

When asked to find the count of continuous subarrays summing to a target, use prefix sums with a hash map to track sums seen so far for O(n) solution.

Common Mistakes

Mistake: Not initializing the map with sum 0 count as 1
Fix: Initialize map with {0:1} to handle subarrays starting at index 0

Mistake: Checking for sum in map before updating count
Fix: Always check for sum-k in map before adding current sum to map

Summary

Counts how many continuous subarrays sum to a given value k.

Use when you need efficient counting of subarrays with a specific sum.

Keep track of prefix sums and use a map to find matching sums quickly.

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