Subarray Sum Equals K Using Hash Map in DSA Typescript - Build from Scratch

Subarray Sum Equals K Using Hash Map

📖 Scenario: You are analyzing daily sales data for a small shop. You want to find how many continuous days had sales that add up exactly to a target number.

🎯 Goal: Build a TypeScript program that counts the number of continuous subarrays whose sum equals a given target k using a hash map for efficient lookup.

📋 What You'll Learn

Create an array called sales with exact daily sales numbers

Create a variable called k for the target sum

Use a hash map (JavaScript object) to store prefix sums and their counts

Implement a loop to find the count of subarrays summing to k

Print the final count

💡 Why This Matters

🌍 Real World

Finding continuous periods where sales meet a target helps businesses analyze performance and plan promotions.

💼 Career

This technique is useful in data analysis, software development, and roles involving algorithmic problem solving.

1

Create the sales data array

Create an array called sales with these exact daily sales numbers: 1, 2, 3, 4, 2

DSA Typescript

# Your code here

Hint

Use square brackets to create an array and separate numbers with commas.

2

Set the target sum k

Create a variable called k and set it to 5 as the target sum.

DSA Typescript

const sales = [1, 2, 3, 4, 2];
# Your code here

Hint

Use const k = 5; to create the target sum variable.

3

Implement the subarray sum counting logic

Create a variable count set to 0, a variable prefixSum set to 0, and an object prefixSums initialized with {0: 1}. Then use a for loop with variable i to iterate over sales. Inside the loop, add sales[i] to prefixSum. Check if prefixSum - k exists as a key in prefixSums, and if yes, add its value to count. Finally, update prefixSums[prefixSum] by incrementing it or setting it to 1 if not present.

DSA Typescript

const sales = [1, 2, 3, 4, 2];
const k = 5;
# Your code here

Hint

Use a hash map to store counts of prefix sums. Update count when a matching prefix sum is found.

4

Print the count of subarrays summing to k

Write a console.log statement to print the variable count.

DSA Typescript

const sales = [1, 2, 3, 4, 2];
const k = 5;

let count = 0;
let prefixSum = 0;
const prefixSums: {[key: number]: number} = {0: 1};

for (let i = 0; i < sales.length; i++) {
    prefixSum += sales[i];
    if (prefixSums[prefixSum - k] !== undefined) {
        count += prefixSums[prefixSum - k];
    }
    prefixSums[prefixSum] = (prefixSums[prefixSum] || 0) + 1;
}
# Your code here

Hint

Use console.log(count); to display the final count.

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