10
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ TO answer your specific question: What is the mathematical relationship between i and o? Print them out if it helps. BTW the comma operator is unhelpful in the termination condition of the loop. \$\endgroup\$ – Snowbody Jan 3 '18 at 16:24
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ As another suggestion: If you wanted to sum the N smallest elements from an array of size M, you can do that in O(M) using Quickselect (The O(M) is average case, and is very similar to quick sort) \$\endgroup\$ – Nathan Merrill Jan 3 '18 at 20:52
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer/ jsperf website. I forgot about that site and didn't realize I could use it for hackerrank questions. I have been trying to find a way to measure my solutions with time. \$\endgroup\$ – Dream_Cap Jan 3 '18 at 7:12
  • \$\begingroup\$ -1 Using a sort to find min and max is not the way to solve this problem. \$\endgroup\$ – Blindman67 Jan 3 '18 at 13:40
  • 1
    \$\begingroup\$ @Blindman67 The part using sort comes from the original post in the question, it's not a recommendation in this answer. (And in the meantime the answer was improved to point out the problems with using sort.) \$\endgroup\$ – janos Jan 3 '18 at 21:29
  • \$\begingroup\$ Instead of the ternaries for min-max, I'd recommend using Math.min and Math.max. \$\endgroup\$ – Gerrit0 Jan 3 '18 at 22:53
  • \$\begingroup\$ @Gerrit0 Thanks, but may I ask why? Are they more idiomatic, or maybe faster? \$\endgroup\$ – Gerardo Furtado Jan 3 '18 at 23:36
5
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ If you have questions about time complexity calculation for this specific algorithm, feel free to ask. \$\endgroup\$ – Glenn Codes Jan 3 '18 at 13:28
  • 1
    \$\begingroup\$ If bored, find min and max using 3n/2 comparisons using open code in the same loop computing the sum. \$\endgroup\$ – greybeard Jan 3 '18 at 13:47
  • 1
    \$\begingroup\$ @GerardoFurtado I hope you didn't delete your answer just because somebody gave it a -1. (I'm ready to +1 if you undelete.) \$\endgroup\$ – janos Jan 3 '18 at 14:27
  • 1
    \$\begingroup\$ @janos no, I deleted it because this one is the correct one, I should not have used sort in my answer, as the answerer here explains. \$\endgroup\$ – Gerardo Furtado Jan 3 '18 at 14:30
  • 2
    \$\begingroup\$ @GerardoFurtado I didn't see your answer as "you used sort". Sorting was in the original code already, it was not your idea. That's how I read your answer. You added other improvements, and the upvotes show that readers found your review helpful, and that's why I hope you will undelete it (with some minor touch-ups perhaps) \$\endgroup\$ – janos Jan 3 '18 at 14:38
-1
\$\begingroup\$

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.

\$\endgroup\$
  • 5
    \$\begingroup\$ This is already explained in the other answers. Do you have anything new to add? \$\endgroup\$ – Null Jan 3 '18 at 14:23

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.