Subarray Sum Equals K Using Hash Map in DSA Rust - Time & Space Complexity

Time Complexity: Subarray Sum Equals K Using Hash Map

O(n)

Understanding Time Complexity

We want to understand how fast the algorithm finds subarrays that add up to a target sum.

How does the time needed grow as the input array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn subarray_sum(nums: &[i32], k: i32) -> i32 {
    use std::collections::HashMap;
    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
}
    

This code counts how many continuous parts of the array add up exactly to k using a hash map.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: One loop through the array elements.
• How many times: Exactly once for each element in the input array.

How Execution Grows With Input

Each element is processed once, and hash map lookups and inserts happen in constant time on average.

Input Size (n)	Approx. Operations
10	About 10 loop steps + 10 hash map operations
100	About 100 loop steps + 100 hash map operations
1000	About 1000 loop steps + 1000 hash map operations

Pattern observation: The work grows roughly in a straight line as input size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows directly with the number of elements in the array.

Common Mistake

[X] Wrong: "Because of the nested hash map operations, the time is O(n²)."

[OK] Correct: Each hash map operation is on average constant time, so they do not multiply the loop steps.

Interview Connect

Understanding this pattern helps you solve many problems where you track sums or counts efficiently.

Self-Check

"What if we replaced the hash map with a simple array for counting sums? How would the time complexity change?"

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)