Subarray Sum Equals K Using Hash Map in DSA Rust - Execution Trace

Concept Flow - Subarray Sum Equals K Using Hash Map

Start with sum=0, map={0:1}

↓

Iterate over array elements

↓

Add current element to sum

↓

Check if (sum-k) in map?

↓

Add map[sum-k

↓

Update map with sum count

↓

Repeat for next element

↓

Return total count

We keep a running sum and use a map to count how many times each sum appears. For each element, we check if sum-k was seen before to find subarrays summing to k.

Execution Sample

DSA Rust

nums = [1, 2, 3]
k = 3
sum = 0
map = {0:1}
count = 0
for num in nums:
    sum += num
    if (sum - k) in map:
        count += map[sum - k]
    map[sum] = map.get(sum, 0) + 1

This code counts subarrays in nums that sum to k using a hash map to track prefix sums.

Execution Table

Step	Operation	Current Num	Running Sum	Check sum-k in map	Count Updated	Map State	Subarrays Found
1	Start	N/A	0	N/A	count=0	{0:1}	[]
2	Add num	1	1	1-3=-2 in map? No	count=0	{0:1,1:1}	[]
3	Add num	2	3	3-3=0 in map? Yes	count=0+1=1	{0:1,1:1,3:1}	[[1,2]]
4	Add num	3	6	6-3=3 in map? Yes	count=1+1=2	{0:1,1:1,3:1,6:1}	[[1,2],[3]]
5	End	N/A	N/A	N/A	Final count=2	{0:1,1:1,3:1,6:1}	[[1,2],[3]]

💡 All elements processed, total subarrays with sum k found.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
sum	0	1	3	6	6
count	0	0	1	2	2
map	{0:1}	{0:1,1:1}	{0:1,1:1,3:1}	{0:1,1:1,3:1,6:1}	{0:1,1:1,3:1,6:1}

Key Moments - 3 Insights

Why do we initialize the map with {0:1} before starting?

Because a subarray starting from index 0 that sums to k means sum-k=0, so we count that initial sum 0 once (see Step 3 in execution_table).

Why do we check if sum-k is in the map at each step?

Because if sum-k was seen before, the subarray between that previous index and current index sums to k (see Steps 3 and 4 where count increases).

Why do we update the map with the current sum after checking?

To record that this sum has been seen, so future elements can find subarrays ending later (map updates happen after count checks in each step).

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the running sum and does sum-k exist in the map?

A Running sum is 3, sum-k=0 exists in map

B Running sum is 1, sum-k=2 does not exist

C Running sum is 3, sum-k=3 does not exist

D Running sum is 6, sum-k=3 exists

💡 Hint

Check columns 'Running Sum' and 'Check sum-k in map' at Step 3 in execution_table

At which step does the count first increase due to finding sum-k in the map?

A Step 1

B Step 3

C Step 4

D Step 2

💡 Hint

Look at 'Count Updated' column in execution_table; first count update happens at Step 3

If the input array was [1, 1, 1] and k=2, how would the count change after processing the second element?

A Count would be 0

B Count would be 2

C Count would be 1

D Count would be 3

💡 Hint

Think about how many subarrays sum to 2 after two elements, referencing how count updates in execution_table

Concept Snapshot

Subarray Sum Equals K Using Hash Map
- Keep running sum and a map of sum frequencies
- Initialize map with {0:1} for empty prefix
- For each element: sum += num
- Check if (sum-k) in map, add map[sum-k] to count
- Update map[sum] += 1
- Result is total count of subarrays summing to k

Full Transcript

This concept uses a running sum and a hash map to find how many subarrays sum to a target k. We start with sum zero and map containing zero once. For each number, we add it to sum. We check if sum minus k was seen before in the map. If yes, it means a subarray ending here sums to k, so we add how many times sum-k appeared to the count. Then we update the map with the current sum. After processing all elements, the count is the total number of subarrays with sum k.

Practice

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

easy

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

B. To sort the array elements before processing

C. To store the original array elements as keys

D. To reverse the array for easier traversal

Solution

1. Step 1: Understand the problem requirement

   The problem requires finding subarrays whose sums equal a target value k. Using a hash map helps track cumulative sums efficiently.

2. Step 2: Role of hash map in the solution

   The hash map stores cumulative sums as keys and their counts as values. This allows quick checking if a previous sum exists that forms a subarray summing to k.

3. Final Answer:

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

4. Quick Check:

   Hash map stores sums = A [OK]

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

Common Mistakes:

• Thinking hash map stores individual elements only
• Using hash map to sort elements
• Ignoring cumulative sums concept

2. Which of the following Rust code snippets correctly initializes a hash map to store cumulative sums and their counts?

easy

A. let map = std::collections::HashMap;

B. let mut map = std::collections::HashMap::new();

C. let mut map = HashMap();

D. let map = HashMap::new();

Solution

1. Step 1: Identify correct HashMap initialization syntax in Rust

   Rust requires importing and initializing a mutable HashMap with std::collections::HashMap::new() and mut if we want to modify it.

2. Step 2: Check each option

   let mut map = std::collections::HashMap::new(); uses correct syntax with mut and full path. let map = HashMap::new(); misses mut. let mut map = HashMap(); uses wrong constructor syntax. let map = std::collections::HashMap; is incomplete.

3. Final Answer:

   let mut map = std::collections::HashMap::new(); -> Option B

4. Quick Check:

   Correct Rust HashMap init = D [OK]

Hint: Use mut and full path to create modifiable HashMap [OK]

Common Mistakes:

• Forgetting mut for mutable map
• Using wrong constructor syntax
• Omitting std::collections prefix

3. What will be the output of the following Rust code snippet that counts subarrays summing to k = 3?

use std::collections::HashMap;

fn subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
    let mut count = 0;
    let mut sum = 0;
    let mut map = HashMap::new();
    map.insert(0, 1);
    for num in nums {
        sum += num;
        if let Some(&c) = map.get(&(sum - k)) {
            count += c;
        }
        *map.entry(sum).or_insert(0) += 1;
    }
    count
}

fn main() {
    let nums = vec![1, 2, 1, 2, 1];
    let k = 3;
    println!("{}", subarray_sum(nums, k));
}

medium

A. 5

B. 3

C. 2

D. 4

Solution

1. Step 1: Trace cumulative sums and map updates

   nums = [1,2,1,2,1], k=3 - sum=1, map={0:1,1:1}, count=0 - sum=3, map has (3-3)=0 count=1, count=1, map={0:1,1:1,3:1} - sum=4, map has (4-3)=1 count=1, count=2, map={0:1,1:1,3:1,4:1} - sum=6, map has (6-3)=3 count=1, count=3, map={0:1,1:1,3:1,4:1,6:1} - sum=7, map has (7-3)=4 count=1, count=4, map={0:1,1:1,3:1,4:1,6:1,7:1}

2. Step 2: Calculate final count of subarrays

   Total count of subarrays summing to 3 is 4.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Count of subarrays = 4 [OK]

Hint: Track cumulative sums and check map for (sum-k) [OK]

Common Mistakes:

• Not initializing map with (0,1)
• Incorrectly updating count
• Confusing sum and index

4. Identify the bug in this Rust function for counting subarrays summing to k and select the fix:

fn subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
    let mut count = 0;
    let mut sum = 0;
    let mut map = std::collections::HashMap::new();
    for num in nums {
        sum += num;
        if let Some(&c) = map.get(&(sum - k)) {
            count += c;
        }
        map.insert(sum, 1);
    }
    count
}

medium

A. Change map.insert(sum, 1) to map.entry(sum).or_insert(0) += 1

B. Initialize map with (0,1) before loop

C. Remove the if let block checking map.get

D. Initialize count to 1 instead of 0

Solution

1. Step 1: Identify problem with map insertion

   Using map.insert(sum, 1) overwrites previous counts, losing frequency data needed for correct counting.

2. Step 2: Correct way to update map counts

   Use map.entry(sum).or_insert(0) += 1 to increment count if sum exists or insert 0 then increment, preserving frequencies.

3. Final Answer:

   Change map.insert(sum, 1) to map.entry(sum).or_insert(0) += 1 -> Option A

4. Quick Check:

   Use entry API to update counts [OK]

Hint: Use entry().or_insert(0) += 1 to update counts safely [OK]

Common Mistakes:

• Overwriting counts with insert instead of incrementing
• Not initializing map with (0,1)
• Ignoring frequency updates

5. Given an array nums = [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. 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 - sum=3, map={0:1,3:1}, count=0 - sum=7, map has (7-7)=0 count=1, count=1, map={0:1,3:1,7:1} - sum=14, map has (14-7)=7 count=1, count=2, map={0:1,3:1,7:1,14:1} - sum=16, map has (16-7)=9 no, count=2, map={0:1,3:1,7:1,14:1,16:1} - sum=13, map has (13-7)=6 no, count=2, map={0:1,3:1,7:1,14:1,16:1,13:1} - sum=14, map has (14-7)=7 count=1, count=3, map={0:1,3:1,7:1,14:2,16:1,13:1} - sum=18, map has (18-7)=11 no, count=3, map={0:1,3:1,7:1,14:2,16:1,13:1,18:1} - sum=20, map has (20-7)=13 count=1, count=4, map={0:1,3:1,7:1,14:2,16:1,13:1,18:1,20:1}

2. Step 2: Count subarrays carefully including duplicates

   The trace shows four increments corresponding to the four subarrays summing to 7: [3,4], [7], [7,2,-3,1], [1,4,2]. Total count is 4.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Count subarrays with sum k = 4 [OK]

Hint: Count frequencies of sums and check (sum-k) in map [OK]

Common Mistakes:

• Not counting repeated cumulative sums correctly
• Missing negative numbers effect
• Forgetting to initialize map with (0,1)