Count Subarrays having Sum K

Last Updated : 28 Jul, 2025

Given an array arr[] of postive and negative integers, the objective is to find the number of subarrays having a sum exactly equal to a given number k.

Examples:

Input : arr[] = [10, 2, -2, -20, 10], k = -10
Output : 3
Explanation: Subarrays: arr[0...3], arr[1...4], arr[3...4] have sum equal to -10.
Input : arr[] = [9, 4, 20, 3, 10, 5], k = 33
Output : 2
Explanation: Subarrays: arr[0...2], arr[2...4] have sum equal to 33.
Input : arr[] = [1, 3, 5], k = 2
Output : 0
Explanation: No subarrays with 0 sum.

Table of Content

[Naive Approach] Using Nested Loop - O(n^2) Time and O(1) Space
[Expected Approach] Using Hash Map and Prefix Sum - O(n) Time and O(n) Space

[Naive Approach] Using Nested Loop - O(n²) Time and O(1) Space

A simple solution is to traverse all the subarrays and calculate their sum. If the sum is equal to the given number k, then increment the count of subarrays.

C++

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

int cntSubarrays(vector<int>& arr, int k) {
    
    int size = arr.size();
    
    // for maintaing the count of
    // subarrays whose sum equal to k
    int count = 0;
    for(int i = 0; i < size; i++){
        
        int currSum = 0;
        
        // subarray from i to each j -> arr[i....j]
        for(int j = i; j < size; j++){
            currSum += arr[j];
            
            // increment count if the currSum equal to k
            count += (currSum == k);
        }
    }
    
    return count;
}

int main() {
    vector<int> arr = {10, 2, -2, -20, 10};
    int k = -10;
    cout << cntSubarrays(arr, k);
    return 0;
}

#include <stdio.h>

int cntSubarrays(int arr[], int n, int k) {
    
    // for maintaining the count of
    // subarrays whose sum equal to k
    int count = 0;

    for (int i = 0; i < n; i++) {
        int currSum = 0;

        // subarray from i to each j -> arr[i....j]
        for (int j = i; j < n; j++) {
            currSum += arr[j];

            // increment count if the currSum equals k
            if (currSum == k) {
                count++;
            }
        }
    }

    return count;
}

int main() {
    int arr[] = {10, 2, -2, -20, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = -10;

    printf("%d\n", cntSubarrays(arr, n, k));
    return 0;
}

Java

class GfG {
    public static int cntSubarrays(int[] arr, int k) {
      
        // for maintaining the count of 
        // subarrays whose sum equal to k
        int count = 0;
        int n = arr.length;

        for (int i = 0; i < n; i++) {
            int currSum = 0;

            // subarray from i to each j -> arr[i....j]
            for (int j = i; j < n; j++) {
                currSum += arr[j];

                // increment count if the currSum equals k
                if (currSum == k) {
                    count++;
                }
            }
        }

        return count;
    }

    public static void main(String[] args) {
        int[] arr = {10, 2, -2, -20, 10};
        int k = -10;
        System.out.println(cntSubarrays(arr, k));
    }
}

Python

def cntSubarrays(arr, k):
    
    # for maintaining the count of 
    # subarrays whose sum equal to k
    count = 0
    n = len(arr)

    for i in range(n):
        currSum = 0

        # subarray from i to each j -> arr[i....j]
        for j in range(i, n):
            currSum += arr[j]

            # increment count if the currSum equals k
            if currSum == k:
                count += 1
                
    return count


if __name__ == "__main__":
    arr = [10, 2, -2, -20, 10]
    k = -10
    print(cntSubarrays(arr, k))

using System;

class GfG {
    public static int cntSubarrays(int[] arr, int k) {

        // for maintaining the count
        // of subarrays whose sum equal to k
        int count = 0;
        int n = arr.Length;

        for (int i = 0; i < n; i++) {
            int currSum = 0;

            // subarray from i to each j -> arr[i....j]
            for (int j = i; j < n; j++) {
                currSum += arr[j];

                // increment count if the currSum equals k
                if (currSum == k) {
                    count++;
                }
            }
        }

        return count;
    }

    static void Main() {
        int[] arr = new int[] {10, 2, -2, -20, 10};
        int k = -10;
        Console.WriteLine(cntSubarrays(arr, k));
    }
}

JavaScript

function cntSubarrays(arr, k) {
    
    // for maintaining the count of
    // subarrays whose sum equal to k
    let count = 0;
    let n = arr.length;

    for (let i = 0; i < n; i++) {
        let currSum = 0;

        // subarray from i to each j -> arr[i....j]
        for (let j = i; j < n; j++) {
            currSum += arr[j];

            // increment count if the currSum equals k
            if (currSum === k) {
                count++;
            }
        }
    }

    return count;
}

// Driver Code
let arr = [10, 2, -2, -20, 10];
let k = -10;
console.log(cntSubarrays(arr, k));

Output

[Expected Approach] Using Hash Map and Prefix Sum - O(n) Time and O(n) Space

If you take a closer look at this problem, this is mainly an extension of Subarray with given sum.

To count subarrays with sum k, we use a hash map to store the frequency of prefix sums. At each index, we calculate the current prefix sum currSum and check if (currSum - k) exists in the map. If it does, it means there are subarrays ending at the current index with sum k, and we add their count to the result. Then we update the frequency of currSum in the map.

Step By Step Implementations:

Maintain a running sum of elements from index 0 to i → currSum.
If currSum is equal to k, we’ve found a valid subarray from index 0 to i.
If there’s a prefix sum such that currSum - k exists in the map, then we’ve found subarrays ending at i with sum k.
The number of such subarrays is equal to the frequency of (currSum - k).
Record currSum in the map to help future matches.

Illustration:

C++

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

int cntSubarrays(vector<int> &arr, int k) {
  
    // unordered_map to store prefix sums frequencies
    unordered_map<int, int> prefixSums;
  
    int res = 0;
    int currSum = 0;

    for (int i = 0; i < arr.size(); i++) {
        
        // Add current element to sum so far.
        currSum += arr[i];

        // If currSum is equal to desired sum, then a new
        // subarray is found. So increase count of subarrays.
        if (currSum == k)
            res++;

        // Check if the difference exists in the prefixSums map.
        if (prefixSums.find(currSum - k) != prefixSums.end())
            res += prefixSums[currSum - k];

        // Add currSum to the set of prefix sums.
        prefixSums[currSum]++;
    }

    return res;
}

int main() {
    vector<int> arr = {10, 2, -2, -20, 10};
    int k = -10;
    cout << cntSubarrays(arr, k);
    return 0;
}

Java

import java.util.HashMap;
import java.util.Map;
class GfG {
    static int cntSubarrays(int[] arr, int k) {

        // HashMap to store prefix sums frequencies
        Map<Integer, Integer> prefixSums = new HashMap<>();
        int res = 0;
        int currSum = 0;

        for (int i = 0; i < arr.length; i++) {
            // Add current element to sum so far.
            currSum += arr[i];

            // If currSum is equal to desired sum
            // then a new subarray is found.
            if (currSum == k)
                res++;

            // Check if the difference exists in the prefixSums map.
            if (prefixSums.containsKey(currSum - k))
                res += prefixSums.get(currSum - k);

            // Add currSum to the set of prefix sums.
            prefixSums.put(currSum, prefixSums.getOrDefault(currSum, 0) + 1);
        }

        return res;
    }

    public static void main(String[] args) {
        int[] arr = {10, 2, -2, -20, 10};
        int k = -10;
        System.out.println(cntSubarrays(arr, k));
    }
}

Python

def cntSubarrays(arr, k):
  
    # Dictionary to store prefix sums frequencies
    prefixSums = {}
    res = 0
    currSum = 0

    for val in arr:
        # Add current element to sum so far
        currSum += val

        # If currSum is equal to desired sum
        # then a new subarray is found
        if currSum == k:
            res += 1

        # Check if the difference exists
        # in the prefixSums dictionary
        if currSum - k in prefixSums:
            res += prefixSums[currSum - k]

        # Add currSum to the dictionary of prefix sums
        prefixSums[currSum] = prefixSums.get(currSum, 0) + 1

    return res

if __name__ == "__main__":
    arr = [10, 2, -2, -20, 10]
    k = -10
    print(cntSubarrays(arr, k))

using System;
using System.Collections.Generic;

class GfG {
    static int cntSubarrays(int[] arr, int k) {
      
        // Dictionary to store prefix sums frequencies
        Dictionary<int, int> prefixSums = new Dictionary<int, int>();
        int res = 0;
        int currSum = 0;

        for (int i = 0; i < arr.Length; i++) {
      
            // Add current element to sum so far
            currSum += arr[i];

            // If currSum is equal to desired sum
            // then a new subarray is found
            if (currSum == k)
                res++;

            // Check if the difference exists
            // in the prefixSums dictionary
            if (prefixSums.ContainsKey(currSum - k))
                res += prefixSums[currSum - k];

            // Add currSum to the dictionary of prefix sums
            if (!prefixSums.ContainsKey(currSum))
                prefixSums[currSum] = 0;
            prefixSums[currSum]++;
        }

        return res;
    }

    static void Main(string[] args) {
        int[] arr = { 10, 2, -2, -20, 10 };
        int k = -10;
        Console.WriteLine(cntSubarrays(arr, k));
    }
}

JavaScript

function cntSubarrays(arr, k) {

    // Map to store prefix sums frequencies
    const prefixSums = new Map();
    let res = 0;
    let currSum = 0;

    for (let val of arr) {
        // Add current element to sum so far
        currSum += val;

        // If currSum is equal to desired sum
        // then a new subarray is found
        if (currSum === k)
            res++;

        // Check if the difference exists in the prefixSums map
        if (prefixSums.has(currSum - k))
            res += prefixSums.get(currSum - k);

        // Add currSum to the map of prefix sums
        prefixSums.set(currSum, (prefixSums.get(currSum) || 0) + 1);
    }

    return res;
}

// Driver Code
const arr = [10, 2, -2, -20, 10];
const k = -10;
console.log(cntSubarrays(arr, k));

Output

Count Subarrays having Sum K

Visit Course

Nikhil Jindal

Improve

Article Tags :

Count Subarrays having Sum K

[Naive Approach] Using Nested Loop - O(n2) Time and O(1) Space

[Expected Approach] Using Hash Map and Prefix Sum - O(n) Time and O(n) Space

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem

Thank You!

What kind of Experience do you want to share?

[Naive Approach] Using Nested Loop - O(n²) Time and O(1) Space