Subarray Sum Equals K Using Hash Map in DSA Typescript - Time & Space Complexity

Time Complexity: Subarray Sum Equals K Using Hash Map

O(n)

Understanding Time Complexity

We want to understand how fast the algorithm finds subarrays that add up to a target sum.

How does the time needed grow as the input array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function subarraySum(nums: number[], k: number): number {
  const map = new Map();
  map.set(0, 1);
  let count = 0, sum = 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;
}
    

This code counts how many continuous parts of the array add up exactly to k using a hash map.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: One loop through the array, updating sums and checking the map.
• How many times: Exactly once for each element in the array (n times).

How Execution Grows With Input

Each new number adds a fixed amount of work: updating sum, checking map, and updating map.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The work grows directly with the size of the input array.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the number of elements.

Common Mistake

[X] Wrong: "Because there is a nested check inside the loop, the time is O(n²)."

[OK] Correct: The map lookups and updates are fast (amortized constant time), so they don't multiply the loop work.

Interview Connect

Understanding this pattern helps you solve many problems where you track sums or counts efficiently.

Self-Check

"What if we used a list instead of a hash map to store sums? How would the time complexity change?"

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