Subarray Sum Equals K Using Hash Map in DSA C - Build from Scratch

Subarray Sum Equals K Using Hash Map

📖 Scenario: Imagine you are analyzing daily sales numbers for a small shop. You want to find how many continuous days had sales that add up exactly to a target number k. This helps the shop owner understand patterns in sales.

🎯 Goal: Build a program that counts the number of continuous subarrays in an integer array whose sum equals a given target k. Use a hash map (implemented with arrays) to efficiently track sums.

📋 What You'll Learn

Create an integer array called sales with the exact values: {1, 2, 3, -2, 5}

Create an integer variable called k and set it to 5

Implement a function subarraySum that takes sales, its length, and k, and returns the count of continuous subarrays summing to k using a hash map

Print the result returned by subarraySum

💡 Why This Matters

🌍 Real World

Finding continuous periods where sales or data points sum to a target helps in financial analysis, detecting patterns, and anomaly detection.

💼 Career

This technique is useful in software engineering roles involving data analysis, algorithm optimization, and performance-critical applications.

1

Create the sales data array

Create an integer array called sales with the exact values {1, 2, 3, -2, 5} and an integer variable n set to the length of sales.

DSA C

# Create the sales array and its length
// Your code here

Hint

Use int sales[] = {1, 2, 3, -2, 5}; and int n = 5; to create the array and its size.

2

Set the target sum k

Create an integer variable called k and set it to 5.

DSA C

int sales[] = {1, 2, 3, -2, 5};
int n = 5;
// Set the target sum k
// Your code here

Hint

Use int k = 5; to set the target sum.

3

Implement the subarraySum function using a hash map

Implement a function called subarraySum that takes int* nums, int numsSize, and int k as parameters and returns an int. Use a hash map (array) to count how many continuous subarrays sum to k. Use variables count, sum, and a fixed-size hash map array hashMap of size 20001 to store frequencies of prefix sums. Initialize hashMap[10000] to 1 to handle zero sum offset. Iterate over nums, update sum, and update count by checking hashMap[sum - k + 10000]. Update hashMap[sum + 10000] accordingly.

DSA C

int sales[] = {1, 2, 3, -2, 5};
int n = 5;
int k = 5;

// Implement subarraySum function below
// Your code here

Hint

Use a fixed-size array as a hash map with offset 10000 to handle negative sums. Initialize hashMap[10000] to 1 for the empty prefix sum. Loop through nums, update sum, and update count and hashMap accordingly.

4

Print the count of subarrays summing to k

Print the result of calling subarraySum with sales, n, and k.

DSA C

int sales[] = {1, 2, 3, -2, 5};
int n = 5;
int k = 5;

int subarraySum(int* nums, int numsSize, int k) {
    int hashMap[20001] = {0};
    int count = 0;
    int sum = 0;
    hashMap[10000] = 1; // offset for zero sum
    for (int i = 0; i = 0 && sum - k + 10000 = 0 && sum + 10000 < 20001) {
            hashMap[sum + 10000]++;
        }
    }
    return count;
}

// Print the count of subarrays
// Your code here

Hint

Use printf("%d\n", subarraySum(sales, n, k)); inside main to print the count.

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