Function that finds largest pair sum in unordered array of integers

Question

I want to write a function that, given a sequence of unordered numbers, finds the largest pair sum.

largestPairSum([10, 14, 2, 23, 19]) --> 42 (i.e. sum of 23 and 19)
largestPairSum([99, 2, 2, 23, 19])  --> 122 (i.e. sum of 99 and 23)
largestPairSum([-10,-20,-30,-40])   --> -30 (i.e sum of -10 and -20)

My try

function largestPairSum(numbers)
{
   let counter =0;
   let numbersord = numbers.sort();

   if (numbersord[0] === -numbersord[0]) {
       numbersord.reverse()
       counter=numbersord[0]+numbersord[1]
       }

   else {
       counter=numbersord[-1]+numbersord[-2]
    }
  return counter
}

When invoked, the function says 'NaN' , however when I


console.log(typeof(numbersord[0]))

it says number. Not sure where I have gone wrong, thanks for reading!

you can not take negative indices for a arrays. `NaN` is still a number. even sorting does not work without callback, because it treats all values as string. — Nina Scholz, Jun 12 '20 at 09:19
Is this `numbersord[0] === -numbersord[0]` every evaluates to true? You are checking if number is same as it's negative value? Also `numbersord[-1]` takes element with index `-1` that is out of bounds from your array. — Justinas, Jun 12 '20 at 09:23

Nina Scholz · Answer 1 · 2020-06-12T09:49:26.860

You approach does not works, because

sorting by string ascending (standard without callback)
using negative indices.

You could sort descending and take the first two elememts.

function largestPairSum(numbers) {
    numbers.sort((a, b) => b - a);

    return numbers[0] + numbers[1];
}

console.log(largestPairSum([10, 14, 2, 23, 19])); // 42 (23 + 19)
console.log(largestPairSum([99, 2, 2, 23, 19]));  // 122 (99 + 23)
console.log(largestPairSum([-10, -20, -30, -40])) // -30 (-10 + -20)

A solution without sorting.

function largestPairSum(numbers) {
    let largest = numbers.slice(0, 2),
        smallest = largest[0] < largest[1] ? 0 : 1;

    for (let i = 2; i < numbers.length; i++) {
        if (largest[smallest] > numbers[i]) continue;
        largest[smallest] = numbers[i];
        smallest = largest[0] < largest[1] ? 0 : 1;
    }
    return largest[0] + largest[1];
}

console.log(largestPairSum([10, 14, 2, 23, 19])); // 42 (23 + 19)
console.log(largestPairSum([99, 2, 2, 23, 19]));  // 122 (99 + 23)
console.log(largestPairSum([-10, -20, -30, -40])) // -30 (-10 + -20)

No need for sorting. It can be done in `O(n)` but just linearly scanning for the two largest numbers. — VLAZ, Jun 12 '20 at 09:30

Lewis · Answer 2 · 2020-06-12T20:42:10.607

1

In O(n), as advised by @VLAZ:

const largestPairSum = (arr) => {
  let a = -Infinity,
      b = -Infinity;
  
  for (let item of arr)
    if (item > a && b > -Infinity)
      a = item;
    else if (item > b)
      b = item;
      
  return a+b;
}

let tests = [
  largestPairSum([10, 14, 2, 23, 19]),
  largestPairSum([99, 2, 2, 23, 19]),
  largestPairSum([-10,-20,-30,-40]),
];

console.log(tests);
console.log("Nina's test:", largestPairSum([20, 50, 10, 1, 2]));

edited Jun 12 '20 at 20:42

answered Jun 12 '20 at 09:25

Lewis

4,285
1
23
36

this does sometimes not work, because you replace maybe a larger value than the other variable has. – Nina Scholz Jun 12 '20 at 09:50
@NinaScholz Can you show me a case where it does not work? It's an `if / else if` statement, so only one of those two blocks will happen per loop, and `a` and `b` will contain the two largest values of the array after iterating over the full thing. – Lewis Jun 12 '20 at 20:28
just try `[20, 50, 10, 1, 2]`, your approach yields `60`, instead of `70`. – Nina Scholz Jun 12 '20 at 20:36
@NinaScholz Oh you're right, it overwrote `a`. Added a check to make sure logic flows to `b` if it hasn't been set yet. – Lewis Jun 12 '20 at 20:43

score 0 · Accepted Answer · answered Jun 12 '20 at 09:50

There are three problems in your code.

First, counter=numbersord[-1]+numbersord[-2] is incorrect. Trying to get a negative index from an array, just returns undefined, since there is nothing there. It's not flipping and getting from the end, to do that, you need to explicitly pass arrayLength - negativeIndex to get things from the end:

const arr = ["a", "b", "c", "d", "e"];

console.log(arr[1]);
console.log(arr[2]);

console.log(arr[-1]);
console.log(arr[-2]);

console.log(arr[arr.length - 1]);
console.log(arr[arr.length - 2]);

Second, numbers.sort() is not correct. It sorts using lexicographical order, not numeric, where 1 < 2 but also 10 < 2. You need to sort numbers properly (check the link for more information):

const arr = [1, 2, 10, 20]

arr.sort();
console.log("default (lexicographical) sort", arr);

arr.sort((a, b) => a - b);
console.log("ascending sort", arr);

arr.sort((a, b) => b - a);
console.log("descending sort", arr);

Finally, if(numbersord[0] === -numbersord[0]) this condition is useless. The only number that is equal to a negative of itself is zero:

console.log(0 === -0);
console.log(1 === -1);
console.log(42 === -42);
console.log(Infinity === -Infinity);
console.log(NaN === -NaN);

However, that's not useful to check for. The logic there (essentially) checks if the array starts with zero and if it does, it reverses it and takes the first two results. If it doesn't start with zero, it tries to take the last two elements of the array.

However, if you simply sort in descending order you get all of that for free and you can take the first two items every time.

So, with these changes, your code looks like this

function largestPairSum(numbers)
{
   let counter =0;
   //perform a descending sort
   let numbersord = numbers.sort((a, b) => b - a);
   
   //always take the first two items
   counter=numbersord[0]+numbersord[1]
       
   return counter
}

console.log(largestPairSum([10, 14, 2, 23, 19]))// --> 42 (i.e. sum of 23 and 19)
console.log(largestPairSum([99, 2, 2, 23, 19])) // --> 122 (i.e. sum of 99 and 23)
console.log(largestPairSum([-10,-20,-30,-40]))  // --> -30 (i.e sum of -10 and -20)

Thanks for your elaborate answer VLAZ, as a beginner I really appreciate to fully understand where I have gone wrong. I'm sure any beginner with a similar question can benefit from your answer. — Jenny, Jun 12 '20 at 09:57

score 0 · Answer 4 · answered Jun 12 '20 at 09:55

NaN type is a number, it is correct. You get this because there are no elements with indexes "-1" or "-2" in any array. If you want to get an elements from the end you have to use something like

arr[arr.length - 1] // returns last element

Then,

let numbersord = numbers.sort(); // sort() method mutates the original array, be careful

numbersord[0] === -numbersord[0] // - returns true only when number is 0
// to check if it is negative use Math.abs()

The question is - can array contains both negative and positive elements? In this case you can not just reverse an array [-10, -5, -2, 10] - the max sum is 8, not -15.

I would use reduce method like this:

function largestPairSum(arr) {
  const initialAcc = [-Infinity, -Infinity]
  const highestNumbers = arr.reduce((acc, rec)=> {
    if (rec <= acc[0]) return acc
    if (rec >= acc[1]) return [acc[1], rec]
    return [rec, acc[1]]
  },initialAcc)
  return highestNumbers[0] + highestNumbers[1]
}

Function that finds largest pair sum in unordered array of integers

4 Answers4