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

Recall & Review

beginner

What is the main idea behind using a hash map to solve the Subarray Sum Equals K problem?

We use a hash map to store the cumulative sums and their frequencies. This helps us quickly find if there is a previous cumulative sum that, when subtracted from the current cumulative sum, equals k, indicating a subarray summing to k.

beginner

In the Subarray Sum Equals K problem, what does the key in the hash map represent?

The key represents a cumulative sum of elements from the start of the array up to a certain index.

intermediate

Why do we initialize the hash map with {0:1} in the Subarray Sum Equals K solution?

We initialize with {0:1} to handle the case where a subarray starting from index 0 sums exactly to k. It means the cumulative sum equals k at that point.

intermediate

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

The time complexity is O(n), where n is the number of elements in the array, because we traverse the array once and perform constant time hash map operations.

advanced

How does the hash map help in counting multiple subarrays that sum to k?

The hash map stores frequencies of cumulative sums. When the difference (current_sum - k) appears multiple times, it means multiple subarrays ending at the current index sum to k, and we add all those counts.

What does the cumulative sum represent in the Subarray Sum Equals K problem?

A Sum of elements from start to current index

B Sum of elements from current index to end

C Sum of all elements in the array

D Sum of elements excluding current index

Cumulative sum is the sum of elements from the start of the array up to the current index.

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

A To count total elements processed

B To find if a subarray sums to k ending at current index

C To reset the cumulative sum

D To find the maximum sum subarray

If (current_sum - k) exists, it means a previous cumulative sum allows a subarray summing to k ending at current index.

What initial value is stored in the hash map before processing the array?

A {} (empty)

B {k:1}

C {0:1}

D {sum:0}

We start with {0:1} to count subarrays that start from index 0 and sum to k.

What is the space complexity of the hash map approach for Subarray Sum Equals K?

A O(n^2)

B O(1)

C O(log n)

D O(n)

The hash map can store up to n cumulative sums, so space complexity is O(n).

If the array is [1, 2, 3] and k=3, how many subarrays sum to k?

A 2

B 1

C 3

D 0

Subarrays [1, 2] and [3] both sum to 3.

Explain how a hash map is used to find the number of subarrays that sum to k.

Think about how previous sums help identify subarrays ending at current index.

Describe the step-by-step process to solve Subarray Sum Equals K using a hash map.

Focus on how each element updates the cumulative sum and hash map.

Practice

1. What is the main purpose of using a hash map in the Subarray Sum Equals K problem?

easy

A. To sort the array elements before processing

B. To keep track of the maximum subarray length

C. To store the original array elements as keys

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

Solution

1. Step 1: Understand the problem goal

   The problem requires finding the number of continuous subarrays whose sum equals a target value k.

2. Step 2: Role of hash map in solution

   A hash map stores cumulative sums encountered so far and their counts. This allows quick checking if a previous cumulative sum exists that can form a subarray summing to k.

3. Final Answer:

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

4. Quick Check:

   Hash map stores sums [OK]

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

Common Mistakes:

• Thinking hash map stores array elements as keys
• Assuming sorting is needed
• Using hash map to track max length instead of sums

2. Which of the following is the correct way to initialize the hash map for cumulative sums in Python?

easy

A. hash_map = {0: 1}

B. hash_map = {}

C. hash_map = {k: 0}

D. hash_map = {None: 0}

Solution

1. Step 1: Understand initialization role

   We initialize the hash map with cumulative sum 0 having count 1 to handle subarrays starting from index 0.

2. Step 2: Check each option

   hash_map = {0: 1} correctly initializes with {0: 1}. hash_map = {} is empty, missing initial sum. hash_map = {k: 0} uses undefined k. hash_map = {None: 0} uses None key which is incorrect.

3. Final Answer:

   hash_map = {0: 1} -> Option A

4. Quick Check:

   Start with sum 0 count 1 [OK]

Hint: Start hash map with {0:1} for empty prefix sum [OK]

Common Mistakes:

• Not initializing with {0:1}
• Using empty dictionary without base case
• Using invalid keys like None or undefined variables

3. What is the output of the following code?

def subarray_sum(nums, k):
    count = 0
    cum_sum = 0
    hash_map = {0: 1}
    for num in nums:
        cum_sum += num
        if cum_sum - k in hash_map:
            count += hash_map[cum_sum - k]
        hash_map[cum_sum] = hash_map.get(cum_sum, 0) + 1
    return count

print(subarray_sum([1, 2, 3], 3))

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Trace cumulative sums and hash map updates

   nums = [1,2,3], k=3 - cum_sum=1, hash_map={0:1,1:1}, cum_sum-k= -2 not in map - cum_sum=3, hash_map={0:1,1:1,3:1}, cum_sum-k=0 in map count=1 - cum_sum=6, hash_map={0:1,1:1,3:1,6:1}, cum_sum-k=3 in map count=1+1=2

2. Step 2: Final count of subarrays

   Two subarrays sum to 3: [1,2] and [3].

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Subarrays [1,2], [3] = 2 [OK]

Hint: Count increments when cum_sum-k found in map [OK]

Common Mistakes:

• Not updating count correctly
• Ignoring initial hash_map entry
• Miscounting subarrays overlapping

4. Find the error in this code snippet for counting subarrays with sum k:

def subarray_sum(nums, k):
    count = 0
    cum_sum = 0
    hash_map = {0: 0}
    for num in nums:
        cum_sum += num
        if cum_sum - k in hash_map:
            count += hash_map[cum_sum - k]
        hash_map[cum_sum] = hash_map.get(cum_sum, 0) + 1
    return count

print(subarray_sum([1, 1, 1], 2))

medium

A. hash_map initialized with {0: 0} instead of {0: 1}

B. cum_sum should be reset inside the loop

C. count should be incremented by 1 instead of hash_map value

D. hash_map update line is missing

Solution

1. Step 1: Check hash_map initialization

   hash_map is initialized as {0: 0}, but it should be {0: 1} to count subarrays starting at index 0.

2. Step 2: Effect of wrong initialization

   With {0: 0}, the code misses counting subarrays that start from the beginning, leading to incorrect count.

3. Final Answer:

   hash_map initialized with {0: 0} instead of {0: 1} -> Option A

4. Quick Check:

   Initialize {0:1} to count empty prefix [OK]

Hint: Initialize hash_map with {0:1} to count prefix sums [OK]

Common Mistakes:

• Setting initial count to 0 instead of 1
• Resetting cum_sum inside loop incorrectly
• Ignoring hash_map update line

5. Given the array nums = [3, 4, 7, 2, -3, 1, 4, 2] and k = 7, how many subarrays sum to k? Use the hash map approach.

hard

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Calculate cumulative sums and track counts

   nums = [3,4,7,2,-3,1,4,2], k=7
   - cum=3, -4 not, map={0:1,3:1}, count=0
   - cum=7, 0 yes (+1), count=1, map={...,7:1}
   - cum=14, 7 yes (+1), count=2, map={...,14:1}
   - cum=16, 9 no, count=2, map={...,16:1}
   - cum=13, 6 no, count=2, map={...,13:1}
   - cum=14, 7 yes (+1), count=3, map={...,14:2}
   - cum=18, 11 no, count=3, map={...,18:1}
   - cum=20, 13 yes (+1), count=4, map={...,20:1}

2. Step 2: Count total subarrays

   Four subarrays sum to 7: [3,4], [7], [7,2,-3,1], [1,4,2].

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Count subarrays using cum_sum and map = 4 [OK]

Hint: Add counts when (cum_sum - k) found in map [OK]

Common Mistakes:

• Not counting repeated cumulative sums correctly
• Forgetting negative numbers affect sums
• Miscounting overlapping subarrays