2

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

  • 1
    How can you come up with an O(N) solution, but then say you couldn't better the O(N^2) solution? – Robert Harvey Mar 14 '15 at 23:05
  • 1
    @RobertHarvey I didn't say that. :-) – Fogmeister Mar 14 '15 at 23:05
  • 1
    @RobertHarvey yup, I didn't say that. – Fogmeister Mar 14 '15 at 23:06
  • 2
    By the way, Googling the title of your question comes up with tons of help. Apparently this question is not a novel one. – Robert Harvey Mar 14 '15 at 23:14
  • 1
    @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 – Fogmeister Mar 15 '15 at 21:45
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)).

  • 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. – Fogmeister Mar 16 '15 at 22:04
  • Yes, thats the idea (and np obv, liked the problem) – Hirle Mar 16 '15 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. – Fogmeister Mar 16 '15 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) – Ahmad Mar 17 '15 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. – Fogmeister Mar 17 '15 at 17:51
1

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. – Fogmeister Mar 16 '15 at 18:22
  • 1
    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 :) – Ahmad Mar 16 '15 at 18:24
  • 2
    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 – Jimmy Hoffa Mar 16 '15 at 19:13
  • 1
    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. – Hirle Mar 16 '15 at 22:52
  • 1
    @Hirle, you are right, I turn back to my previous statement, that the constraints are too much to be satisfied simply ;) ! – Ahmad Mar 17 '15 at 16:50
0

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.

-1

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;
            }
        }
    }
}
  • 1
    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. – gnasher729 Jun 22 '16 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 :-) – Raghu Kumar Jun 23 '16 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.