Finding the first subarray that sums to a given total

Question

Here is the question:

Given and unordered array of positive and negative integers. How can you find the first subarray to sum to a given value?

For example. Given the array...

[1, -3, 4, 8, 2, -14, 3, -1, 10, 6]

Find the first subarray to sum to 9.

In this example the sub array would be...

[-3, 4, 8]

I found a solution that is O(n^2) by iterating the array for start points and then iterating every end point until you find the value.

But is there a way to do this better than O(n^2)?

Answer 1

What about this?

• We run through the array, computing the sums of all the prefixes along the way. (O(n) since we can keep a running tally of the sum)

• We save the sums we encounter in some datastructure where we can search by the value of the sum and also get prefix that the sum belongs to (see below for implementation of this)

• If the sum of the prefix up to index n is off target by an amount that is the sum of a prefix we previously encountered, say, up to index m, then we found our subarray, the array from m to n. Since sum(prefix(n)) - sum(prefix(m)) = targetSum and subArray(m,n) = prefix(n) - prefix(m) (hopefully this psuedo-notation is somewhat clear)

Now the running time of our algorithm is n * (the time it takes to insert the sum of our prefix to the datastructure + the time it takes to search if we have a certain sum in our datastructure).

An obvious choice for a datastructure would be a hashtable with sums as keys and the prefix they are the sum of as values. Here search and insert take O(1) on average, so we would be O(n) on average, which seems rather decent. Code could be:

public int[] findSubArray(int[] arr, int targetSum){
    Map<Integer, Integer> sumsToIndex = new HashMap<Integer, Integer>();
    int sum = 0;

    for(int index = 0; index <= arr.length; index++){
        if(sumsToIndex.get(sum) == null){
            sumsToIndex.put(sum, index);
        }

        int offTarget = sum - targetSum;
        Integer offTargetPrefix = sumsToIndex.get(offTarget);
        if(offTargetPrefix != null){
            return Arrays.copyOfRange(arr, offTargetPrefix, index);
        }

        if(index < arr.length){
            sum += arr[index];
        }
    }
    return null;
}

However worst case, search in a hashtable is O(n) if we get a boatload of collisions, I don't know how this pans out here. Since our keys are integers, I think we might be okay. But maybe theoretically we are still O(n) worst case. Making our algorithm O(n^2) still.

What we could do is use some other datastructure, like red-black trees (with the sums as sorting key), where search and insertion are O(log n) in the worst case, making our algorithm O(n log(n)).

Answer 2

I think I came up with a solution. Suppose the following numbers, and you want to find the first subarray to sum to 4:

2 -3 7 1 5 -1

First to get rid of negative numbers, I suggest find the smallest number (-3) and add its absolute value to all the numbers, that takes O(n), we have:

5  0  10 4  8 2

Then for any sub-array with size n, the sum should be n*3 + 4, if you find that sum, then you have found the answer

I wrote the target for the sub-arrays with size 1, 2, 3 ...

7   10  13  16   19

Now start with 5, it is less than 7 then you can continue, add it to 0, it is less than 10, and you can continue, add it to 10, it is more than 13, then ignore 5, and regard 0 + 10, it is less than 10, actually it is equal to 10, it means you have found the answer, the answer is -3 + 7 = 4

---

I try to write the algorithm down! ,

 SubArraySumTo(A[], y)
 {
     x = abs(min(A));  // a loop over the array
     foreach (var a in A)
     {
         a+=x;
     }
     int start =0;
     int sum =A[0];
     int i=0;
     while (i < n)
     {
         target = (i - start +1)*x + y;              
         if (sum == target)
         {
              return A[start..i];
         }
         else if (sum < target)
         {
            i++; 
            sum += A[i];
         }
         else if (sum > target)
         {
             start++;
             sum -= A[start];
         }
     }
 }

It's an iteration with O(2n) in worst case

Answer 3

If you are looking for a sum s, and the total of all array elements is t, then the sum of the first i and the last j elements must be t - s, so the elements from index i to index n-j exclusive add up to s.

So you create a hash table or a balanced binary tree for the sum of the last j elements, starting with j = 0, then adding another element for j = 1, 2, 3 etc. Hash table will be O (1) on average, but balanced binary tree is O (log n) worst case.

For each j, you check whether t minus s minus the sum of the first i = n-j elements is in the hash table or binary tree, and proceed until j = n and i = 0.

O (n) average using a hash table, but no guarantee for the worst case. O (n log n) if you use a balanced search tree.

As an example with the data [1, -3, 4, 8, 2, -14, 3, -1, 10, 6]: The total is t = 16, we were given s = 9, so the sum of the first i and the last j elements must be 7. The list of sums of the last j elements are:

j = 0: 0
j = 1: 0, 6
j = 2: 0, 6, 16
j = 3: 0, 6, 16, 15
j = 4: 0, 6, 16, 15, 18
j = 5: 0, 6, 16, 15, 18, 4
j = 6: 0, 6, 16, 15, 18, 4, 6
j = 7: 0, 6, 16, 15, 18, 4, 6, 14
j = 8: 0, 6, 16, 15, 18, 4, 6, 14, 18
j = 9: 0, 6, 16, 15, 18, 4, 6, 14, 18, 15
j = 10: 0, 6, 16, 15, 18, 4, 6, 14, 18, 15, 16

Then we calculate the sum of the first i = 10-j elements, and 7 minus that sum must be in the last of the sums of the last j elements.

j =  0, i = 10: 7 -  16 = -9, not found
j =  1, i =  9: 7 -  10 = -3, not found
j =  2, i =  8: 7 -   0 =  7, not found
j =  3, i =  7: 7 -   1 =  6, found
j =  4, i =  6: 7 - (-2) = 9, not found
j =  5, i =  5: 7 -  12 = -5, not found
j =  6, i =  4: 7 -  10 = -3, not found
j =  7, i =  3: 7 -   2 =  5, not found
j =  8, i =  2: 7 - (-2) = 9, not found
j =  9, i =  1: 7 -   1 =  6, found
j = 10, i =  0: 7 -   0 =  7, not found

The first 1 elements have a sum of 1, the last 1 or 6 elements have a sum of 6, so elements 1..9 or 1..4 have a sum of 9. The time is basically n insertions and lookups into a data structure.

Answer 4

Below is what i have done using the sliding window approach. It works for positive and negative numbers in the array. tested for the given input and works. please see if this helps.

import numpy as np
arr=np.array([1, -3, 4, 8, 2, -14, 3, -1, 10, 6])#np.array([2,3,4,5,6,7])
length=len(arr)
start=0
end=0
sum1=0
flag=False
VALUE=9

while(flag==False):
sum1+=arr[end]
if(sum1<VALUE):
    if(end<length-1):
        end+=1
    else:
        if(start<lenth-1):
            start+=1
            end=start
            sum1=0
        else:
            print("didnt find any range**")
            break
elif(sum1==VALUE):
    print('start',start,'end',end)
    break
else:
    if(start<length-1):
        
        start+=1
        end=start
        sum1=0
      #  print("start",start)
        
    else:
        print("didnt find any range")
        break

Answer 5

The above posted solutions looks good. Here is my code for the same. It takes O(n) time to complete.

The output from the above program is 2 4. Which means 2nd, 3rd and 4th elements sum gives the value of 9. 2nd Element indicates array index of 1 not 2.

class FindArrayProblem {
    public static void main (String[] args) {
        int array[] = {1, -3, 4, 8, 2, -14, 3, -1, 10, 6};
        int sum = 9;
        findSubArray(array,sum);
    }

    static void findSubArray(int[] array, int sum){
        int start = 0 , end =0;
        int tmpSum = array[0] ;
        while (end < array.length) {
            if (tmpSum == sum){
                System.out.println((start + 1) + " " + (end + 1)) ;
                break;
            }
            if (tmpSum <= sum){
               end++ ;
                if (end < array.length)
                    tmpSum += array[end];
            } else {
                tmpSum -= array[start];
                ++ start;
            }
        }
    }
}