Finding the number of sub arrays that have a sum of K

Question

I am trying to find the number of sub arrays that have a sum equal to k:

int subarraySum(vector<int>& nums, int k)
{
    int start, end, curr_sum = 0, count = 0;

    start = 0, end = 0;
    while (end < (int)nums.size())
    {
        curr_sum = curr_sum + nums[end];
        end++;

        while (start < end && curr_sum >= k)
        {
            if (curr_sum == k)
                count++;
            curr_sum = curr_sum - nums[start];
            start++;
        }
    }
    return count;
}

The above code I have written, works for most cases, but fails for the following:

array = {-1, -1, 1} with k = 0

I have tried to add another while loop to iterate from the start and go up the array until it reaches the end:

int subarraySum(vector<int>& nums, int k)
{
    int start, end, curr_sum = 0, count = 0;

    start = 0, end = 0;
    while (end < (int)nums.size())
    {
        curr_sum = curr_sum + nums[end];
        end++;

        while (start < end && curr_sum >= k)
        {
            if (curr_sum == k)
                count++;
            curr_sum = curr_sum - nums[start];
            start++;
        }
    }

    while (start < end)
    {
        if (curr_sum == k)
            count++;
        curr_sum = curr_sum - nums[start];
        start++;
    }
    return count;
}

Why is this not working? I am sliding the window until the last element is reached, which should have found a sum equal to k? How can I solve this issue?

Answer 1

Unfortunately, you did not program a sliding window in the correct way. And a sliding window is not really a solution for this problem. One of your main issues is, that you do not move the start of the window based on the proper conditions. You always sum up and wait until the sum is greater than the search value.

This will not really work. Especially for your example -1, -1, 1. The running sum of this is: -1, -2, -1 and you do not see the 0, although it is there. You may have the idea to write while (start < end && curr_sum != k), but this will also not work, because you handle the start pointer not correctly.

Your approach will lead to the brute force solution that typically takes something like N*N loop operations, where N is the size of the array. This, because we need a double nested loop.

That will of course always work, but maybe very time-consuming, and, in the end, too slow.

Anyway. Let us implement that. We will start from each value in the std::vector and try out all sub arrays starting from the beginning value. We must evaluate all following values in the std::vector, because for example the last value could be a big negative number and bring down the sum again to the search value.

We could implement this for example like the following:

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

int subarraySum(vector<int>& numbers, int searchSumValue) {

    // Here we will store the result
    int resultingCount{};

    // Iterate over all values in the array. So, use all different start values
    for (std::size_t i{}; i < numbers.size(); ++i) {

        // Here we stor the running sum of the elements in the vector
        int sum{ numbers[i] };

        // Check for trivial case. A one-element sub-array does already match the search value
        if (sum == searchSumValue) ++resultingCount;

        // Now we build all subarrays beginning with the start value
        for (std::size_t k{ i + 1 }; k < numbers.size(); ++k) {
            sum += numbers[k];
            if (sum == searchSumValue) ++resultingCount;
        }
    }
    return resultingCount;
}

int main() {
    vector v{ -1,-1,1 };
    std::cout << subarraySum(v, 0);
}

.

---

But, as said, the above is often too slow for big vectors and there is indeed a better solution available, which is based on a DP (dynamic programming) algorithm.

It uses so-called prefix sums, running sums, based on the running sum before the current evaluated value.

We need to show an example. Let's use a std::vector with 5 values {1,2,3,4,5}. And we want to look subarrays with a sum of 9.

We can “guess” that there are 2 subarrays: {2,3,4} and {4,5} that have a sum of 9.

Let us investigate further

      Index  0   1   2   3   4   
      Value  1   2   3   4   5   

We can now add a running sum and see, how much delta we have between the current evaluated element and the left neighbor or over-next neighbor and so on. And if we have a delta that is equal to our search value, then we must have a subarray building this sum.

Running Sum  1   3   6  10  15

Deltas of        2   3   4   5 against next left
Running sum          5   7   9 against next next left 
                         9  12 against next next next left 

Example {2,3,4}. If we evaluate the 4 with a running sum of 10, and subtract the search value 9, then we get the previous running sum 1. “1+9=10” all values are there.

Example {4,5}. If we evaluate the 5 with a running sum of 15, and subtract the search value 9, then we get the previous running sum = 6. “6+9=15” all values are there.

We can find all solutions using the same approach.

So, the only thing we need to do, is to subtract the search value from the current running sum and see, if we have this running sum already calculated before.

Like: “Search-Value” + “previously Calculated Sum” = “Current Running Sum”.

Or: “Current Running Sum” – “Search-Value” = “previously Calculated Sum”

Again, we need to do the subtraction and check, if we already calculated such a sum previously.

So, we need to store all previously calculated running sums. And, because such a sum may appear more than one, we need to find occurrences of equal running sums and count them.

It is very hard to digest, and you need to think a while to understand.

With the above wisdom, you can draft the below potential solution.

#include <iostream>
#include <vector>
#include <unordered_map>

int subarraySum(std::vector<int>& numbers, int searchSumValue) {

    // Here we will store the result
    int resultingSubarrayCount{};

    // Here we will stor all running sums and how ofthen their value appeared
    std::unordered_map<int, int> countOfRunningSums;

    // Continuosly calculating the running sum
    int runningSum{};
    // And initialize the first value
    countOfRunningSums[runningSum] = 1;

    // Now iterate over all values in the vector
    for (const int n : numbers) {

        // Calculate the running sum
        runningSum += n;

        // Check, if we have the searched value already available
        // And add the number of occurences to our resulting number of subarrays
        resultingSubarrayCount += countOfRunningSums[runningSum - searchSumValue];

        // Store the new running sum. Respectively. Add 1 to the counter, if the running sum was alreadyy existing
        countOfRunningSums[runningSum]++;
    }
    return resultingSubarrayCount;
}

int main() {
    std::vector v{ 1,2,3,4,5 };
    std::cout << subarraySum(v, 9);
}