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

Subarray Sum Equals K Using Hash Map

📖 Scenario: You are analyzing daily sales data represented as a list of integers. You want to find how many continuous days' sales add up exactly to a target number k. This helps in spotting special sales patterns.

🎯 Goal: Build a Rust program that counts the number of continuous subarrays whose sum equals k using a hash map for efficient lookup.

📋 What You'll Learn

Create a vector called sales with the exact values: [1, 2, 3, 4, 2]

Create an integer variable called k and set it to 5

Use a hash map called prefix_sums to store cumulative sums and their counts

Implement a loop to iterate over sales and count subarrays summing to k

Print the final count of such subarrays

💡 Why This Matters

🌍 Real World

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

💼 Career

This technique is useful in data analysis, software engineering, and algorithm design roles where efficient data processing is required.

1

Create the sales data vector

Create a vector called sales with the exact values [1, 2, 3, 4, 2].

DSA Rust

# Create a vector called sales with values [1, 2, 3, 4, 2]
// Your code here

Hint

Use let sales = vec![1, 2, 3, 4, 2]; to create the vector.

2

Set the target sum k

Create an integer variable called k and set it to 5 inside the main function after the sales vector.

DSA Rust

fn main() {
    let sales = vec![1, 2, 3, 4, 2];
    // Create an integer variable k and set it to 5
    // Your code here
}

Hint

Use let k = 5; to create the target sum variable.

3

Implement the subarray sum counting logic

Inside the main function, create a mutable hash map called prefix_sums from std::collections::HashMap to store cumulative sums and their counts. Initialize it with 0 mapped to 1. Create mutable integers count and current_sum set to 0. Use a for loop with variable num to iterate over sales. In each iteration, add num to current_sum. Check if current_sum - k exists in prefix_sums and if so, add its value to count. Then update prefix_sums to increment the count for current_sum by 1 or insert it if not present.

DSA Rust

fn main() {
    let sales = vec![1, 2, 3, 4, 2];
    let k = 5;
    // Implement the subarray sum counting logic using prefix_sums hash map
    // Your code here
}

Hint

Use a hash map to track how many times each cumulative sum appears. For each number, update the current sum and check if current_sum - k was seen before.

4

Print the count of subarrays summing to k

Add a println! statement inside the main function to print the value of count.

DSA Rust

use std::collections::HashMap;

fn main() {
    let sales = vec![1, 2, 3, 4, 2];
    let k = 5;

    let mut prefix_sums = HashMap::new();
    prefix_sums.insert(0, 1);

    let mut count = 0;
    let mut current_sum = 0;

    for num in sales {
        current_sum += num;
        if let Some(&freq) = prefix_sums.get(&(current_sum - k)) {
            count += freq;
        }
        *prefix_sums.entry(current_sum).or_insert(0) += 1;
    }
    // Print the count variable
    // Your code here
}

Hint

Use println!("{}", count); to display the final count.

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)