Count Subarrays with Given Sum

Algorithm Steps

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

Count Subarrays with Sum Equal to K using Prefix Sum and Hash Map Code

Python

JavaScript

Java

C++

from collections import defaultdict

def count_subarrays_with_sum(arr, k):
    prefix_count = defaultdict(int)
    curr_sum = 0
    count = 0

    for num in arr:
        curr_sum += num
        if curr_sum == k:
            count += 1
        if (curr_sum - k) in prefix_count:
            count += prefix_count[curr_sum - k]
        prefix_count[curr_sum] += 1

    return count

# Sample Input
arr = [1, 1, 1]
k = 2
print("Count of Subarrays:", count_subarrays_with_sum(arr, k))

Count Subarrays with Given Sum - Optimal Approach

Algorithm Steps

Count Subarrays with Sum Equal to K using Prefix Sum and Hash Map Code