Subarray Sum Equals K Using Hash Map in DSA Rust

Mental Model

We keep track of sums of elements from the start and use a map to find if a previous sum can help form a subarray with sum k.

Analogy: Imagine walking along a path and counting steps. If you know how many steps you took before, you can quickly find if a segment of your walk adds up to a target number by subtracting previous counts.

Array: [1] -> [2] -> [3] -> [4] -> [5]
Prefix sums map: {0:1, 1:1, 3:1, 6:1, 10:1, 15:1}
↑ current prefix sum
Keys are sums seen so far, values are counts of those sums

Dry Run Walkthrough

Input: array: [1, 2, 3], k = 3

Goal: Find how many continuous subarrays sum to 3

Step 1: Start with prefix_sum = 0 and map = {0:1} to count empty prefix

prefix_sum=0, map={0:1}, count=0

Why: We count empty prefix to handle subarrays starting at index 0

Step 2: Add first element 1 to prefix_sum -> prefix_sum=1; check if prefix_sum-k=1-3=-2 in map (no)

prefix_sum=1, map={0:1,1:1}, count=0

Why: No subarray ending here sums to k yet; record prefix_sum

Step 3: Add second element 2 -> prefix_sum=3; check prefix_sum-k=3-3=0 in map (yes, count=1)

prefix_sum=3, map={0:1,1:1,3:1}, count=1

Why: Found subarray [1,2] summing to k; increment count

Step 4: Add third element 3 -> prefix_sum=6; check prefix_sum-k=6-3=3 in map (yes, count=1+1=2)

prefix_sum=6, map={0:1,1:1,3:1,6:1}, count=2

Why: Found subarray [3] summing to k; increment count

Result:

Final count=2; subarrays are [1,2] and [3]

Annotated Code

DSA Rust

use std::collections::HashMap;

fn subarray_sum(nums: &[i32], k: i32) -> i32 {
    let mut count = 0;
    let mut prefix_sum = 0;
    let mut map = HashMap::new();
    map.insert(0, 1); // empty prefix sum count

    for &num in nums {
        prefix_sum += num; // add current number to prefix sum
        if let Some(&freq) = map.get(&(prefix_sum - k)) {
            count += freq; // add count of prefix sums that match prefix_sum-k
        }
        *map.entry(prefix_sum).or_insert(0) += 1; // record current prefix sum
    }
    count
}

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

map.insert(0, 1); // empty prefix sum count

initialize map with zero prefix sum to handle subarrays starting at index 0

prefix_sum += num; // add current number to prefix sum

update running sum with current element

if let Some(&freq) = map.get(&(prefix_sum - k)) { count += freq; }

check if a previous prefix sum exists that forms subarray summing to k

*map.entry(prefix_sum).or_insert(0) += 1; // record current prefix sum

record current prefix sum frequency for future subarray checks

Output

2

Complexity Analysis

Time: O(n) because we traverse the array once and do constant time map operations per element

Space: O(n) because in worst case all prefix sums are unique and stored in the map

vs Alternative: Naive approach is O(n^2) by checking all subarrays; this method uses prefix sums and a map to reduce to O(n)

Edge Cases

empty array

returns 0 since no subarrays exist

DSA Rust

map.insert(0, 1); // empty prefix sum count

array with all zeros and k=0

counts all subarrays of zeros correctly using prefix sums

DSA Rust

if let Some(&freq) = map.get(&(prefix_sum - k)) { count += freq; }

no subarray sums to k

returns 0 as count

DSA Rust

if let Some(&freq) = map.get(&(prefix_sum - k)) { count += freq; }

When to Use This Pattern

When asked to find count of subarrays with a target sum, use prefix sums with a hash map to track sums and find matches efficiently.

Common Mistakes

Mistake: Not initializing the map with {0:1}, missing subarrays starting at index 0
Fix: Always insert 0 with count 1 before loop to handle subarrays from start

Mistake: Using prefix_sum instead of prefix_sum - k to check map
Fix: Check map for prefix_sum - k to find valid subarrays ending at current index

Summary

Counts how many continuous subarrays sum to a target k using prefix sums and a hash map.

Use when you need to find subarrays with a specific sum efficiently in O(n) time.

The key insight is that difference of prefix sums reveals subarrays summing to 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)