Subarray Sum Equals K Using Hash Map in DSA C++

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 counting steps. If you know how many steps you took at two points, subtracting them tells you how many steps you took between those points.

Array: [1] -> [2] -> [3] -> [4] -> [5]
Prefix sums: 0 -> 1 -> 3 -> 6 -> 10 -> 15
HashMap stores sums seen so far with their counts.

Dry Run Walkthrough

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

Goal: Find how many continuous subarrays sum to 3

Step 1: Start with prefix_sum = 0 and map = {0:1} to count empty sum

prefix_sum=0, map={0:1}

Why: We count the empty prefix to handle subarrays starting at index 0

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

prefix_sum=1, map={0:1, 1:1}, count=0

Why: No subarray ending here sums to k yet; store prefix_sum

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

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

Why: Found subarray [1,2] summing to 3

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

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

Why: Found subarray [3] summing to 3

Result:

Final count=2; subarrays are [1,2] and [3]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> prefixSumCount;
        prefixSumCount[0] = 1; // empty prefix sum
        int prefix_sum = 0;
        int count = 0;
        for (int num : nums) {
            prefix_sum += num; // add current number to prefix sum
            if (prefixSumCount.find(prefix_sum - k) != prefixSumCount.end()) {
                count += prefixSumCount[prefix_sum - k]; // add count of prefix sums that match
            }
            prefixSumCount[prefix_sum]++; // record current prefix sum
        }
        return count;
    }
};

int main() {
    vector<int> nums = {1, 2, 3};
    int k = 3;
    Solution sol;
    cout << sol.subarraySum(nums, k) << "\n";
    return 0;
}

prefixSumCount[0] = 1; // empty prefix sum

Initialize map with zero sum count to handle subarrays starting at index 0

prefix_sum += num; // add current number to prefix sum

Update running sum including current element

if (prefixSumCount.find(prefix_sum - k) != prefixSumCount.end()) {

Check if there is a prefix sum that when removed leaves sum k

count += prefixSumCount[prefix_sum - k]; // add count of prefix sums that match

Add number of subarrays ending here with sum k

prefixSumCount[prefix_sum]++; // record current prefix sum

Record current prefix sum count for future subarrays

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 hashing to reduce to O(n)

Edge Cases

empty array

returns 0 since no subarrays exist

DSA C++

prefixSumCount[0] = 1;

array with all zeros and k=0

counts all subarrays of zeros correctly using prefix sums

DSA C++

count += prefixSumCount[prefix_sum - k];

no subarray sums to k

returns 0 as count

DSA C++

if (prefixSumCount.find(prefix_sum - k) != prefixSumCount.end())

When to Use This Pattern

When asked to find 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 prefixSumCount[0] = 1, missing subarrays starting at index 0
Fix: Always initialize map with zero sum count 1 before loop

Mistake: Updating prefixSumCount before checking for prefix_sum - k in map
Fix: Check for prefix_sum - k first, then update map

Summary

Counts how many continuous subarrays sum to a given value k using prefix sums and a hash map.

Use when you need to find subarrays with a specific sum efficiently in O(n) time.

The key insight is that the difference between two prefix sums equals the sum of the subarray between them.

Practice

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

easy

A. To keep track of the maximum subarray length

B. To sort the array elements before processing

C. To store the original array elements as keys

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

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

   The hash map stores cumulative sums and their counts to quickly check 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 D

4. Quick Check:

   Hash map stores sums = D [OK]

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

Common Mistakes:

• Using hash map to sort elements
• Storing array elements as keys instead of sums
• Trying to track max length instead of counts

2. Which of the following is the correct C++ syntax to declare a hash map for storing int keys and values?

easy

A. std::unordered_map map;

B. std::map<int> map;

C. unordered_map map;

D. std::hash_map map;

Solution

1. Step 1: Identify correct hash map declaration

   In C++, std::unordered_map<Key, Value> is used for hash maps.

2. Step 2: Check syntax correctness

   std::unordered_map map; uses correct template syntax and namespace. Others have syntax errors or wrong types.

3. Final Answer:

   std::unordered_map map; -> Option A

4. Quick Check:

   Correct unordered_map syntax = A [OK]

Hint: Use std::unordered_map for hash maps [OK]

Common Mistakes:

• Missing template brackets <>
• Using std::map instead of unordered_map for hash map
• Wrong order of template parameters

3. What will be the output of the following C++ code snippet?

std::vector<int> nums = {1, 2, 3};
int k = 3;
int count = 0;
std::unordered_map prefixSumCount;
prefixSumCount[0] = 1;
int sum = 0;
for (int num : nums) {
    sum += num;
    if (prefixSumCount.find(sum - k) != prefixSumCount.end()) {
        count += prefixSumCount[sum - k];
    }
    prefixSumCount[sum]++;
}
std::cout << count << std::endl;

medium

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Calculate prefix sums and counts

   Prefix sums: 1, 3, 6. Check if (sum - k) exists in map: - sum=1: 1-3=-2 not found - sum=3: 3-3=0 found, count=1 - sum=6: 6-3=3 found, count=1+1=2

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 A

4. Quick Check:

   Subarrays summing to 3 = 2 [OK]

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

Common Mistakes:

• Not initializing prefixSumCount[0] = 1
• Incorrectly updating count
• Confusing sum and sum-k keys

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

int subarraySum(std::vector<int>& nums, int k) {
    std::unordered_map map;
    int count = 0, sum = 0;
    for (int num : nums) {
        sum += num;
        if (map.find(sum - k) != map.end()) {
            count += map[sum - k];
        }
        map[sum] = 1;
    }
    return count;
}

medium

A. count should be incremented by 1 only

B. sum should be reset to 0 inside the loop

C. map[sum] should be incremented, not set to 1

D. map should be a vector instead of unordered_map

Solution

1. Step 1: Analyze map update logic

   Setting map[sum] = 1 overwrites previous counts, losing frequency data.

2. Step 2: Correct way to update map

   We must increment map[sum] to count all occurrences of the prefix sum.

3. Final Answer:

   map[sum] should be incremented, not set to 1 -> Option C

4. Quick Check:

   Increment map[sum] to track frequencies [OK]

Hint: Increment map[sum] to count frequencies, not overwrite [OK]

Common Mistakes:

• Overwriting map[sum] instead of incrementing
• Resetting sum inside loop incorrectly
• Using wrong data structure for map

5. Given an array nums = {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. 3

B. 5

C. 4

D. 6

Solution

1. Step 1: Calculate prefix sums and track counts

   Prefix sums: 3,7,14,16,13,14,18,20.
   Map checks (sum-k found):
   - sum=7: 0 (+1) -> count=1
   - sum=14: 7 (+1) -> count=2
   - sum=14 (2nd): 7 (+1) -> count=3
   - sum=20: 13 (+1) -> count=4
   - sum=18: 11 (+1) -> count=5 (Note: 11 is sum-k for k=7 at sum=18, check if 11 exists in map)

2. Step 2: Final count of subarrays

   Total 5 subarrays: [3,4], [7], [7,2,-3,1], [1,4,2], and [4,7,2,-3,-3].

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Count of subarrays with sum 7 = 5 [OK]

Hint: Track prefix sums and count matches for sum-k [OK]

Common Mistakes:

• Not incrementing count for multiple occurrences
• Missing negative numbers effect on sums
• Incorrect prefix sum updates