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

Given an array of integers arrs and an integer k, return the total number of subarrays whose sum equals to k. A subarray is a contiguous non-empty sequence of elements within an array.

LeetCode Problem Link

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.

We’ll use a hashmap (map), with key as the sum of the array elements upto current index (i) and value as the number of subarrays with the given key (sum).

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:
Ideone

Leave a Reply