Find number of subarrays with given sum (with Negative numbers) – LeetCode Solution [Medium]

In the previous post, we discussed about finding the total number of continuous subarrays of a given array (of non-negative numbers) whose sum equals to k.
In this post we’ll include negative numbers in the given array arr.

Problem Statement

https://leetcode.com/problems/subarray-sum-equals-k/

Example 1:

Input: arr = [-1,-1,1], k = 0
Output: 1
Explanation: arr[1,2] ie -1 + 1 = 0, hence one subarray.

Find number of subarrays with given sum solution

Approach

The idea is, if the sum of consecutive array elements from arr[i] to arr[i+k] is same, then the sum of elements from arr[i] to arr[i+k] = 0. Similarly, if sum of elements between two indices i and j is such that: sum[i] – sum[j] = k, then the sum of elements between i and j indices is k.

Pseudocode

1. Initialize: sum = 0, solution = 0, map[0] = 1
2. N = A.size()
3. for i = 0 to N-1
4.   sum += A[i]    //sum till ith element
5    if (map.find(sum-k) != map.end()) //finding sum-k upto i
6.     solution += map[sum-k]
7.   map[sum] += 1
8. return solution

Code Implementation

//
//  main.cpp
//  Subarray with sum
//
//  Created by Himanshu on 18/09/21.
//

#include <iostream>
#include <climits>
#include <map>
using namespace std;
const int N = 7;

int subarraySum(int A[], int k) {
    map<int, int > hmap;
    int sum = 0, sol = 0;
    
    hmap[0] = 1;
    
    for (int i=0; i<N; i++) {
        sum = sum + A[i];
        if (hmap.find(sum-k) != hmap.end()) {
            sol += hmap[sum-k];
        }
        hmap[sum] += 1;
    }

    return sol;
}

int main() {
    int A[N] = {5, 2, 4, -6, -1, -1, 1};
    int k = 6;
    
    cout<<"Number of subarray with sum "<<k<<": "<<subarraySum(A, k)<<endl;
    
    k = 0;
    cout<<"Number of subarray with sum "<<k<<": "<<subarraySum(A, k)<<endl;
    
    return 0;
}

Output

Number of subarray with sum 6: 1
Number of subarray with sum 0: 2

Here’s a working example:

https://ideone.com/AWlMTx

Leave a Reply

Your email address will not be published.