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

Subarray Sum Equals K Using Hash Map

📖 Scenario: You are analyzing daily sales data for a small store. You want to find how many continuous days had sales that add up exactly to a target number.

🎯 Goal: Build a program that counts the number of continuous subarrays in a list of daily sales that sum to a given target k using a hash map for efficient lookup.

📋 What You'll Learn

Create a list called sales with the exact values [3, 4, 7, 2, -3, 1, 4, 2]

Create a variable called k and set it to 7

Use a hash map (dictionary) called prefix_sums to store counts of prefix sums

Use a variable called count to keep track of the number of subarrays summing to k

Use a variable called current_sum to store the running sum while iterating through sales

Print the final count of subarrays that sum to k

💡 Why This Matters

🌍 Real World

Finding continuous periods where sales or other metrics meet exact targets helps businesses analyze trends and make decisions.

💼 Career

This technique is useful for software engineers and data analysts working on time series data, financial analysis, or any scenario requiring efficient subarray sum calculations.

1

Create the sales data list

Create a list called sales with these exact values: [3, 4, 7, 2, -3, 1, 4, 2]

DSA Python

# Create the sales list with exact values
# Your code here

Hint

Use square brackets to create a list and separate numbers with commas.

2

Set the target sum k

Create a variable called k and set it to the integer 7

DSA Python

sales = [3, 4, 7, 2, -3, 1, 4, 2]
# Set the target sum k to 7
# Your code here

Hint

Use = to assign the value 7 to the variable k.

3

Count subarrays summing to k using a hash map

Create a dictionary called prefix_sums with initial entry {0: 1}. Create variables count and current_sum set to 0. Use a for loop with variable num to iterate over sales. Inside the loop, add num to current_sum. Check if current_sum - k is in prefix_sums and if yes, add its value to count. Update prefix_sums[current_sum] by adding 1 if it exists or setting it to 1 if not.

DSA Python

sales = [3, 4, 7, 2, -3, 1, 4, 2]
k = 7
# Initialize prefix_sums, count, current_sum
# Use a for loop to iterate over sales and update count
# Your code here

Hint

Use a dictionary to store counts of sums seen so far. Update count when you find a matching prefix sum.

4

Print the count of subarrays summing to k

Print the variable count to display the number of continuous subarrays in sales that sum to k

DSA Python

sales = [3, 4, 7, 2, -3, 1, 4, 2]
k = 7
prefix_sums = {0: 1}
count = 0
current_sum = 0
for num in sales:
    current_sum += num
    if current_sum - k in prefix_sums:
        count += prefix_sums[current_sum - k]
    prefix_sums[current_sum] = prefix_sums.get(current_sum, 0) + 1
# Print the count variable
# Your code here

Hint

The output should be the total count of subarrays that sum to 7.

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