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.