Subarray Sum Equals K Using Hash Map in DSA Typescript

Mental Model

We keep track of sums of elements from the start to each position and use a map to find if a previous sum allows a subarray to sum to k.

Analogy: Imagine walking along a path and counting steps. If you know the total steps at two points, subtracting them tells you how many steps you took between those points. The map remembers where you were before to quickly find these distances.

Array: [1, 2, 3, 4]
Prefix sums: 0 -> 1 -> 3 -> 6 -> 10
HashMap stores sums seen so far with their counts:
{0:1} initially
After first element: {0:1, 1:1}
After second: {0:1, 1:1, 3:1}
...

Dry Run Walkthrough

Input: array: [1, 2, 3], k = 3

Goal: Find how many continuous subarrays sum to 3

Step 1: Start with sum = 0 and map = {0:1} to count empty prefix

sum=0, map={0:1}

Why: We count the empty prefix to handle subarrays starting at index 0

Step 2: Add first element 1 to sum: sum=1; check if sum-k=1-3=-2 in map (no); add sum=1 to map

sum=1, map={0:1, 1:1}

Why: No subarray ending here sums to k yet; record sum for future

Step 3: Add second element 2: sum=3; check sum-k=3-3=0 in map (yes, count=1); increment result by 1; add sum=3 to map

sum=3, map={0:1, 1:1, 3:1}, result=1

Why: Found subarray [1,2] summing to k

Step 4: Add third element 3: sum=6; check sum-k=6-3=3 in map (yes, count=1); increment result by 1; add sum=6 to map

sum=6, map={0:1, 1:1, 3:1, 6:1}, result=2

Why: Found subarray [3] summing to k

Result:

Final result = 2 subarrays: [1,2] and [3]

Annotated Code

DSA Typescript

class SubarraySum {
  static subarraySum(nums: number[], k: number): number {
    let count = 0;
    let sum = 0;
    const map = new Map<number, number>();
    map.set(0, 1); // empty prefix sum count

    for (const num of nums) {
      sum += num; // add current number to running sum
      if (map.has(sum - k)) {
        count += map.get(sum - k)!; // add count of previous sums that allow subarray sum k
      }
      map.set(sum, (map.get(sum) ?? 0) + 1); // record current sum count
    }

    return count;
  }
}

// Driver code
const nums = [1, 2, 3];
const k = 3;
console.log(SubarraySum.subarraySum(nums, k));

map.set(0, 1); // empty prefix sum count

Initialize map with sum 0 count 1 to handle subarrays starting at index 0

sum += num; // add current number to running sum

Update running sum with current element

if (map.has(sum - k)) { count += map.get(sum - k)!; }

Check if a previous prefix sum exists so that subarray sum equals k

map.set(sum, (map.get(sum) ?? 0) + 1);

Record current prefix sum count for future subarray checks

Output

2

Complexity Analysis

Time: O(n) because we traverse the array once and do constant time map operations per element

Space: O(n) because in worst case all prefix sums are unique and stored in the map

vs Alternative: Naive approach is O(n^2) by checking all subarrays; this method uses prefix sums and a map to reduce to O(n)

Edge Cases

Empty array

Returns 0 since no subarrays exist

DSA Typescript

map.set(0, 1); // empty prefix sum count

Array with all zeros and k=0

Counts all subarrays of zeros correctly using map counts

DSA Typescript

count += map.get(sum - k)!;

No subarray sums to k

Returns 0 as no matching prefix sums found

DSA Typescript

if (map.has(sum - k)) { count += map.get(sum - k)!; }

When to Use This Pattern

When asked to find the count of continuous subarrays summing to a target, use prefix sums with a hash map to track sums and find matches efficiently.

Common Mistakes

Mistake: Not initializing the map with sum 0 count 1, missing subarrays starting at index 0
Fix: Add map.set(0, 1) before looping to handle empty prefix sum

Summary

Counts how many continuous subarrays sum to a target value k using prefix sums and a hash map.

Use when you need to find subarrays with a specific sum efficiently in O(n) time.

The key insight is that the difference between two prefix sums equals the sum of the subarray between them.

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