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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Subarray Sum Count

What is the output of the following C++ code that counts subarrays summing to k using a hash map?

DSA C++

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

int main() {
    vector<int> nums = {1, 2, 3};
    int k = 3;
    cout << subarraySum(nums, k) << endl;
    return 0;
}

A 0

B 1

C 3

D 2

💡 Hint

Think about all continuous subarrays that sum to 3.

The subarrays [1, 2] and [3] both sum to 3, so the count is 2.

❓ Predict Output

intermediate

Result of Subarray Sum with Negative Numbers

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

DSA C++

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

int main() {
    vector<int> nums = {1, -1, 0};
    int k = 0;
    cout << subarraySum(nums, k) << endl;
    return 0;
}

A 3

B 2

C 1

D 0

💡 Hint

Count all subarrays that sum exactly to zero.

Subarrays [1, -1], [-1, 0], and [0] sum to 0, total 3.

🔧 Debug

advanced

Identify the Error in Subarray Sum Code

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

DSA C++

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

int main() {
    vector<int> nums = {1, 2, 3};
    int k = 3;
    cout << subarraySum(nums, k) << endl;
    return 0;
}

A Wrong output due to uninitialized map entry

B Returns 0 always

C Correct output 2

D Compilation error due to missing include

💡 Hint

Check if prefixSumCount[0] is initialized before loop.

The map prefixSumCount does not have prefixSumCount[0] initialized to 1, so the code misses counting subarrays starting at index 0, causing wrong count.

❓ Predict Output

advanced

Output of Subarray Sum with Large Input

What is the output of this code counting subarrays summing to k for a large input array?

DSA C++

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

int main() {
    vector<int> nums(1000, 1);
    int k = 2;
    cout << subarraySum(nums, k) << endl;
    return 0;
}

A 0

B 1000

C 999

D 998

💡 Hint

Count how many subarrays of length 2 sum to 2 in an array of 1s.

Each pair of consecutive 1s sums to 2. There are 999 such pairs in 1000 elements.

🧠 Conceptual

expert

Why Use Hash Map in Subarray Sum Equals K?

Which reason best explains why a hash map is used in the subarray sum equals k algorithm?

A To store all subarrays explicitly for counting

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

C To sort the array elements for binary search

D To keep track of maximum subarray length

💡 Hint

Think about how the algorithm finds if a previous sum exists to form k.

The hash map stores how many times each prefix sum has appeared, allowing quick checks if sum-k occurred before, which means a subarray sums to k.

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