Prefix sum problems: Given an array and value k, return the count of subarray with sum k

Problem Statement:

You are given a array with sum k.

You need to find the number of subarrays with sum k.

Example:

Input: arr = [1, 2, 3, 1, 2, 3] k = 3 
Output: 4

Explanation: [1, 2], [3], [1, 2], [3]

Solution 1: Bruteforce Approach

We will traverse all the subarray and calculate the sum and increment the count if the sum is equal to k.

Time Complexity: O(n*n)
Space Complexity: O(1)

Solution 2: Hashmap with Prefix sum approach

We will use hashmap to store the prefix sum.

We will take 2 variables, count and sum.

Traverse the array and check if sum is equal to k.

Then check if sum-k is present in Hashmap, meaning subarray exist with sum equal to k.

if the sum-k is not available, then update the sum at that index

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

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


int solution_2(vector<int> arr, int k) 
{
    int n= arr.size();
    int sum=0;
    int count=0;
    int i=0;
    int j=0;

    unordered_map<int, int>mp;
    
    for(i=0; i<n; i++)
    {
        sum += arr[i];
        if(sum == k)
            count++;

        if(mp.find(sum-k)!=mp.end())
            count+=mp[sum-k];

        mp[sum]++;
    } 
    
    return count;
}

int solution_1(vector<int> arr, int k) 
{
    
    int size = arr.size();
    
    int count = 0;

    for(int i = 0; i < size; i++)
    {
        
        int sum = 0;
        
        for(int j = i; j < size; j++)
        {
            sum += arr[j];
            count += (sum == k);
        }
    }
    
    return count;
}

int main()
{
    vector<int> arr =  {1, 2, 3, 4};
    int k = 4;
  
    cout<<solution_1(arr, k)<<endl;
    cout<<solution_2(arr, k)<<endl;

    return 0;
}

Output

1
1