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

Recall & Review

beginner

What is the main idea behind using a hash map to find subarrays with sum equals k?

We keep track of cumulative sums and their frequencies in a hash map. For each new sum, we check if (current_sum - k) exists in the map, which means a subarray summing to k ends here.

beginner

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

Because a cumulative sum of 0 occurs once before starting. This helps count subarrays that start from index 0 and sum to k.

intermediate

In the context of Subarray Sum Equals K, what does the expression (current_sum - k) represent?

It represents a previous cumulative sum that, if found, indicates the subarray between that previous index and current index sums to k.

intermediate

How does the hash map help achieve better time complexity compared to a brute force approach?

The hash map allows checking for needed sums in constant time, reducing the overall time complexity from O(n²) to O(n).

beginner

What is the role of cumulative sum in the Subarray Sum Equals K problem?

Cumulative sum helps represent the sum of elements from the start up to the current index, enabling quick calculation of any subarray sum by subtraction.

What initial value should the hash map contain before processing the array?

A {0:1}

B {k:1}

C {} (empty)

D {sum_of_array:1}

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

If current cumulative sum is 10 and k is 7, what sum should we look for in the hash map?

A 3

B 17

C 7

D 10

We look for (current_sum - k) = 10 - 7 = 3 in the hash map.

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

A O(n²)

B O(log n)

C O(n)

D O(n log n)

Using a hash map, we process each element once, so time complexity is O(n).

What does the value stored in the hash map represent?

A Length of subarray

B Index of the last occurrence

C Sum of all elements

D Frequency of cumulative sums encountered

The hash map stores how many times each cumulative sum has appeared.

Why can't we just check subarrays by nested loops instead of using a hash map?

A Nested loops don't find subarrays

B Nested loops are slower with O(n²) time

C Hash map uses more memory

D Nested loops are harder to code

Nested loops check all pairs and take O(n²) time, which is slower than the hash map approach.

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

Think about how sums before and after an index relate.

Describe the step-by-step process of solving Subarray Sum Equals K using a hash map.

Focus on how cumulative sums and hash map interact.

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)