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

Overview - Subarray Sum Equals K Using Hash Map

What is it?

This topic teaches how to find the number of continuous parts (subarrays) in a list of numbers that add up exactly to a target number k. We use a special tool called a hash map to remember sums we have seen before, so we don't have to check every possible subarray one by one. This method helps us solve the problem faster and more efficiently.

Why it matters

Without this approach, finding subarrays that sum to k would take a long time, especially for big lists, because we would check every possible part. This would be slow and not practical for real-world problems like analyzing data streams or financial transactions. Using a hash map makes the process quick and scalable, which is important in many applications.

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 involving prefix sums, sliding windows, or advanced hashing techniques.

Mental Model

Core Idea

Keep track of sums of numbers seen so far and use a hash map to quickly find if a previous sum allows a subarray to sum to k.

Think of it like...

Imagine walking along a path and counting your steps. If you remember where you were after a certain number of steps, you can quickly tell how many steps you took between two points without counting again.

Array: [1, 2, 3, 4]
Prefix sums: 0 -> 1 -> 3 -> 6 -> 10
Hash Map stores sums seen so far:
{0:1, 1:1, 3:1, 6:1, 10:1}
To find subarray sum k=3, check if (current_sum - k) exists in map.

Build-Up - 6 Steps

1

Foundation

Understanding Subarrays and Their 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 calculate its sum.

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

2

Foundation

Introduction to Prefix Sums

Concept: Use prefix sums to quickly find sums of subarrays.

A prefix sum at position i is the sum of all elements from the start up to i. For example, for [1, 2, 3], prefix sums are [0, 1, 3, 6]. To find sum of subarray from i to j, subtract prefixSum[i] from prefixSum[j+1].

Result

You can find any subarray sum in constant time after computing prefix sums.

Prefix sums reduce repeated addition and speed up sum calculations.

3

Intermediate

Using Hash Map to Store 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 subarrays summing to k efficiently.

We keep a hash map where keys are prefix sums and values are how many times they appear. For each new prefix sum, we check if (current prefix sum - k) exists in the map. If yes, it means a subarray summing to k ends here.

Result

We can count subarrays summing to k in one pass through the array.

Using a hash map with prefix sums lets us find matching sums instantly without checking all subarrays.

4

Intermediate

Implementing the Algorithm in TypeScript

🤔Before reading on: do you think the algorithm needs to update the hash map before or after checking for subarrays? Commit to your answer.

Concept: Write code that uses prefix sums and a hash map to count subarrays summing to k.

Initialize a hash map with {0:1} to handle subarrays starting at index 0. Loop through the array, update prefix sum, check if (prefixSum - k) is in map, add count to result, then update map with current prefix sum count.

Result

The code returns the total count of subarrays summing to k.

The order of updating the hash map and checking is crucial to count all valid subarrays correctly.

5

Advanced

Handling Negative Numbers and Zeroes

🤔Before reading on: do you think negative numbers break the hash map approach? Commit to yes or no.

Concept: The hash map method works even with negative numbers and zeroes in the array.

Because prefix sums can increase or decrease, the hash map tracks all sums seen so far. Negative numbers do not affect correctness, unlike sliding window methods which fail with negatives.

Result

The algorithm correctly counts subarrays summing to k regardless of negative or zero values.

Understanding that prefix sums and hash maps handle negatives is key to applying this method broadly.

6

Expert

Optimizing Space and Time Complexity

🤔Before reading on: do you think this algorithm can be improved beyond O(n) time? Commit to yes or no.

Concept: The algorithm runs in O(n) time and O(n) space, which is optimal for this problem.

Each element is processed once, and hash map lookups are O(1) on average. Space is used to store prefix sums counts. Attempts to reduce space usually increase time or complexity.

Result

This approach is the best known for counting subarrays summing to k efficiently.

Knowing the algorithm's optimality helps focus on correctness and practical use rather than unnecessary optimization.

Under the Hood

The algorithm uses prefix sums to transform the problem of finding subarrays summing to k into finding pairs of prefix sums where their difference is k. The hash map stores counts of prefix sums encountered so far. When processing a new prefix sum, the algorithm checks if a prefix sum equal to current_sum - k exists, indicating a subarray summing to k ends at the current index. This avoids nested loops by using constant-time hash map lookups.

Why designed this way?

The design leverages prefix sums to avoid repeated summation and uses a hash map for quick lookups, reducing time complexity from O(n²) to O(n). Alternatives like brute force were too slow. Sliding window methods fail with negative numbers, so this approach balances speed and correctness.

Array: [a0, a1, a2, ..., an]
Prefix sums: S0=0
S1 = a0
S2 = a0 + a1
...
Sn = a0 + a1 + ... + an-1

Hash Map stores counts of S_i
For each S_j, check if (S_j - k) in map
If yes, add map[S_j - k] to result
Update map[S_j] += 1

Flow:
Start -> Compute S_j -> Check map -> Update result -> Update map -> Next element

Myth Busters - 3 Common Misconceptions

Quick: Do you think sliding window works for arrays with negative numbers? Commit yes or no.

Common Belief: Sliding window technique can always find subarrays summing to k, even with negative numbers.

Reality: Sliding window only works correctly for non-negative numbers because negative numbers can shrink the window unpredictably.

Why it matters: Using sliding window with negatives leads to incorrect results or infinite loops, causing bugs in real applications.

Quick: Do you think prefix sums alone solve the problem without a hash map? Commit yes or no.

Common Belief: Calculating prefix sums is enough to find subarrays summing to k without extra data structures.

Reality: Prefix sums alone don't tell which subarrays sum to k; the hash map is needed to find matching prefix sums efficiently.

Why it matters: Without the hash map, you would still need nested loops, losing the efficiency gain.

Quick: Do you think the hash map stores only unique prefix sums? Commit yes or no.

Common Belief: The hash map stores only unique prefix sums once.

Reality: The hash map stores counts of how many times each prefix sum appears, not just unique keys.

Why it matters: Ignoring counts causes undercounting subarrays, leading to wrong answers.

Expert Zone

1

The hash map must be initialized with {0:1} to count subarrays starting at index 0 correctly.

2

Counting prefix sums frequency allows handling multiple overlapping subarrays ending at the same index.

3

The approach works for any integer array, including those with large positive and negative values, without modification.

When NOT to use

This method is not suitable if you need to find the actual subarrays, only their count. For that, extra bookkeeping or different algorithms are needed. Also, if the array is extremely large and memory is limited, storing prefix sums in a hash map may be costly; alternative streaming or approximate methods might be preferred.

Production Patterns

In real systems, this algorithm is used in analytics to detect patterns in time series data, such as detecting fraud by finding sequences of transactions summing to suspicious amounts. It is also used in competitive programming and coding interviews as a standard approach to subarray sum problems.

Connections

Prefix Sum Array

Builds-on

Understanding prefix sums is essential because the hash map method relies on prefix sums to transform the problem into a difference lookup.

Sliding Window Technique

Contrasts with

Knowing when sliding window fails (with negatives) helps appreciate why the hash map approach is necessary and more general.

Financial Ledger Balancing

Analogous pattern

Tracking cumulative balances and detecting when a certain net change occurs is similar to prefix sums and subarray sums, showing how this algorithmic idea applies in finance.

Common Pitfalls

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

Wrong approach:

const map = new Map(); // empty map
// rest of code without map.set(0,1)

Correct approach:

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

Root cause:

Missing this initialization causes subarrays starting at index 0 to be missed in the count.

#2 Updating the hash map before checking for subarrays.

Wrong approach:

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

Correct approach:

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

Root cause:

Updating before checking causes counting subarrays that include the current prefix sum incorrectly, leading to overcounting.

#3 Using sliding window approach on arrays with negative numbers.

Wrong approach:

let start = 0, sum = 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 prefix sums and hash map method instead, as sliding window fails with negatives.

Root cause:

Sliding window assumes sums only increase when expanding window, which is false with negative numbers.

Key Takeaways

Subarray sum equals k problem can be solved efficiently using prefix sums combined with a hash map to track sums seen so far.

The hash map stores counts of prefix sums, allowing constant-time checks for subarrays ending at the current index that sum to k.

This method works correctly even with negative numbers and zeroes, unlike sliding window techniques.

Proper initialization and order of operations in updating the hash map are crucial to avoid counting errors.

The algorithm runs in linear time and space, making it optimal for large input arrays.

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