Subarray Sum Equals K Using Hash Map in DSA Javascript

Mental Model

We keep track of sums of numbers from the start to each position and use a map to find if a previous sum allows a subarray to add up to k.

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

Array: [1] -> [2] -> [3] -> [4] -> [5]
Prefix sums: 0 -> 1 -> 3 -> 6 -> 10 -> 15
HashMap stores sums seen so far with their counts.

Dry Run Walkthrough

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

Goal: Find how many continuous subarrays sum to 3

Step 1: Initialize sum = 0, map = {0:1}, count = 0

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

Why: Start with sum 0 to handle subarrays starting at index 0

Step 2: Add first element (1) to sum: sum=1

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

Why: Update running sum to include current element

Step 3: Check if sum-k=1-3=-2 in map: no

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

Why: No previous prefix sum to form subarray summing to k yet

Step 4: Add sum=1 to map: map={0:1,1:1}

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

Why: Record current sum for future subarray checks

Step 5: Add second element (2) to sum: sum=3

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

Why: Update running sum with next element

Step 6: Check if sum-k=3-3=0 in map: yes, count += map[0]=1

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

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

Step 7: Add sum=3 to map: map={0:1,1:1,3:1}

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

Why: Record current sum for future subarray checks

Step 8: Add third element (3) to sum: sum=6

sum=6, map={0:1,1:1,3:1}, count=1

Why: Update running sum with next element

Step 9: Check if sum-k=6-3=3 in map: yes, count += map[3]=1

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

Why: Found subarray [3] summing to k

Step 10: Add sum=6 to map: map={0:1,1:1,3:1,6:1}

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

Why: Record current sum for future subarray checks

Result:

Final count = 2
Subarrays: [1,2], [3]

Annotated Code

DSA Javascript

class SubarraySum {
  static subarraySum(nums, k) {
    let count = 0;
    let sum = 0;
    const map = new Map();
    map.set(0, 1); // sum 0 occurs once

    for (let num of nums) {
      sum += num; // add current number to running sum
      if (map.has(sum - k)) {
        count += map.get(sum - k); // add count of previous sums that allow subarray sum k
      }
      map.set(sum, (map.get(sum) || 0) + 1); // record current sum count
    }

    return count;
  }
}

// Driver code
const nums = [1, 2, 3];
const k = 3;
console.log(SubarraySum.subarraySum(nums, k));

map.set(0, 1); // sum 0 occurs once

Initialize map with sum 0 to handle subarrays starting at index 0

sum += num; // add current number to running sum

Update running sum with current element

if (map.has(sum - k)) { count += map.get(sum - k); }

Check if a previous prefix sum allows a subarray summing to k

map.set(sum, (map.get(sum) || 0) + 1);

Record current sum count for future 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 the worst case all prefix sums are unique and stored in the map

vs Alternative: Compared to a naive O(n^2) approach checking all subarrays, this method is much faster by using prefix sums and a map

Edge Cases

empty array

returns 0 since no subarrays exist

DSA Javascript

map.set(0, 1); // sum 0 occurs once

array with all zeros and k=0

counts all subarrays of zeros correctly

DSA Javascript

count += map.get(sum - k);

no subarray sums to k

returns 0 as count

DSA Javascript

if (map.has(sum - k)) { count += map.get(sum - k); }

When to Use This Pattern

When asked to find the number of continuous subarrays summing to a target, use prefix sums with a hash map to track sums and counts efficiently.

Common Mistakes

Mistake: Not initializing the map with sum 0 count as 1
Fix: Add map.set(0, 1) before the loop to handle subarrays starting at index 0

Mistake: Updating count before checking map for sum-k
Fix: Check map for sum-k before updating map with current sum

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 the difference between two prefix sums equals the sum of the subarray between them.

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