CODEWITHSUNDEEP
algorithm
Qiang Li
Qiang Li

Reputation: 10865

Find the farthest sum of two elements from zero in an array

Given an array, what is the most time- and space-efficient algorithm to find the sum of two elements farthest from zero in that array?

Edit For example, [1, -1, 3, 6, -10] has the farthest sum equal to -11 which is equal to (-1)+(-10).

Upvotes: 0

Views: 1187

Answers (4)

Petar Ivanov
Petar Ivanov

Reputation: 93080

Just iterate over the array keeping track of the smallest and the largest elements encountered so far. This is time O(n), space O(1) and obviously you can't do better than that.

int GetAnswer(int[] arr){
    int min = arr[0];
    int max = arr[0];
    int maxDistSum = 0;

    for (int i = 1; i < arr.Length; ++i)
    {
        int x = arr[i];
        if(Math.Abs(maxDistSum) < Math.Abs(max+x)) maxDistSum = max+x;
        if(Math.Abs(maxDistSum) < Math.Abs(min+x)) maxDistSum = min+x;

        if(x < min) min = x;
        if(x > max) max = x;
    }

    return maxDistSum;
}

The key observation is that the furthest distance is either the sum of the two smallest elements or the sum of the two largest.

Upvotes: 0

PengOne
PengOne

Reputation: 48398

Using a tournament comparison method to find the largest and second largest elements uses the fewest comparisons, in total n+log(n)-2. Do this twice, once to find the largest and second largest elements, say Z and Y, and again to find the smallest and second smallest elements, say A and B. Then the answer is either Z+Y or -A-B, so one more comparison solves the problem. Overall, this takes 2n+2log(n)-3 comparisons. This is still O(n), but in practice is faster than scanning the entire list 4 times to find A,B,Y,Z (in total uses 4n-5 comparisons).

The tournament method is nicely explained with pictures and sample code in these two tutorials: one and two

Upvotes: 2

Rafał Dowgird
Rafał Dowgird

Reputation: 45141

If you mean the sum whose absolute value is maximum, it is either the largest sum or the smallest sum. The largest sum is the sum of the two maximal elements. The smallest sum is the sum of the two minimal elements.

So you need to find the four values: Maximal, second maximal, minimal, second minimal. You can do it in a single pass in O(n) time and O(1) memory. I suspect that this question might be about minimizing the constant in O(n) - you can do it by taking elements in fives, sorting each five (it can be done in 7 comparisons) and comparing the two top elements with current-max elements (3 comparisons at worst) and the two bottom elements with current-min elements (ditto.) This gives 2.6 comparisons per element which is a small improvement over the 3 comparisons per element of the obvious algorithm.

Then just sum the two max elements, sum the two min elements and take whichever value has the larger abs().

Upvotes: 1

corsiKa
corsiKa

Reputation: 82589

Let's look at the problem from a general perspective:

Find the largest sum of k integers in your array.

  • Begin by tracking the FIRST k integers - keep them sorted as you go.
  • Iterate over the array, testing each integer against the min value of the saved integers thus far.
    • If it is larger than the min value of the saved integers, replace it with the smallest value, and bubble it up to its proper sorted position.

When you've finished the array, you have your largest k integers.

Now you can easily apply this to k=2.

Upvotes: 0

Related Questions