Count Subarrays with Given Sum

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.

#include <stdio.h>
#include <stdlib.h>

int countSubarraysWithSum(int* arr, int n, int k) {
    int* prefixCount = calloc(10000, sizeof(int)); // simplistic large array
    int currSum = 0, count = 0;
    for (int i = 0; i < n; i++) {
        currSum += arr[i];
        if (currSum == k) count++;
        if (prefixCount[currSum - k + 5000]) count += prefixCount[currSum - k + 5000];
        prefixCount[currSum + 5000]++;
    }
    free(prefixCount);
    return count;
}

int main() {
    int arr[] = {1, 1, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    printf("Count of Subarrays: %d\n", countSubarraysWithSum(arr, n, k));
    return 0;
}

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int countSubarraysWithSum(vector<int>& arr, int k) {
    unordered_map<int, int> prefixCount;
    int currSum = 0, count = 0;
    for (int num : arr) {
        currSum += num;
        if (currSum == k) count++;
        if (prefixCount.find(currSum - k) != prefixCount.end()) count += prefixCount[currSum - k];
        prefixCount[currSum]++;
    }
    return count;
}

int main() {
    vector<int> arr = {1, 1, 1};
    int k = 2;
    cout << "Count of Subarrays: " << countSubarraysWithSum(arr, k) << endl;
    return 0;
}

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

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

import java.util.*;

public class CountSubarraysWithSum {
    public static int countSubarrays(int[] arr, int k) {
        Map<Integer, Integer> prefixCount = new HashMap<>();
        int currSum = 0, count = 0;
        for (int num : arr) {
            currSum += num;
            if (currSum == k) count++;
            if (prefixCount.containsKey(currSum - k)) count += prefixCount.get(currSum - k);
            prefixCount.put(currSum, prefixCount.getOrDefault(currSum, 0) + 1);
        }
        return count;
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 1};
        int k = 2;
        System.out.println("Count of Subarrays: " + countSubarrays(arr, k));
    }
}

function countSubarraysWithSum(arr, k) {
    let prefixCount = new Map();
    let currSum = 0;
    let count = 0;
    for (let num of arr) {
        currSum += num;
        if (currSum === k) count++;
        if (prefixCount.has(currSum - k)) count += prefixCount.get(currSum - k);
        prefixCount.set(currSum, (prefixCount.get(currSum) || 0) + 1);
    }
    return count;
}

const arr = [1, 1, 1];
const k = 2;
console.log('Count of Subarrays:', countSubarraysWithSum(arr, k));

package main

import (
    "fmt"
)

func countSubarraysWithSum(arr []int, k int) int {
    prefixCount := make(map[int]int)
    currSum, count := 0, 0
    for _, num := range arr {
        currSum += num
        if currSum == k {
            count++
        }
        if val, ok := prefixCount[currSum-k]; ok {
            count += val
        }
        prefixCount[currSum]++
    }
    return count
}

func main() {
    arr := []int{1, 1, 1}
    k := 2
    fmt.Println("Count of Subarrays:", countSubarraysWithSum(arr, k))
}

use std::collections::HashMap;

fn count_subarrays_with_sum(arr: &[i32], k: i32) -> i32 {
    let mut prefix_count = HashMap::new();
    let mut curr_sum = 0;
    let mut count = 0;

    for &num in arr {
        curr_sum += num;
        if curr_sum == k {
            count += 1;
        }
        if let Some(&val) = prefix_count.get(&(curr_sum - k)) {
            count += val;
        }
        *prefix_count.entry(curr_sum).or_insert(0) += 1;
    }
    count
}

fn main() {
    let arr = vec![1, 1, 1];
    let k = 2;
    println!("Count of Subarrays: {}", count_subarrays_with_sum(&arr, k));
}

fun countSubarraysWithSum(arr: IntArray, k: Int): Int {
    val prefixCount = mutableMapOf<Int, Int>()
    var currSum = 0
    var count = 0
    for (num in arr) {
        currSum += num
        if (currSum == k) count++
        count += prefixCount.getOrDefault(currSum - k, 0)
        prefixCount[currSum] = prefixCount.getOrDefault(currSum, 0) + 1
    }
    return count
}

fun main() {
    val arr = intArrayOf(1, 1, 1)
    val k = 2
    println("Count of Subarrays: ${countSubarraysWithSum(arr, k)}")
}

import Foundation

func countSubarraysWithSum(_ arr: [Int], _ k: Int) -> Int {
    var prefixCount = [Int: Int]()
    var currSum = 0
    var count = 0
    for num in arr {
        currSum += num
        if currSum == k {
            count += 1
        }
        if let val = prefixCount[currSum - k] {
            count += val
        }
        prefixCount[currSum, default: 0] += 1
    }
    return count
}

let arr = [1, 1, 1]
let k = 2
print("Count of Subarrays: \(countSubarraysWithSum(arr, k))")

function countSubarraysWithSum(arr: number[], k: number): number {
    const prefixCount = new Map<number, number>();
    let currSum = 0;
    let count = 0;
    for (const num of arr) {
        currSum += num;
        if (currSum === k) count++;
        if (prefixCount.has(currSum - k)) count += prefixCount.get(currSum - k)!;
        prefixCount.set(currSum, (prefixCount.get(currSum) || 0) + 1);
    }
    return count;
}

const arr = [1, 1, 1];
const k = 2;
console.log('Count of Subarrays:', countSubarraysWithSum(arr, k));

Time complexity

Space complexity

O(n)

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.