# Finding the first subarray that sums to a given total

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)?

• How can you come up with an O(N) solution, but then say you couldn't better the O(N^2) solution? Commented Mar 14, 2015 at 23:05
• @RobertHarvey I didn't say that. :-) Commented Mar 14, 2015 at 23:05
• @RobertHarvey yup, I didn't say that. Commented Mar 14, 2015 at 23:06
• By the way, Googling the title of your question comes up with tons of help. Apparently this question is not a novel one. Commented Mar 14, 2015 at 23:14
• @StevenBurnap yep, after reading through again I'm confident that that link will not solve this problem. I've edited the question now. (Well, not really, it's still the same question just with fewer words). Would appreciate it being taken off hold now. Thanks Commented Mar 15, 2015 at 21:45

• 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)).

• Ok. So we store the sum total up to each index. And store it as a key value pair with the sum total as the key and the index as the value. Then if we are at say value 100 and we try to get the value for the key 90 then we know it has a subarray with sum 10. Commented Mar 16, 2015 at 22:04
• Yes, thats the idea (and np obv, liked the problem) Commented Mar 16, 2015 at 22:11
• It's actually similar to an idea I came up with in the interview but I didn't store the running totals in a hash to look them up. I stored them in an array but then it was n^2 to find too with the correct difference. Commented Mar 16, 2015 at 22:14
• @Fogmeister I googled the problem and found a similar problem and solution stackoverflow.com/questions/14865688/subsequence-sum, according to that I think it should be `return Arrays.copyOfRange(arr, offTargetPrefix + 1, index);`, Moreover, as you look for the first sub-array, I think if we encounter a collision we should keep the old index and don't update it, this way, the complexity would remain `O(n)` Commented Mar 17, 2015 at 17:46
• @Ahmad yes I thought this too. Because you're looking for the first then if the previous sum exists then don't change it. Commented Mar 17, 2015 at 17:51

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

• Ah. I like that. So it is essentially O(2n) which is just n. By removing the negative numbers you've changed it to the simpler version of dealing just with non negative integers. Commented Mar 16, 2015 at 18:22
• Your welcome, I didn't test it much! you can test it with your sequences, I hope it works! ironically I was the one who just already said it can't be solved simply :) Commented Mar 16, 2015 at 18:24
• Not sure this works. Try and find the sum "400" in O(n) given this list: -1 -4 -90 -2 -22 -44 -1231 -1 -1 -900 -4 500 -100 Commented Mar 16, 2015 at 19:13
• Ex. find 1 in [2,-1]. Naively, after seeing [2], we wont try to add since 2 is already too large. That's wrong, our sum will get smaller if we add more. Now your trick. We add 1 to everything and transform to [3,0]. We see [3] and match to the new target, 2. Too large, so we wont try adding more. Still wrong. Only now its not because our sum will get smaller, but because our target will get bigger (faster than our sum will get bigger) if we add more. Commented Mar 16, 2015 at 22:52
• @Hirle, you are right, I turn back to my previous statement, that the constraints are too much to be satisfied simply ;) ! Commented Mar 17, 2015 at 16:50

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.

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
``````
• Hi, this answer would be better if you explained the algorithm a bit Commented Feb 22, 2021 at 20:12
• Hi @guysherman, thanks for your comment. I have written this in Python. Basically what it does is : 1) intialises a sliding window ( start & end to 0) 2) Then it starts with the window. 2) If the window sum is less than expected given sum it increases the end pointer. this process is repeated either the sum is met/cross the Sum value or reaches the boundary of the array . If the sum is reached means we are done. 3) In the other two cases i.e. end is reached/sum is crossed the given value, it shifts the window by incrementing the start pointer. This process is repeated until we cover array
– Giri
Commented Feb 23, 2021 at 7:45

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;
}
}
}
}
``````
• It seems you copied a solution for a different problem. What makes you think this will work with negative numbers? For example, take n numbers, the first n-1 equal to 2, the last equal to 3-2n, and try to find the sum 1. Commented Jun 22, 2016 at 18:30
• @gnasher729, 1) there are plenty of such interview questions online. If you spend few mins coding you'll figure out the answer, good to see that you concluded the code is copied. 2) The question was to find a first sub-array which this code does, not sure which different problem i solved here. 3) Regarding the test-case mentioned, i haven't tested that. If it fails yes, it can be improved to fix. 4) Thanks for downvoting :-) Commented Jun 23, 2016 at 22:33