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

Admin 1
Viewed 92

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!

space-complexity memory algorithm c++
2 Answers

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
user_28053050

I think this algorithm would work, using O(1) space.

We maintain two pointers to the beginning and end of the current subsequence, as well as the sum of the current subsequence. Initially, both pointers point to array[0], and the sum is obviously set to array[0].

Advance the end pointer (thus extending the subsequence to the right), and increase the sum by the value it points to, until that sum exceeds k. Then advance the start pointer (thus shrinking the subsequence from the left), and decrease the sum, until that sum gets below k. Keep doing this until the end pointer reaches the end of the array. Keep track of the number of times the sum was exactly k.

user_16701290
Related