Finding the minimum and maximum sums

Question

For this HackerRank warmup challenge, I was wondering if there was a way I could improve the selection of my indices for the minSum:

Here is the problem:

Print two space-separated long integers denoting the respective minimum and maximum values that can be calculated by summing exactly four of the five integers. (The output can be greater than 32 bit integer.)

Sample Input

1 2 3 4 5

Sample Output

10 14

Here is the solution:

function miniMaxSum(inArr) {
    // Complete this function


    let maxSum = 0,
        minSum = 0;
   inArr.sort();

    for (var i = arr.length - 1, o = 0; i >= arr.length - 4, o < 4; i--, o++){
       maxSum += arr[i];
       minSum += arr[o];
    }
    console.log(minSum, maxSum)
}

Is there a way I could have avoided the o counter in my for loop and instead selected the array in a different way? Like minSum += arr[some math computation].

Also, any performance optimizations are welcome too.

Answer 1

Instead of calculating two sums, you could just calculate one: the sum of all elements. Then, the min sum is the sum minus the maximum element, and max sum is the sum minus the minimum element. Note that sorting just to find the minimum and maximum elements is inefficient, because sorting is generally an \$O(n \log n)\$ operation, and finding the minimum and maximum (and the sum) is possible in a single pass, which would be \$O(n)\$.

Hard-coding the number 4 makes the solution very rigid, applicable to only this specific problem. In your implementation you could use the length of the array instead in a way to make that number 4 unnecessary, and easily make your implementation applicable to a more general set of problems. The number 4 is an artificial restriction; it's wise to get rid of it.

Answer 2

I hope that since you asked...

Is there a way I could have avoided the 'o' counter in my for loop and instead selected the array in a different way?

... you're open to completely different approaches. If that's correct, I reckon that there is a simpler way to do this.

Just slice that array

Actually, you almost get it when you did:

inArr.sort();

As you'll see, sorting the array is the key here. If you stop to think, after sorting (in ascending order) your array:

• minSum is just the sum of all elements except the last one;
• maxSum is just the sum of all elements except the first one.

That being said, you can sort your array...

arr.sort();

... and, after that, using a very basic function to sum elements, like reduce...

function sum(subArr) {
  return subArr.reduce(function(a, b) {
    return a + b;
  }, 0);
}

... that you call on different slices of the array:

var minSum = sum(arr.slice(0, -1))//all elements except the last one
var maxSum = sum(arr.slice(1))//all elements except the first one

Here is the demo, with different arrays:

function miniMaxSum(arr) {
  arr.sort();
  var minSum = sum(arr.slice(0, -1))
  var maxSum = sum(arr.slice(1))
  console.log(minSum, maxSum)
}

function sum(subArr) {
  return subArr.reduce(function(a, b) {
    return a + b;
  }, 0);
}

miniMaxSum([1, 4, 2, 5, 3])
miniMaxSum([42, 24, 12, 57, 3])
miniMaxSum([100, 102, 101, 103, 104])

It gets simpler

The solution above, using reduce, works with an array of any length:

function miniMaxSum(arr) {
  arr.sort();
  var minSum = sum(arr.slice(0, -1))
  var maxSum = sum(arr.slice(1))
  console.log(minSum, maxSum)
}

function sum(subArr) {
  return subArr.reduce(function(a, b) {
    return a + b;
  }, 0);
}

miniMaxSum([1, 4, 7, 5, 3, 8, 6, 2])

However, as the the challenge says that you'll always be given five integers, and as your very solution only accepts an array with 5 integers...

i >= arr.length - 4, o < 4

... this could be even simpler, dropping both the reduce and the for loop:

function miniMaxSum(arr) {
  arr.sort();
  var minSum = arr[0] + arr[1] + arr[2] + arr[3]
  var maxSum = arr[1] + arr[2] + arr[3] + arr[4]
  console.log(minSum, maxSum)
}

miniMaxSum([1, 4, 2, 5, 3])
miniMaxSum([42, 24, 12, 57, 3])
miniMaxSum([100, 102, 101, 103, 104])

It gets even more simple: no sort

Using sort can greatly increase the time complexity. The good news is that there is a solution without sort. It's based on this simple logic, as described in this other answer:

• minSum is just the sum of all elements except the smallest one;
• maxSum is just the sum of all elements except the biggest one.

Therefore, you just need to sum all elements, then subtract the smaller one to get minSum and subtract the biggest one to get maxSum.

So, here is yet another solution, without any sort:

function miniMaxSum(arr) {
  var min = Infinity,
    max = -Infinity,
    count = 0;
  for (var i = 0; i < arr.length; i++) {
    count += arr[i];
    min = arr[i] < min ? arr[i] : min;
    max = arr[i] > max ? arr[i] : max;
  }
  console.log(count - min, count - max)
}

miniMaxSum([1, 4, 2, 5, 3])
miniMaxSum([42, 24, 12, 57, 3])
miniMaxSum([100, 102, 101, 103, 104])

Performance

Regarding the performance, your code (for loop) is around 5% faster than mine (reduce), have a look here:

https://jsperf.com/minmaxsum

I believe 5% is not a big value, but if you are ultra-concerned about performance, stick with the for loop.

Of course, the simple solution (just adding the elements of the array) is, as expected, faster than both:

https://jsperf.com/minmaxsum-v2/1

Funnily enough, the "no sort" version doesn't seem to be that fast in the JSPerf test:

https://jsperf.com/min-max-sum-v3/1

---

PS: be careful with the names: in your snippet you have a parameter named inArr, but there is no arr anywhere.

Answer 3

Since the accepted answer still makes use of a sort function and thus has as time complexity \$O(n \log(n))\$, I would like to add that there is an option to have \$O(n)\$ time complexity. Of course as \$n\$ in the challenge is always 5, the time complexity for the challenge is actually constant, but the solution can generalize to \$n\$. (i.e. Search the minimum and maximum values that can be calculated by summing exactly \$n-1\$ of \$n\$ integers.)

The important part is basically to not use sort. Calculate the smallest and the biggest element of the input array with a simple loop that iterates once over the values. Then calculate the total sum of the entire array (which also just iterates once over the values and can happen in the same loop but that's not necessary). Finally subtract the minimum and maximum elements from the total sum to get respectively the maximum and minimum values as result.

Answer 4

I wouldn't bother sorting the array. Instead I would calculate the sum, and find minimum an maximum values in the list. The answers can then be calculated as sum - maxval and sum - minval.