Subarray Sum Equals K Using Hash Map in DSA C#

Mental Model

We keep track of sums of numbers 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 parts of the array add up to 3

Step 1: Start with sum = 0 and map = {0:1} because sum 0 is seen once

sum=0, map={0:1}

Why: We count empty prefix 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); add sum=1 to map

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

Why: No subarray ending here sums to k yet; record sum for future

Step 3: Add second element 2: sum=3; check sum-k=3-3=0 in map (yes, count=1); increment result by 1; add sum=3 to map

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

Why: Found subarray [1,2] that sums to k

Step 4: Add third element 3: sum=6; check sum-k=6-3=3 in map (yes, count=1); increment result by 1; add sum=6 to map

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

Why: Found subarray [3] that sums to k

Result:

Final result = 2 (subarrays [1,2] and [3])

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Solution {
    public static int SubarraySum(int[] nums, int k) {
        int count = 0;
        int sum = 0;
        Dictionary<int, int> map = new Dictionary<int, int>();
        map[0] = 1; // empty prefix sum

        foreach (int num in nums) {
            sum += num; // add current number to running sum
            int target = sum - k;
            if (map.ContainsKey(target)) {
                count += map[target]; // add count of prefix sums that match target
            }
            if (map.ContainsKey(sum)) {
                map[sum] += 1; // increment count of this sum
            } else {
                map[sum] = 1; // first time seeing this sum
            }
        }
        return count;
    }

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

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

initialize map with sum 0 to count subarrays starting at index 0

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

update running sum with current element

int target = sum - k;

calculate needed prefix sum to find subarray summing to k

if (map.ContainsKey(target)) { count += map[target]; }

if target sum seen before, add its count to result

if (map.ContainsKey(sum)) { map[sum] += 1; } else { map[sum] = 1; }

record current sum count for future subarray checks

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 extra space to reduce time to O(n)

Edge Cases

empty array

returns 0 because no subarrays exist

DSA C#

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

array with all zeros and k=0

counts all subarrays of zeros correctly using map counts

DSA C#

if (map.ContainsKey(target)) { count += map[target]; }

no subarray sums to k

returns 0 as no matching sums found

DSA C#

if (map.ContainsKey(target)) { count += map[target]; }

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 and find matches in O(n) time.

Common Mistakes

Mistake: Not initializing map with {0:1}, missing subarrays starting at index 0
Fix: Initialize map with sum 0 count as 1 before loop

Mistake: Updating map sum count before checking for target sum
Fix: Check for target sum in map before updating current sum count

Summary

Counts how many continuous parts of an array add up to a given number k.

Use when you need to find subarrays with a specific sum efficiently.

Keep track of sums seen so far and use their counts to find matching subarrays quickly.

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}