Subarray Sum Equals K Using Hash Map in DSA Javascript - Execution Trace

Concept Flow - Subarray Sum Equals K Using Hash Map

Start with sum=0 and map={0:1}

↓

Iterate over array elements

↓

Add current element to sum

↓

Check if (sum-k) exists in map?

↓

Add map[sum-k

↓

Update map with current sum count

↓

Repeat for next element

↓

Return total count of subarrays

We keep a running sum and use a map to count how many times each sum appears. For each new sum, we check if sum-k was seen before to find subarrays that add up to k.

Execution Sample

DSA Javascript

function subarraySum(nums, k) {
  let count = 0, sum = 0;
  const map = new Map([[0, 1]]);
  for (const 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 subarrays sum to k using a running sum and a hash map.

Execution Table

Step	Operation	Current Num	Running Sum	Check sum-k in Map	Map State	Count
1	Initialize	-	0	sum-k=0-3=-3 not in map	{0:1}	0
2	Add num	1	1	1-3=-2 not in map	{0:1, 1:1}	0
3	Add num	2	3	3-3=0 in map with count=1	{0:1, 1:1, 3:1}	1
4	Add num	3	6	6-3=3 in map with count=1	{0:1, 1:1, 3:1, 6:1}	2
5	Add num	4	10	10-3=7 not in map	{0:1, 1:1, 3:1, 6:1, 10:1}	2
6	Add num	-3	7	7-3=4 not in map	{0:1, 1:1, 3:1, 6:1, 10:1, 7:1}	2
7	Add num	1	8	8-3=5 not in map	{0:1, 1:1, 3:1, 6:1, 10:1, 7:1, 8:1}	2
8	Add num	2	10	10-3=7 in map with count=1	{0:1, 1:1, 3:1, 6:1, 10:2, 7:1, 8:1}	3
9	Add num	3	13	13-3=10 in map with count=2	{0:1, 1:1, 3:1, 6:1, 10:2, 7:1, 8:1, 13:1}	5
10	End	-	-	-	-	5

💡 All elements processed, total count of subarrays with sum k=3 is 5

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	Final
sum	0	1	3	6	10	7	8	10	13	13	13
count	0	0	1	2	2	2	2	3	5	5	5
map	{0:1}	{0:1,1:1}	{0:1,1:1,3:1}	{0:1,1:1,3:1,6:1}	{0:1,1:1,3:1,6:1,10:1}	{0:1,1:1,3:1,6:1,10:1,7:1}	{0:1,1:1,3:1,6:1,10:1,7:1,8:1}	{0:1,1:1,3:1,6:1,10:2,7:1,8:1}	{0:1,1:1,3:1,6:1,10:2,7:1,8:1,13:1}	{0:1,1:1,3:1,6:1,10:2,7:1,8:1,13:1}	{0:1,1:1,3:1,6:1,10:2,7:1,8:1,13:1}

Key Moments - 3 Insights

Why do we initialize the map with {0:1} before starting?

Because a subarray starting from index 0 that sums to k should be counted. The initial sum 0 with count 1 allows detecting subarrays that start at the beginning (see step 3 where sum=3 and sum-k=0 is found in map).

Why do we check for sum-k in the map instead of just sum?

Checking sum-k helps find if there was a previous prefix sum that, when removed from current sum, equals k. This means the subarray between that previous index and current index sums to k (see steps 3,4,8,9).

Why do we update the map with the current sum after checking?

We update after checking to avoid counting the current prefix sum as a subarray itself before it exists. This ensures only previous sums are considered for subarrays (see map updates in execution_table).

Visual Quiz - 3 Questions

Look at the execution table at step 4. What is the count value after processing the number 3?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Count' column at step 4 in the execution_table.

At which step does the running sum first reach 10?

A Step 5

B Step 6

C Step 8

D Step 9

💡 Hint

Look at the 'Running Sum' column in the execution_table to find when sum equals 10 first.

If the initial map did not contain {0:1}, what would be the count after step 3?

A 2

B 1

C 0

D 3

💡 Hint

Refer to the key moment about why map starts with {0:1} and check step 3 count.

Concept Snapshot

Subarray Sum Equals K Using Hash Map:
- Use running sum to track cumulative total.
- Use a map to store counts of prefix sums.
- For each sum, check if (sum-k) exists in map to find subarrays.
- Initialize map with {0:1} to count subarrays starting at index 0.
- Update map with current sum count after checking.
- Time complexity: O(n), space: O(n).

Full Transcript

This concept uses a running sum and a hash map to find how many continuous subarrays sum to a target k. We start with sum=0 and map containing {0:1} to handle subarrays starting at the beginning. For each number, we add it to sum, then check if sum-k exists in the map. If yes, it means a subarray ending here sums to k, so we add the count from the map. Then we update the map with the current sum count. This process continues for all elements, and the final count is returned. The execution table shows each step with current number, running sum, map state, and count updates. Key moments clarify why map starts with {0:1}, why we check sum-k, and why map updates happen after checking. The visual quiz tests understanding of count updates, running sum values, and the importance of initial map state.

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