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 previous sum allows a subarray to sum to k.

Analogy: Imagine walking along a path and noting the total distance walked at each step. If you want to find a segment of the path that is exactly k long, you check if you have been at a distance that is current distance minus k before.

Array: [1] -> [2] -> [3] -> [4] -> [5]
Prefix sums: 0 -> 1 -> 3 -> 6 -> 10 -> 15
Hash map 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: Initialize prefix_sum = 0, map = {0:1} to count empty prefix

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 prefix_sum: prefix_sum=1; check if prefix_sum-k=1-3=-2 in map (no); add prefix_sum=1 to map

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

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

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

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

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

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

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

Why: Found subarray [3] summing to k

Result:

Final result = 2 subarrays
Subarrays: [1,2], [3]

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node for hashmap chaining
typedef struct Node {
    int key;
    int value;
    struct Node* next;
} Node;

// Simple hashmap with chaining
#define HASH_SIZE 1000

Node* hashMap[HASH_SIZE];

unsigned int hash(int key) {
    return (unsigned int)((key % HASH_SIZE + HASH_SIZE) % HASH_SIZE);
}

// Find node with key
Node* findNode(int key) {
    unsigned int h = hash(key);
    Node* curr = hashMap[h];
    while (curr) {
        if (curr->key == key) return curr;
        curr = curr->next;
    }
    return NULL;
}

// Insert or update key with value
void put(int key, int value) {
    Node* node = findNode(key);
    if (node) {
        node->value += value; // increment count
    } else {
        unsigned int h = hash(key);
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->key = key;
        newNode->value = value;
        newNode->next = hashMap[h];
        hashMap[h] = newNode;
    }
}

// Get value for key or 0 if not found
int get(int key) {
    Node* node = findNode(key);
    if (node) return node->value;
    return 0;
}

int subarraySum(int* nums, int numsSize, int k) {
    int count = 0;
    int prefix_sum = 0;
    // Initialize hashmap
    for (int i = 0; i < HASH_SIZE; i++) hashMap[i] = NULL;
    put(0, 1); // prefix sum 0 occurs once

    for (int i = 0; i < numsSize; i++) {
        prefix_sum += nums[i]; // add current element to prefix sum
        count += get(prefix_sum - k); // check if prefix_sum-k seen before
        put(prefix_sum, 1); // add/update prefix_sum count
    }
    return count;
}

int main() {
    int nums[] = {1, 2, 3};
    int k = 3;
    int result = subarraySum(nums, 3, k);
    printf("%d\n", result);
    return 0;
}

put(0, 1); // prefix sum 0 occurs once

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

prefix_sum += nums[i]; // add current element to prefix sum

update running sum including current element

count += get(prefix_sum - k); // check if prefix_sum-k seen before

add count of previous prefix sums that allow subarray sum k ending here

put(prefix_sum, 1); // add/update prefix_sum count

record current prefix sum in map for future subarrays

Output

2

Complexity Analysis

Time: O(n) because we traverse the array once and each hashmap operation is O(1) on average

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

vs Alternative: Naive approach is O(n^2) by checking all subarrays; hashmap reduces it to O(n)

Edge Cases

empty array

returns 0 since no subarrays exist

DSA C

for (int i = 0; i < numsSize; i++) { ... } handles zero iterations

array with all zeros and k=0

counts all subarrays of zeros correctly using prefix sums

DSA C

put(0, 1); ensures subarrays starting at index 0 are counted

no subarray sums to k

returns 0 as no prefix_sum-k found in map

DSA C

count += get(prefix_sum - k); adds zero if not found

When to Use This Pattern

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

Common Mistakes

Mistake: Not initializing hashmap with sum zero count 1
Fix: Add put(0, 1) before loop to handle subarrays starting at index 0

Mistake: Using prefix_sum instead of prefix_sum - k to check map
Fix: Check map for prefix_sum - k to find valid subarrays ending at current index

Summary

Counts how many continuous subarrays sum exactly to k using prefix sums and a hashmap.

Use when you need to find number of subarrays with a given sum efficiently.

The key insight is that if prefix_sum[j] - prefix_sum[i] = k, then subarray (i+1 to j) 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 store the original array elements as keys

B. To sort the array elements before processing

C. To keep track of the maximum subarray length

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

Solution

1. Step 1: Understand the problem requirement

   The problem requires finding subarrays whose sums equal a target value k.

2. Step 2: Role of hash map in the solution

   The hash map stores cumulative sums seen so far and their counts to quickly check if a subarray sum equals k exists.

3. Final Answer:

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

4. Quick Check:

   Hash map stores sums for fast subarray sum checks [OK]

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

Common Mistakes:

• Thinking hash map sorts elements
• Using hash map to store array elements directly
• Confusing hash map with array for indexing

2. Which of the following is the correct way to initialize a hash map in C for storing integer keys and values?

easy

A. map map;

B. HashMap map = new HashMap<>();

C. int map[1000] = {0};

D. unordered_map map;

Solution

1. Step 1: Identify C language syntax

   In C, hash maps are not built-in; arrays can be used as simple maps for small ranges.

2. Step 2: Check options for C syntax

   int map[1000] = {0}; uses an integer array initialized to zero, suitable as a simple map in C.

3. Final Answer:

   int map[1000] = {0}; -> Option C

4. Quick Check:

   Array initialization is valid C syntax [OK]

Hint: Use arrays for maps in C, no built-in hash map [OK]

Common Mistakes:

• Using C++ or Java syntax in C code
• Trying to declare hash maps directly in C
• Not initializing arrays before use

3. What will be the output of the following code snippet in C that counts subarrays summing to k=5?

int arr[] = {1, 2, 3, 2, 1};
int k = 5;
// Assume correct hash map logic implemented
int result = subarraySum(arr, 5, k);
printf("%d", result);

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Identify subarrays summing to 5

   Subarrays: [2,3] (indices 1-2), [3,2] (indices 2-3), [2,3] (indices 3-4); total 3 subarrays.

2. Step 2: Count valid subarrays

   Counting carefully, the subarrays summing to 5 are three in total.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count of subarrays with sum 5 = 3 [OK]

Hint: Count all subarrays with sum k using prefix sums [OK]

Common Mistakes:

• Counting only non-overlapping subarrays
• Missing subarrays starting at index 0
• Incorrectly summing elements

4. Identify the bug in this C code snippet for counting subarrays with sum k using a hash map:

int subarraySum(int* nums, int numsSize, int k) {
    int count = 0, sum = 0;
    int map[10000] = {0};
    map[0] = 1;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
        if (map[sum - k])
            count += map[sum - k];
        map[sum]++;
    }
    return count;
}

medium

A. Array map size is too small for negative sums

B. Missing initialization of count variable

C. Incorrect loop range causing out-of-bounds access

D. Using map as pointer without allocation

Solution

1. Step 1: Analyze map usage for sums

   The map array uses indices as sums, but sums can be negative, causing invalid indexing.

2. Step 2: Identify impact of negative sums

   Negative sums cause out-of-bound access or wrong counts since array indices can't be negative.

3. Final Answer:

   Array map size is too small for negative sums -> Option A

4. Quick Check:

   Negative sums need offset or different data structure [OK]

Hint: Handle negative sums with offset or hash map [OK]

Common Mistakes:

• Ignoring negative sums in indexing
• Assuming sums are always positive
• Not initializing map for sum 0

5. Given an array arr = {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 answer.

hard

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Calculate prefix sums and track counts

   Prefix sums: 3,7,14,16,13,14,18,20. Check sums - k in map to count subarrays.

2. Step 2: Count subarrays with sum k=7

   Subarrays: [3,4], [7], [7,2,-3,1], [1,4,2], [4,2, -3,1,4] total 5 subarrays.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Count subarrays summing to 7 = 5 [OK]

Hint: Use prefix sums and hash map to count subarrays fast [OK]

Common Mistakes:

• Missing subarrays with negative numbers
• Counting overlapping subarrays incorrectly
• Not updating hash map counts properly