Subarray Sum Equals K Using Hash Map in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using a hash map to solve the 'Subarray Sum Equals K' problem?

We use a hash map to store the cumulative sums and their frequencies. This helps us quickly find if there is a previous cumulative sum that, when subtracted from the current sum, equals k, indicating a subarray summing to k.

beginner

In the 'Subarray Sum Equals K' problem, what does the key in the hash map represent?

The key represents a cumulative sum of elements from the start of the array up to a certain index.

intermediate

Why do we initialize the hash map with {0:1} in the 'Subarray Sum Equals K' solution?

Because a cumulative sum of 0 occurs once before starting, this allows us to count subarrays that start from index 0 and sum exactly to k.

intermediate

What is the time complexity of the 'Subarray Sum Equals K Using Hash Map' algorithm?

The time complexity is O(n), where n is the length of the array, because we traverse the array once and perform constant-time hash map operations.

intermediate

How does the algorithm handle multiple subarrays that sum to k?

The hash map stores frequencies of cumulative sums, so when the difference (current_sum - k) appears multiple times, it counts all those subarrays.

What does the hash map store in the 'Subarray Sum Equals K' problem?

A Subarray lengths

B Individual elements and their indices

C Only the sum k

D Cumulative sums and their frequencies

The hash map stores cumulative sums as keys and their frequencies as values to quickly find subarrays summing to k.

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

A To reset the cumulative sum

B To find the maximum subarray length

C To find if a subarray sums to k ending at current index

D To count negative numbers

If (current_sum - k) exists, it means a previous cumulative sum allows a subarray summing to k ending at the current index.

What initial value is set in the hash map before processing the array?

A {} (empty)

B {0:1}

C {k:1}

D {-1:0}

We initialize with {0:1} to count subarrays starting at index 0 that sum to k.

What is the overall time complexity of this algorithm?

A O(n)

B O(n^2)

C O(log n)

D O(1)

The algorithm runs in O(n) time because it processes each element once and uses constant-time hash map operations.

If the array is [1, 2, 3] and k=3, how many subarrays sum to k?

A 2

B 1

C 3

D 0

Subarrays [3] and [1, 2] both sum to 3, so the answer is 2.

Explain how the hash map helps find subarrays that sum to k in the 'Subarray Sum Equals K' problem.

Think about how subtracting sums helps identify subarrays.

Describe the steps to implement the 'Subarray Sum Equals K Using Hash Map' algorithm.

Focus on initialization, iteration, checking, counting, and updating.

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