Subarray Sum Equals K Using Hash Map in DSA Typescript - 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?

Yes→Add map[sum-k

↓

Update count

↓

Update map with current sum count

↓

Repeat for next element

↓

Return count

We keep track of cumulative sums and their counts in a map. For each element, we check if a previous sum exists that forms a subarray summing to k.

Execution Sample

DSA Typescript

function subarraySum(nums: number[], k: number): number {
  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 hash map to store cumulative sums.

Execution Table

Step	Operation	Current Num	Cumulative Sum	Check sum-k in Map	Map State	Count	Visual State
1	Initialize	-	0	Map initialized with {0:1}	{0:1}	0	count=0, sum=0, map={0:1}
2	Add num	1	1	Check 1-3=-2 in map: No	{0:1, 1:1}	0	sum=1, map updated with 1:1
3	Add num	2	3	Check 3-3=0 in map: Yes (count=1)	{0:1, 1:1, 3:1}	1	sum=3, count incremented to 1
4	Add num	-1	2	Check 2-3=-1 in map: No	{0:1, 1:1, 3:1, 2:1}	1	sum=2, map updated with 2:1
5	Add num	1	3	Check 3-3=0 in map: Yes (count=1+1=2)	{0:1, 1:1, 3:2, 2:1}	2	sum=3, count incremented to 2, map 3 count updated to 2
6	Add num	2	5	Check 5-3=2 in map: Yes (count=2+1=3)	{0:1, 1:1, 3:2, 2:1, 5:1}	3	sum=5, count incremented to 3
7	End	-	-	-	{0:1, 1:1, 3:2, 2:1, 5:1}	3	Return count=3

💡 All elements processed, final count of subarrays summing to k is 3

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
sum	0	1	3	2	3	5	5
count	0	0	1	1	2	3	3
map	{0:1}	{0:1,1:1}	{0:1,1:1,3:1}	{0:1,1:1,3:1,2:1}	{0:1,1:1,3:2,2:1}	{0:1,1:1,3:2,2:1,5:1}	{0:1,1:1,3:2,2:1,5:1}

Key Moments - 3 Insights

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

Because a subarray starting from index 0 can sum to k. The map entry {0:1} means sum 0 has occurred once, allowing detection of subarrays starting at the beginning (see step 3 in execution_table).

Why do we check if (sum - k) exists in the map?

Because if sum - k was seen before, the subarray between that previous index and current index sums to k. This is shown in steps 3, 5, and 6 where count increments when sum-k is found.

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

We update after checking to avoid counting the current prefix sum before it is used for subarray detection. This order ensures correct counting as shown in the map states in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the count value after processing the current number?

A 0

B 1

C 2

D 3

💡 Hint

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

At which step does the cumulative sum first equal 3?

A Step 3

B Step 2

C Step 5

D Step 6

💡 Hint

Look at the 'Cumulative Sum' column in execution_table for the first occurrence of 3.

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_moments explanation about why {0:1} is needed and check step 3 count in execution_table.

Concept Snapshot

Subarray Sum Equals K Using Hash Map:
- Use a map to store cumulative sum frequencies.
- Initialize map with {0:1} to handle subarrays from start.
- For each element, update sum and check if (sum-k) exists in map.
- Increment count by map[sum-k] if found.
- Update map with current sum count.
- Return total count of subarrays summing to k.

Full Transcript

This concept uses a hash map to count how many continuous subarrays sum to a target k. We keep a running total called cumulative sum as we move through the array. The map stores how many times each cumulative sum has appeared. Initially, map has {0:1} to count subarrays starting at index 0. For each number, we add it to sum, then check if sum-k exists in the map. If yes, it means a subarray summing to k ends here, so we add the count from the map to our total count. Then we update the map with the current sum. After processing all elements, the count is the total number of subarrays that sum to k. The execution table shows step-by-step how sum, count, and map change. Key moments clarify why map starts with {0:1}, why we check sum-k, and why map updates happen after counting. The visual quiz tests understanding of these steps.

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 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 seen so far and their counts, enabling quick checks if a subarray sum equals k.

3. Final Answer:

   To store cumulative sums and their frequencies for quick lookup -> Option A

4. Quick Check:

   Hash map stores sums = quick lookup [OK]

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

Common Mistakes:

• Thinking hash map stores array elements as keys
• Assuming sorting is needed
• Using hash map to reverse array

2. Which of the following TypeScript code snippets correctly initializes the hash map for the Subarray Sum Equals K problem?

easy

A. const map = new Map(); map.set(0, 1);

B. const map = new Map(); map.set('0', '1');

C. const map = new Map(); map.set(0, []);

D. const map = new Map(); map[0] = 1;

Solution

1. Step 1: Identify correct Map initialization

   We need a map from number to number to store cumulative sums and their counts.

2. Step 2: Check initialization correctness

   const map = new Map(); map.set(0, 1); correctly creates a Map and sets sum 0 count to 1, which is standard for this problem.

3. Final Answer:

   const map = new Map(); map.set(0, 1); -> Option A

4. Quick Check:

   Map with 0->1 set = correct init [OK]

Hint: Use Map and set(0,1) to start [OK]

Common Mistakes:

• Using string keys instead of number keys
• Initializing map with arrays as values
• Using object syntax instead of Map methods

3. What is the output of the following TypeScript code snippet?

function subarraySum(nums: number[], k: number): number {
  const map = new Map();
  map.set(0, 1);
  let sum = 0, count = 0;
  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;
}

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

medium

A. 0

B. 1

C. 3

D. 2

Solution

1. Step 1: Trace cumulative sums and map updates

   nums = [1,2,3], k=3 - sum=1, map has (1-3)=-2? No, map updated with sum=1 count=1 - sum=3, map has (3-3)=0? Yes, count += map.get(0)=1, map updated sum=3 count=1 - sum=6, map has (6-3)=3? Yes, count += map.get(3)=1, map updated sum=6 count=1 Total count=2

2. Step 2: Confirm final count returned

   Function returns 2, meaning two subarrays sum to 3: [1,2] and [3].

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Subarrays [1,2] and [3] sum to 3 = 2 [OK]

Hint: Count increments when (sum - k) found in map [OK]

Common Mistakes:

• Counting only single elements equal to k
• Not updating map counts correctly
• Ignoring multiple subarrays with same sum

4. Identify the bug in this TypeScript code for Subarray Sum Equals K and select the fix:

function subarraySum(nums: number[], k: number): number {
  const map = new Map();
  let sum = 0, count = 0;
  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;
}

medium

A. Change map to an object instead of Map

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

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

D. Initialize sum and count to 1 instead of 0

Solution

1. Step 1: Identify missing initialization

   The map must start with sum 0 count 1 to count 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 that start from the beginning.

3. Final Answer:

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

4. Quick Check:

   map.set(0,1) needed for correct count [OK]

Hint: Always set map(0) = 1 before loop [OK]

Common Mistakes:

• Forgetting to initialize map with 0 sum
• Removing necessary condition checks
• Changing variable initial values incorrectly

5. Given the array nums = [3, 4, 7, 2, -3, 1, 4, 2] and k = 7, how many subarrays sum to k using the hash map approach?

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}, no (3-7)=-4 - sum=7, map has (7-7)=0, count=1 - sum=14, map has (14-7)=7, count=1+1=2 - sum=16, map has (16-7)=9 no - sum=13, map has (13-7)=6 no - sum=14, map has (14-7)=7, count=2+1=3 - sum=18, map has (18-7)=11 no - sum=20, map has (20-7)=13, count=3+1=4 Total count=4 Subarrays summing to 7 are: [3,4], [7], [7,2,-3,1], [1,4,2]

2. Step 2: Confirm final count

   After full iteration, total subarrays summing to 7 are 4.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Count subarrays with sum k = 4 [OK]

Hint: Track cumulative sums and count matches for (sum - k) [OK]

Common Mistakes:

• Missing negative numbers affecting sums
• Not counting overlapping subarrays
• Ignoring multiple occurrences of same sum