Can we really avoid extra space when all the values are non-negative?

Question

This question is a follow-up of another one I had asked quite a while ago:

We have been given an array of integers and another number k and we need to find the total number of continuous subarrays whose sum equals to k. For e.g., for the input: [1,1,1] and k=2, the expected output is 2.

In the accepted answer, @talex says:

PS: BTW if all values are non-negative there is better algorithm. it doesn't require extra memory.

While I didn't think much about it then, I am curious about it now. IMHO, we will require extra memory. In the event that all the input values are non-negative, our running (prefix) sum will go on increasing, and as such, sure, we don't need an unordered_map to store the frequency of a particular sum. But, we will still need extra memory (perhaps an unordered_set) to store the running (prefix) sums that we get along the way. This obviously contradicts what @talex said.

Could someone please confirm if we absolutely do need extra memory or if it could be avoided?

Thanks!

Answer 1

Let's start with a slightly simpler problem: all values are positive (no zeros). In this case the sub arrays can overlap, but they cannot contain one another.

I.e.: arr = 2 1 5 1 1 5 1 2, Sum = 8

2 1 5 1 1 5 1 2
|---|
  |-----|
      |-----|
          |---|

But this situation can never occur:

* * * * * * *
  |-------|
    |---|

With this in mind there is algorithm that doesn't require extra space (well.. O(1) space) and has O(n) time complexity. The ideea is to have left and right indexes indicating the current sequence and the sum of the current sequence.

• if the sum is k increment the counter, advance left and right
• if the sum is less than k then advance right
• else advance left

---

Now if there are zeros the intervals can contain one another, but only if the zeros are on the margins of the interval.

To adapt to non-negative numbers:

Do as above, except:

• skip zeros when advancing left
• if sum is k:
  • count consecutive zeros to the right of right, lets say zeroes_right_count
  • count consecutive zeros to the left of left. lets say zeroes_left_count
  • instead of incrementing the count as before, increase the counter by: (zeroes_left_count + 1) * (zeroes_right_count + 1)

Example:

... 7 0 0 5  1  2 0 0 0 9 ...
          ^     ^
          left  right         

Here we have 2 zeroes to the left and 3 zeros to the right. This makes (2 + 1) * (3 + 1) = 12 sequences with sum 8 here:

5 1 2
5 1 2 0
5 1 2 0 0 
5 1 2 0 0 0

0 5 1 2 
0 5 1 2 0
0 5 1 2 0 0 
0 5 1 2 0 0 0

0 0 5 1 2
0 0 5 1 2 0
0 0 5 1 2 0 0 
0 0 5 1 2 0 0 0