Array Complexity – Finding the First Subarray That Sums to a Given Total

arraybig ocomplexity

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

Best Answer

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

Related Topic