Subarray Sum Equals K Using Hash Map in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using a hash map to find subarrays with sum equal to k?

We store the cumulative sums and their frequencies in a hash map to quickly find if a subarray with sum k exists by checking if (current_sum - k) has appeared before.

beginner

Why do we use cumulative sums in the Subarray Sum Equals K problem?

Cumulative sums help us find the sum of any subarray by subtracting two cumulative sums, making it easier to check if a subarray sums to k.

intermediate

In the hash map approach, what does the key and value represent?

The key is a cumulative sum value, and the value is the count of how many times this cumulative sum has appeared so far.

intermediate

What is the time complexity of the Subarray Sum Equals K algorithm using a hash map?

The time complexity is O(n) because we traverse the array once and perform constant time hash map operations.

intermediate

How does the algorithm handle the case when a subarray starts from index 0?

We initialize the hash map with {0:1} to count the empty subarray sum, so if cumulative sum equals k at any point, it counts as a valid subarray starting from index 0.

What does the hash map store in the Subarray Sum Equals K problem?

A Array elements and their indices

B Cumulative sums and their frequencies

C Subarray lengths

D Sum of all subarrays

The hash map stores cumulative sums as keys and their frequencies as values to quickly find subarrays summing to k.

Why do we check if (current_sum - k) exists in the hash map?

A To count negative numbers

B To find the maximum subarray length

C To find if a subarray with sum k ends at the current index

D To sort the array

If (current_sum - k) exists, it means a subarray summing to k ends at the current index.

What initial value do we put in the hash map before starting the iteration?

A {0:1}

B {k:1}

C {} (empty)

D {sum:0}

We initialize with {0:1} to handle subarrays starting at index 0.

What is the time complexity of the hash map solution for Subarray Sum Equals K?

A O(1)

B O(n^2)

C O(log n)

D O(n)

The algorithm runs in O(n) time by iterating once and using constant time hash map operations.

What does the value in the hash map represent?

A Frequency of the cumulative sum

B Index of the cumulative sum

C Sum of subarray

D Length of subarray

The value is the count of how many times a cumulative sum has appeared.

Explain how the hash map helps find the number of subarrays that sum to k.

Think about how cumulative sums and their counts relate to subarray sums.

Describe the steps to implement the Subarray Sum Equals K algorithm using a hash map.

Focus on initialization, iteration, and hash map usage.

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