Coders Packet

Count Subarray with Sum Equal to K using Map in C++

By Ashutosh Sunil Rane

This article will see how we can count the total number of subarray with a sum equal to K in linear time complexity using a hash table.

In this problem, we are given an array of size n  and an integer k. And we have to find the number of subarray with a sum equal to k.

A Subarray is a part or section of an array. It is composed of contiguous blocks of indices of the original array. In simple terms, we can say subarray is a part of a given array.

Example:

for an array=[10, 20, 30, 40] the subarrays are [10], [20], [30], [40], [10, 20], [10, 20, 30], [30, 40], [20, 30],

[20, 30, 40] and [10, 20, 30, 40].

So, for an array of size n, we can have a total of n*(n+1)/2 subarrays.

 

Now, for this problem, we are given an array of integers of size n and an integer k. We have to find the total number of subarrays whose sum is equal to k. 

Example:

Example 1:
INPUT: array=[1,2,3] k=3
OUTPUT: 2

Example 2:
INPUT: array=[3,4,7,2,-3,1,4,2] k=4 OUTPUT: 4

Brute Force Algorithm

The brute force or simple approach to solving the problem is to check the sum of all the subarray in the array. And while counting the sum of all arrays we can keep a counter to count the number of subarray with a sum equal to k. This approach will make use of nested loops. 

The Time complexity of this algorithm in the worst case will be O(n2).

Now to find the sum of all n*(n-1)/2 subarrays for a greater value of n the algorithm will take more time.

Efficient Algorithm

This problem can be solved in linear time complexity. The idea is to make use of extra space and reduce the time complexity.

   - Use a unordered_map to keep the frequency of subarray sums we encounter during traversing the array.

   - And while traversing the array check if the (sum-k) value is present in the map or not. 

   - If the value is present, then we have a subarray with a sum equal to k.

   - add the frequency count of the value found to our result variable.

                                                                                                                                                                        

                                                                                                                                                       |<-------------------sum = K --------------->|

Array

 

3

4

7

2

-3

1

4

2

Sum

0

3

7

14

16

13

14

18

20

                                           |<-----------------------------  sum = (Y- k) -------------------------------->|

                                           |<----------------------------------------------------------- Sum = Y ---------------------------------------------------------->|

 

From the above diagram, if sum (y-k) is present in the map then we definitely have a subarray with a sum equal to k.

 

Program

#include 
#include 
#include 
using namespace std;

int subarraySum(vector &array, int k)
{
    unordered_map<int, int> m; //assign map m
    m.insert({0, 1});          // insert initial sum 0 in map

    int sum = 0, result = 0;

    for (int i = 0; i < array.size(); i++)
    {
        sum += array[i]; //sum of array elements

        if (m[sum - k]) //check if (sum - k) in map
            result += m[sum - k];

        m[sum]++;
    }
    return result;
}

int main()
{
    vector array{3, 4, 7, 2, -3, 1, 4, 2}; //assign array
    int k = 7;                                  //sum value equal to k
    int result = subarraySum(array, k);
    cout << "Count of Subarray with sum k : "result << endl;
    return 0;
}

OUTPUT: 

Count of Subarray with sum k : 4  

Download project

Reviews Report

Submitted by Ashutosh Sunil Rane (AshuRane09)

Download packets of source code on Coders Packet