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

Time Complexity: Subarray Sum Equals K Using Hash Map

O(n)

Understanding Time Complexity

We want to know how fast the solution 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.

function subarraySum(nums, k) {
  const map = new Map();
  map.set(0, 1);
  let count = 0, sum = 0;
  for (let num of nums) {
    sum += num;
    if (map.has(sum - k)) count += map.get(sum - k);
    map.set(sum, (map.get(sum) || 0) + 1);
  }
  return count;
}
    

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

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 new element adds a fixed amount of work: updating sums and checking the map.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The work grows directly with the number of elements, so doubling input doubles work.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows in a straight line with the input size.

Common Mistake

[X] Wrong: "Because there is a map inside the loop, the time is O(n²)."

[OK] Correct: Map lookups and inserts are fast (constant time on average), so they do not multiply the loop work.

Interview Connect

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

Self-Check

"What if we used a nested loop to check all subarrays instead of a map? 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 reverse the array for easier traversal

B. To sort the array elements before processing

C. To store the original array elements as keys

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

Solution

1. Step 1: Understand the problem goal

   The problem requires finding subarrays whose sums equal a target value k.

2. Step 2: Role of hash map in solution

   A hash map stores cumulative sums and their counts to quickly check 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 D

4. Quick Check:

   Hash map stores sums = D [OK]

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

Common Mistakes:

• Thinking hash map sorts elements
• Using hash map to store array elements directly
• Ignoring cumulative sums concept

2. Which of the following is the correct syntax to initialize a JavaScript Map to store cumulative sums in the Subarray Sum Equals K problem?

easy

A. const map = new Map();

B. const map = Map();

C. const map = {};

D. const map = new map();

Solution

1. Step 1: Identify correct Map initialization syntax

   In JavaScript, a Map is created using new Map() constructor.

2. Step 2: Check options for correct syntax

   const map = {}; uses object literal {} which is not a Map. const map = Map();: Map() misses new. const map = new Map();: new Map() is correct. const map = new map();: new map() uses invalid lowercase constructor.

3. Final Answer:

   const map = new Map(); -> Option A

4. Quick Check:

   Map initialization = new Map() [OK]

Hint: Use 'new Map()' to create a Map in JavaScript [OK]

Common Mistakes:

• Omitting 'new' keyword
• Using object literal instead of Map
• Incorrect capitalization of Map

3. What will be the output of the following code snippet?

function subarraySum(nums, k) {
  let count = 0, sum = 0;
  const map = new Map();
  map.set(0, 1);
  for (let num of nums) {
    sum += num;
    if (map.has(sum - k)) {
      count += map.get(sum - k);
    }
    map.set(sum, (map.get(sum) || 0) + 1);
  }
  return count;
}

console.log(subarraySum([1, 2, 3], 3));

medium

A. 3

B. 1

C. 2

D. 0

Solution

1. Step 1: Trace cumulative sums and map updates

   nums = [1,2,3], k=3
   sum=0 initially, map={0:1}
   Iteration 1: sum=1, sum-k= -2 (not in map), map={0:1,1:1}
   Iteration 2: sum=3, sum-k=0 (in map with count 1), count=1, map={0:1,1:1,3:1}
   Iteration 3: sum=6, sum-k=3 (in map with count 1), count=2, map={0:1,1:1,3:1,6:1}

2. Step 2: Calculate final count

   Count of subarrays summing to 3 is 2: [1,2] and [3].

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Subarrays with sum 3 = 2 [OK]

Hint: Track sums and counts in map to find subarrays fast [OK]

Common Mistakes:

• Not initializing map with (0,1)
• Forgetting to add counts from map
• Incorrect sum-k calculation

4. Identify the bug in the following code for Subarray Sum Equals K and choose the correct fix.

function subarraySum(nums, k) {
  let count = 0, sum = 0;
  const map = new Map();
  for (let num of nums) {
    sum += num;
    if (map.has(sum - k)) {
      count += map.get(sum - k);
    }
    map.set(sum, (map.get(sum) || 0) + 1);
  }
  return count;
}

medium

A. Change map.set to map.add inside loop

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

C. Remove the if condition checking map.has(sum - k)

D. Initialize count to 1 instead of 0

Solution

1. Step 1: Identify missing initialization

   The map must start with sum 0 having count 1 to handle subarrays starting at index 0.

2. Step 2: Fix by adding map.set(0, 1)

   Adding map.set(0, 1) before the loop ensures correct counting of subarrays.

3. Final Answer:

   Initialize map with map.set(0, 1) before loop -> Option B

4. Quick Check:

   Start map with (0,1) fixes bug [OK]

Hint: Always initialize map with (0,1) before loop [OK]

Common Mistakes:

• Not initializing map with (0,1)
• Using map.add instead of map.set
• Removing essential if condition

5. Given the 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. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Calculate cumulative sums and track counts

   Initialize map with {0:1}, sum=0, count=0
   3: sum=3, sum-k=-4 (not), map={0:1,3:1}
   4: sum=7, 0 (1), count=1, map+={7:1}
   7: sum=14, 7 (1), count=2, map+={14:1}
   2: sum=16, 9 (not), map+={16:1}
   -3: sum=13, 6 (not), map+={13:1}
   1: sum=14, 7 (1), count=3, map 14:2
   4: sum=18, 11 (not), map+={18:1}
   2: sum=20, 13 (1), count=4, map+={20:1}

2. Step 2: Identify all subarrays summing to k

   Subarrays: [3,4], [7], [7,2,-3,1], [1,4,2]. Total count=4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Count subarrays with sum 7 = 4 [OK]

Hint: Count repeated sums in map for total subarrays [OK]

Common Mistakes:

• Ignoring repeated cumulative sums
• Not initializing map with (0,1)
• Miscounting subarrays overlapping