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#

using System;
using System.Collections.Generic;

class Program {
    static int SubarraySum(int[] nums, int k) {
        int count = 0, sum = 0;
        Dictionary<int, int> map = new Dictionary<int, int>();
        map[0] = 1;
        foreach (int num in nums) {
            sum += num;
            if (map.ContainsKey(sum - k)) {
                count += map[sum - k];
            }
            if (map.ContainsKey(sum)) {
                map[sum]++;
            } else {
                map[sum] = 1;
            }
        }
        return count;
    }

    static void Main() {
        int[] nums = {1, 2, 3};
        int k = 3;
        Console.WriteLine(SubarraySum(nums, k));
    }
}

A 3

B 1

C 2

D 0

💡 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 C# code counting subarrays summing to k when the array contains negative numbers?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int SubarraySum(int[] nums, int k) {
        int count = 0, sum = 0;
        Dictionary<int, int> map = new Dictionary<int, int>();
        map[0] = 1;
        foreach (int num in nums) {
            sum += num;
            if (map.ContainsKey(sum - k)) {
                count += map[sum - k];
            }
            if (map.ContainsKey(sum)) {
                map[sum]++;
            } else {
                map[sum] = 1;
            }
        }
        return count;
    }

    static void Main() {
        int[] nums = {1, -1, 0};
        int k = 0;
        Console.WriteLine(SubarraySum(nums, k));
    }
}

A 3

B 0

C 1

D 2

💡 Hint

Consider subarrays that sum exactly to zero.

Subarrays [1,-1], [-1,0], and [0] sum to 0, so count is 3.

🔧 Debug

advanced

Identify the Runtime Error

What error does this C# code produce when counting subarrays summing to k?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int SubarraySum(int[] nums, int k) {
        int count = 0, sum = 0;
        Dictionary<int, int> map = new Dictionary<int, int>();
        // map[0] = 1; // This line is commented out
        foreach (int num in nums) {
            sum += num;
            if (map.ContainsKey(sum - k)) {
                count += map[sum - k];
            }
            if (map.ContainsKey(sum)) {
                map[sum]++;
            } else {
                map[sum] = 1;
            }
        }
        return count;
    }

    static void Main() {
        int[] nums = {1, 2, 3};
        int k = 3;
        Console.WriteLine(SubarraySum(nums, k));
    }
}

A IndexOutOfRangeException

B NullReferenceException

C No error, outputs 2

D KeyNotFoundException

💡 Hint

Check if the dictionary contains keys before accessing them.

Without initializing map[0] = 1, the code tries to access map[sum - k] when sum-k is 0, which is missing, causing KeyNotFoundException.

🧠 Conceptual

advanced

Why Use a Hash Map for Subarray Sum?

Why is a hash map used in the subarray sum equals k problem instead of a nested loop approach?

A To store all subarrays explicitly for later use

B To reduce time complexity from O(n^2) to O(n) by storing prefix sums counts

C To sort the array before counting subarrays

D To avoid using extra space and improve memory usage

💡 Hint

Think about how prefix sums and counts help avoid repeated summations.

The hash map stores counts of prefix sums to find how many subarrays sum to k in linear time, avoiding nested loops.

❓ Predict Output

expert

Output of Complex Subarray Sum Calculation

What is the output of this C# program that counts subarrays summing to k using a hash map with a larger input?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int SubarraySum(int[] nums, int k) {
        int count = 0, sum = 0;
        Dictionary<int, int> map = new Dictionary<int, int>();
        map[0] = 1;
        foreach (int num in nums) {
            sum += num;
            if (map.ContainsKey(sum - k)) {
                count += map[sum - k];
            }
            if (map.ContainsKey(sum)) {
                map[sum]++;
            } else {
                map[sum] = 1;
            }
        }
        return count;
    }

    static void Main() {
        int[] nums = {3, 4, 7, 2, -3, 1, 4, 2};
        int k = 7;
        Console.WriteLine(SubarraySum(nums, k));
    }
}

A 4

B 3

C 5

D 2

💡 Hint

Count all continuous subarrays that sum to 7 carefully.

The subarrays summing to 7 are [7], [3,4], [7,2,-3,1], and [1,4,2], total 4.

Practice

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

easy

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

B. To sort the array elements before processing

C. To store the original array elements as keys

D. To reverse the array for easier traversal

Solution

1. Step 1: Understand the problem goal

   The problem wants to find subarrays whose sums equal a target value k.

2. Step 2: Role of hash map in solution

   The hash map stores cumulative sums seen so far and how many times they occurred, enabling quick checks for needed sums.

3. Final Answer:

   To store cumulative sums and their frequencies for quick lookup -> Option A

4. Quick Check:

   Hash map stores sums = A [OK]

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

Common Mistakes:

• Thinking hash map stores array elements directly
• Assuming sorting is needed
• Using hash map to reverse array

2. Which of the following is the correct way to declare a hash map (Dictionary) in C# to store cumulative sums and their counts?

easy

A. Dictionary sumCounts = new Dictionary();

B. HashMap sumCounts = new HashMap();

C. Map sumCounts = new Map();

D. Dictionary sumCounts = new Dictionary();

Solution

1. Step 1: Identify correct C# dictionary syntax

   C# uses Dictionary<TKey, TValue> with new Dictionary<TKey, TValue>() to declare hash maps.

2. Step 2: Check each option

   Dictionary sumCounts = new Dictionary(); uses correct generic syntax. Options B and C use Java-like syntax. Dictionary sumCounts = new Dictionary(); misses generic types.

3. Final Answer:

   Dictionary sumCounts = new Dictionary(); -> Option A

4. Quick Check:

   C# Dictionary syntax = A [OK]

Hint: Use Dictionary in C# for hash maps [OK]

Common Mistakes:

• Using Java HashMap syntax in C#
• Omitting generic type parameters
• Using non-existent Map type in C#

3. What is the output of the following C# code snippet?

int[] nums = {1, 2, 3};
int k = 3;
int count = 0;
Dictionary sumCounts = new Dictionary();
sumCounts[0] = 1;
int sum = 0;
foreach (int num in nums) {
    sum += num;
    if (sumCounts.ContainsKey(sum - k)) {
        count += sumCounts[sum - k];
    }
    if (sumCounts.ContainsKey(sum)) {
        sumCounts[sum]++;
    } else {
        sumCounts[sum] = 1;
    }
}
Console.WriteLine(count);

medium

A. 1

B. 0

C. 3

D. 2

Solution

1. Step 1: Calculate cumulative sums and check counts

   nums = [1,2,3], k=3. sumCounts starts with {0:1}. - sum=1: sum-k= -2 (not in sumCounts), count=0, sumCounts={0:1,1:1} - sum=3: sum-k=0 (in sumCounts=1), count=1, sumCounts={0:1,1:1,3:1} - sum=6: sum-k=3 (in sumCounts=1), count=2, sumCounts={0:1,1:1,3:1,6:1}

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 D

4. Quick Check:

   Subarrays count = 2 [OK]

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

Common Mistakes:

• Not initializing sumCounts with {0:1}
• Forgetting to update count correctly
• Misunderstanding sum-k lookup

4. Identify the bug in this C# code snippet for counting subarrays summing to k:

int[] nums = {1, 1, 1};
int k = 2;
int count = 0;
Dictionary sumCounts = new Dictionary();
int sum = 0;
foreach (int num in nums) {
    sum += num;
    if (sumCounts.ContainsKey(sum - k)) {
        count += sumCounts[sum - k];
    }
    sumCounts[sum] = 1;
}
Console.WriteLine(count);

medium

A. nums array is empty

B. sumCounts is not initialized with sum 0 count 1

C. count is not incremented correctly

D. sum variable is not updated inside the loop

Solution

1. Step 1: Check initialization of sumCounts

   sumCounts should start with {0:1} to count subarrays starting at index 0, but here it is empty.

2. Step 2: Check updating sumCounts inside loop

   sumCounts[sum] = 1 overwrites counts instead of incrementing, but main bug is missing initial {0:1}.

3. Final Answer:

   sumCounts is not initialized with sum 0 count 1 -> Option B

4. Quick Check:

   Initialize sumCounts[0] = 1 [OK]

Hint: Always initialize sumCounts with {0:1} before loop [OK]

Common Mistakes:

• Not initializing sumCounts with {0:1}
• Overwriting counts instead of incrementing
• Ignoring sum-k lookup logic

5. Given the array nums = {3, 4, 7, 2, -3, 1, 4, 2} and k = 7, how many subarrays sum to k using the hash map approach?

hard

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Calculate cumulative sums and track counts

   Initialize sumCounts = {0:1}, sum=0, count=0. - i=0: sum=3, sum-k=-4(not found), count=0, sumCounts={0:1,3:1} - i=1: sum=7, sum-k=0(found=1), count=1, sumCounts={0:1,3:1,7:1} - i=2: sum=14, sum-k=7(found=1), count=2, sumCounts={0:1,3:1,7:1,14:1} - i=3: sum=16, sum-k=9(not found), count=2, sumCounts={0:1,3:1,7:1,14:1,16:1} - i=4: sum=13, sum-k=6(not found), count=2, sumCounts={0:1,3:1,7:1,14:1,16:1,13:1} - i=5: sum=14, sum-k=7(found=1), count=3, sumCounts[14]=2 - i=6: sum=18, sum-k=11(not found), count=3, sumCounts={0:1,3:1,7:1,14:2,16:1,13:1,18:1} - i=7: sum=20, sum-k=13(found=1), count=4, sumCounts={0:1,3:1,7:1,14:2,16:1,13:1,18:1,20:1}

2. Step 2: Verify the counted subarrays

   Subarrays summing to 7 are: - [3,4] - [7] - [7,2,-3,1] - [1,4,2] Count is 4 total.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Count subarrays with sum k = 4 [OK]

Hint: Track sums and counts carefully to find all subarrays [OK]

Common Mistakes:

• Missing subarrays with negative numbers
• Not updating counts when sum repeats
• Forgetting to initialize sumCounts with {0:1}