Count Subarrays with Given Sum using Prefix Sum and HashMap Optimal Solution

Given an integer array arr and a target sum k, your task is to find the total number of continuous subarrays whose elements add up to exactly k.

A subarray is a sequence of elements that appears in the same order in the array and is contiguous. The same element can be included in multiple subarrays if it appears in different positions.

This problem is common in applications involving range-based queries, financial analysis, and interval sum counting.

Step-by-Step Solution for Beginners: Count Subarrays with Sum = k

1. Understand the Problem First

We are given an array of integers and a target number k. We are asked to count how many continuous subarrays have a sum equal to k.

Let’s take an example to better understand this:

Input: nums = [1, 2, 3], k = 3  
Output: 2

Explanation: The subarrays [1, 2] and [3] both sum to 3.

2. Strategy: Prefix Sum + Hash Map

Instead of checking every possible subarray (which takes O(n²) time), we will use a smarter approach using:

• Prefix Sum: Keep track of running total as we move through the array.
• Hash Map: Store how many times each prefix sum has occurred.

3. How It Works Step by Step

Let’s say we’re at index i and the sum of elements from the beginning up to this point is prefixSum. We are looking for how many previous prefix sums satisfy:

prefixSum - k = previousPrefixSum

If such a previousPrefixSum was seen earlier, then a subarray ending at index i has a total sum of k. We can count all such prefix sums using the hash map.

4. Solve the Given Example

Input: nums = [1, 2, 3], k = 3
Let’s walk through it:

Initialize:
prefixSum = 0
count = 0
map = {0: 1}  (to handle subarrays starting from index 0)

Loop through the array:
- num = 1 → prefixSum = 1  
  → prefixSum - k = -2 → not in map  
  → add 1 to map → map = {0:1, 1:1}

- num = 2 → prefixSum = 3  
  → prefixSum - k = 0 → found in map!  
  → count += 1 (map[0]) → count = 1  
  → add 3 to map → map = {0:1, 1:1, 3:1}

- num = 3 → prefixSum = 6  
  → prefixSum - k = 3 → found in map!  
  → count += 1 (map[3]) → count = 2  
  → add 6 to map → map = {0:1, 1:1, 3:1, 6:1}

Final answer = 2

5. Edge Cases

• Empty Array: No elements means no subarrays. Output = 0.
• Negative Numbers: The prefix sum method works even if elements are negative.
• Zeros: In cases like [0, 0, 0] and k = 0, every subarray sums to 0. We count all valid ones.
• Multiple Matches: If a prefix sum appears multiple times, all such matches should be added to the count.

6. Why This Approach Works Efficiently

Instead of checking every pair of start and end points for subarrays, we maintain a running prefix sum and look up how many times prefixSum - k has occurred before. This lookup is done in constant time using a hash map.

This brings down the time complexity from O(n²) to O(n), which is very efficient even for large arrays.

1. Given an array arr and a target k.
2. Initialize a prefix sum curr_sum = 0 and a hash map prefix_count to store frequency of prefix sums.
3. Initialize count = 0.
4. Iterate through the array:
5. → Add current element to curr_sum.
6. → If curr_sum == k, increment count by 1.
7. → If curr_sum - k exists in prefix_count, add its frequency to count.
8. → Update the frequency of curr_sum in prefix_count.
9. Return the total count.

O(n)

Explanation: A hashmap is used to store the frequency of prefix sums, which can grow up to the size of the input array in the worst case.