Subarray Sum Equals K Using Hash Map in DSA Javascript - Deep Dive

Overview - Subarray Sum Equals K Using Hash Map

What is it?

Subarray Sum Equals K is a problem where we find how many continuous parts of an array add up exactly to a number k. Using a hash map helps us track sums we've seen before to quickly find these parts without checking every possibility. This method makes the search faster and more efficient. It is a common problem in coding interviews and real-world data analysis.

Why it matters

Without this approach, finding subarrays that sum to k would take a long time, especially for big arrays, because you'd check every possible part. This would slow down programs and make them less useful for real-time data. Using a hash map speeds up the process, saving time and computing power, which is important in apps like finance, gaming, or data monitoring.

Where it fits

Before learning this, you should understand arrays, loops, and basic hash maps (or dictionaries). After this, you can explore more complex problems like longest subarray sums, sliding window techniques, or prefix sums in different contexts.

Mental Model

Core Idea

By remembering sums of parts of the array as we go, we can quickly find if a subarray sums to k by checking if a previous sum matches the needed value.

Think of it like...

Imagine walking along a path and counting your steps. If you want to know if you walked exactly k steps between two points, you just check if the difference between your current step count and a previous step count is k.

Array: [1, 2, 3, 4]
Prefix sums: 0 -> 1 -> 3 -> 6 -> 10

We look for pairs where current_sum - previous_sum = k

0 ──> 1 ──> 3 ──> 6 ──> 10
       ↑       ↑       ↑
      sum=1   sum=3   sum=6

If current_sum - k exists in map, subarray found.

Build-Up - 6 Steps

1

Foundation

Understanding Subarrays and Sums

Concept: Learn what a subarray is and how to calculate its sum.

A subarray is a continuous part of an array. For example, in [1, 2, 3], subarrays include [1], [2], [3], [1, 2], [2, 3], and [1, 2, 3]. To find the sum of a subarray, add all its elements. For example, sum of [2, 3] is 5.

Result

You can identify any continuous part of an array and find its total sum.

Understanding subarrays and their sums is the foundation for solving problems about sums within arrays.

2

Foundation

Brute Force Approach to Find Subarray Sum

Concept: Try every possible subarray and check if its sum equals k.

Use two loops: the outer loop picks a start index, the inner loop picks an end index. For each pair, sum the elements between start and end. If sum equals k, count it. Example: array = [1, 2, 3], k = 3 Subarrays: [1], [1,2], [1,2,3], [2], [2,3], [3] Check sums: [1]=1, [1,2]=3 (count), [1,2,3]=6, [2]=2, [2,3]=5, [3]=3 (count) Total count = 2

Result

You find all subarrays summing to k but with slow performance for large arrays.

Brute force works but is inefficient; it helps understand the problem but is not practical for big data.

3

Intermediate

Prefix Sum Concept for Faster Calculation

Concept: Use prefix sums to quickly find sums of subarrays without repeated addition.

Prefix sum at index i is the sum of all elements from start to i. Example: array = [1, 2, 3] Prefix sums: [0, 1, 3, 6] Sum of subarray from i to j = prefixSum[j+1] - prefixSum[i] This lets you find subarray sums in constant time after prefix sums are computed.

Result

You can calculate any subarray sum quickly using prefix sums.

Prefix sums reduce repeated work, making sum calculations faster and enabling more efficient algorithms.

4

Intermediate

Using Hash Map to Track Prefix Sums

🤔Before reading on: do you think storing prefix sums in a hash map can help find subarrays summing to k faster? Commit to yes or no.

Concept: Store counts of prefix sums in a hash map to find how many subarrays sum to k in one pass.

As you move through the array, keep track of the current prefix sum. Check if (current prefix sum - k) exists in the hash map. If yes, it means a subarray ending here sums to k. Update the hash map with the current prefix sum count. Example: array = [1, 2, 3], k = 3 prefix sums: 0 (start), 1, 3, 6 At prefix sum 3, check 3 - 3 = 0 in map? Yes, count += 1 At prefix sum 6, check 6 - 3 = 3 in map? Yes, count += 1 Total count = 2

Result

You find the count of subarrays summing to k in one pass with O(n) time.

Using a hash map with prefix sums turns a slow problem into a fast one by remembering sums seen before.

5

Advanced

Implementing the Hash Map Solution in JavaScript

🤔Before reading on: do you think the hash map should store prefix sums as keys and their counts as values? Commit to yes or no.

Concept: Write code that uses a hash map to count subarrays summing to k efficiently.

function subarraySum(nums, k) { const map = new Map(); map.set(0, 1); // prefix sum 0 occurs once let count = 0; let prefixSum = 0; for (const num of nums) { prefixSum += num; if (map.has(prefixSum - k)) { count += map.get(prefixSum - k); } map.set(prefixSum, (map.get(prefixSum) || 0) + 1); } return count; } // Example usage: // subarraySum([1, 2, 3], 3) returns 2

Result

The function returns the number of subarrays summing to k quickly and correctly.

Knowing how to implement the hash map approach in code solidifies understanding and prepares for real coding tasks.

6

Expert

Handling Negative Numbers and Edge Cases

🤔Before reading on: do you think this hash map method works correctly even if the array has negative numbers? Commit to yes or no.

Concept: The hash map approach works with negative numbers and zeros, unlike some sliding window methods.

Because we track prefix sums and their counts, negative numbers do not break the logic. Example: nums = [1, -1, 0], k = 0 prefix sums: 0, 1, 0, 0 Map updates and checks correctly count subarrays summing to 0. This method is robust and handles all integer values. Edge cases include empty arrays, k = 0, and arrays with repeated numbers.

Result

The method reliably counts subarrays summing to k in all integer arrays.

Understanding that prefix sums and hash maps handle negatives and zeros prevents incorrect assumptions and broadens applicability.

Under the Hood

The algorithm keeps a running total of the array elements (prefix sum). It uses a hash map to store how many times each prefix sum has appeared. When the current prefix sum minus k exists in the map, it means a subarray summing to k ends at the current index. This works because the difference between two prefix sums equals the sum of the elements between those indices.

Why designed this way?

This approach was designed to reduce the time complexity from O(n²) to O(n) by avoiding repeated summation. Using a hash map for prefix sums leverages constant-time lookups to find matching sums quickly. Alternatives like nested loops or sliding windows either are slower or don't handle negative numbers well, making this method both efficient and versatile.

Start
  │
  ▼
[Initialize map with {0:1}]
  │
  ▼
[For each number in array]
  │
  ▼
[Update prefix sum]
  │
  ▼
[Check if (prefixSum - k) in map]
  │       ┌─────────────┐
  │       │Yes: add count│
  │       └─────────────┘
  │
  ▼
[Update map with prefixSum count]
  │
  ▼
[Repeat until end]
  │
  ▼
[Return total count]

Myth Busters - 4 Common Misconceptions

Quick: Does the hash map method only work for positive numbers? Commit to yes or no.

Common Belief: The hash map approach only works if all numbers are positive.

Reality: The method works correctly with negative, zero, and positive numbers because it relies on prefix sums and their differences, not on number signs.

Why it matters: Believing this limits the method's use and may cause learners to avoid it unnecessarily or use slower methods.

Quick: Does the hash map store subarrays themselves? Commit to yes or no.

Common Belief: The hash map stores the actual subarrays that sum to k.

Reality: The hash map only stores counts of prefix sums, not the subarrays themselves.

Why it matters: Thinking it stores subarrays can confuse learners about memory use and algorithm behavior.

Quick: Is the brute force method faster than the hash map method? Commit to yes or no.

Common Belief: Checking all subarrays one by one is faster for small arrays.

Reality: Even for small arrays, the hash map method is generally faster or equally fast because it avoids repeated summations.

Why it matters: Misunderstanding this may cause learners to waste time on inefficient solutions.

Quick: Does the hash map method find the longest subarray summing to k? Commit to yes or no.

Common Belief: This method finds the longest subarray with sum k.

Reality: It counts how many subarrays sum to k but does not find the longest one.

Why it matters: Confusing counting with finding longest subarray can lead to wrong problem-solving approaches.

Expert Zone

1

The hash map stores counts of prefix sums, allowing multiple overlapping subarrays to be counted correctly.

2

Updating the map after checking for (prefixSum - k) ensures subarrays starting at the current index are counted properly.

3

The initial map entry of {0:1} handles subarrays starting at index 0 without extra checks.

When NOT to use

Avoid this method if you need to find the actual subarrays or their indices; use two-pointer or sliding window techniques for positive numbers only. For very large data streams where memory is limited, approximate methods or segment trees might be better.

Production Patterns

Used in real-time analytics to detect patterns in data streams, in finance to find periods of specific gains or losses, and in coding interviews to test understanding of prefix sums and hash maps.

Connections

Prefix Sum Array

Builds-on

Understanding prefix sums is essential because the hash map method relies on differences between prefix sums to find subarrays.

Sliding Window Technique

Alternative approach

Sliding window works well for positive numbers but fails with negatives, highlighting why the hash map method is more general.

Financial Accounting - Running Balances

Same pattern

Tracking running balances in accounts is like prefix sums; differences between balances show transactions over periods, similar to subarray sums.

Common Pitfalls

#1 Not initializing the hash map with prefix sum 0 count.

Wrong approach:

const map = new Map(); // no initial entry

for (const num of nums) {
prefixSum += num;
if (map.has(prefixSum - k)) {
count += map.get(prefixSum - k);
}
map.set(prefixSum, (map.get(prefixSum) || 0) + 1);
}

Correct approach:

const map = new Map();
map.set(0, 1); // initialize with 0 sum count

for (const num of nums) {
prefixSum += num;
if (map.has(prefixSum - k)) {
count += map.get(prefixSum - k);
}
map.set(prefixSum, (map.get(prefixSum) || 0) + 1);
}

Root cause:

Without initializing, subarrays starting at index 0 are missed because the difference prefixSum - k equals 0 won't be found.

#2 Updating the hash map before checking for (prefixSum - k).

Wrong approach:

for (const num of nums) {
prefixSum += num;
map.set(prefixSum, (map.get(prefixSum) || 0) + 1);
if (map.has(prefixSum - k)) {
count += map.get(prefixSum - k);
}
}

Correct approach:

for (const num of nums) {
prefixSum += num;
if (map.has(prefixSum - k)) {
count += map.get(prefixSum - k);
}
map.set(prefixSum, (map.get(prefixSum) || 0) + 1);
}

Root cause:

Checking after updating counts the current prefix sum itself, causing incorrect counts for subarrays starting at the current index.

#3 Using a sliding window approach for arrays with negative numbers.

Wrong approach:

let start = 0, sum = 0, count = 0;
for (let end = 0; end < nums.length; end++) {
sum += nums[end];
while (sum > k) {
sum -= nums[start];
start++;
}
if (sum === k) count++;
}

Correct approach:

Use the hash map prefix sum method which works with negative numbers as shown in previous steps.

Root cause:

Sliding window assumes sums only increase with new elements, which fails with negative numbers causing incorrect results.

Key Takeaways

Subarray Sum Equals K problem finds how many continuous parts of an array add up to a target number k.

Using prefix sums and a hash map lets us find these subarrays efficiently in one pass with O(n) time.

The hash map stores counts of prefix sums seen so far, enabling quick checks for matching sums.

This method works with positive, negative, and zero values, making it versatile.

Proper initialization and order of operations in the hash map are crucial to get correct counts.

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