Is there another way to sort integers in arrays?

Question

I was practicing my skills on CodeWars and I got a problem where I had to find the unique number in the given array. My solution needed to sort a integer array first, thus I had to use this arr.sort(function (a,b) { return a - b }). Because I did it the way I did, it is just complaining that I've exceeded the maximum call stack size. Is there any way I can sort arrays without using the aforementioned method. Code in question:

function findUniq(arr) {
  arr.sort(function (a,b) { return a - b })
  if (arr[0] == arr[1]) { return Math.max(...arr) }
  else { return Math.min(...arr) }
}

Are you allowed to use javascript libraries, or does it have to be your own code? — Andrew Corrigan, Sep 03 '21 at 13:42
what is the "unique number" of an array? And I'm pretty sure, this code won't raise a "Maximum call stack" error ... And no, the way you do the sort, is pretty much how you do it ... — derpirscher, Sep 03 '21 at 13:43
So in summary, you want to sort an array without using [`Array.prototype.sort()`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort)? — 3limin4t0r, Sep 03 '21 at 13:44
Check this out as it might answer all your questions: https://stackoverflow.com/questions/11246758/how-to-get-unique-values-in-an-array — DragonInTraining, Sep 03 '21 at 13:45
I was going to say, if you're allowed it, Lodash is the quickest I've encounteredhttps://lodash.com/docs/#sortBy — Andrew Corrigan, Sep 03 '21 at 13:45
@derpirscher the unique number of an array is a number that is different than the rest of the numbers in the array. When I test this code in CodeWars, it gives me a "maximum call stack" error. — Pexate, Sep 03 '21 at 13:49
@AndrewCorrigan Do you really think `lodash.sortBy` is any faster than `Array.sort`? Especially if you look at the implementation, you can see that it internally uses `Array.sort` — derpirscher, Sep 03 '21 at 13:50
@DragonInTraining that isn't quite what I'm looking for, see previous comment for further explanation. — Pexate, Sep 03 '21 at 13:51
@derpirscher whenever I've used lodash on large (especially complex) datasets, it has shaved a couple of seconds off the execution time - I'm not sure why it works, but in my experience it does — Andrew Corrigan, Sep 03 '21 at 13:51
@AndrewCorrigan That might be the case for complex datasets (and heavily depending on the compare function you wrote yourself) but I doubt lodash will outrun plain `Array.sort` on a simple array of numbers. — derpirscher, Sep 03 '21 at 13:55
@AndrewCorrigan this only needs to be used for an answer for a coding question so I need something that is very basic. Doesn't need to be fast, just simple. — Pexate, Sep 03 '21 at 13:55
@Pexate If I understand you correctly you have an array that contains all equal values, except one? Like `[1,1,1,1,2,1,1,1,1]`, then the expected result would be `2`? There is no need for sorting in this case. This can be done in a single iteration. And that may be the source of the error. In such coding competitions, the set very strict boundaries. And sorting is O(n logn), that may already be too much for the accepted solution — derpirscher, Sep 03 '21 at 13:58
_lodash, the times I've noticed its performance as better is usually when I've looped more complex data, not pure integers. What about indexOf? — DragonInTraining, Sep 03 '21 at 13:59
Fair enough, in that case, you might want to look into the quicksort algorithm - there's a few options here: https://stackoverflow.com/questions/5185864/javascript-quicksort — Andrew Corrigan, Sep 03 '21 at 14:01

3limin4t0r · Answer 1 · 2021-09-03T14:21:00.603

This is a XY-problem.

I had to find the unique number in the given array

Yet you ask about an issue in your attempted solution rather than the problem itself.

To solve this problem I would personally not use sort, but take the first 3 elements and determine the non-outlier. If all the first 3 elements are non-outliers, then you can loop through the remaining array (using find) to find the outlier.

This solution assumes an array of at least 3 elements is passed where all elements are the same except a single element.

function findUniq(arr) {
  // If the first element is not equal to the second and the third,
  // then the first element is the outlier. If it is equal to one of
  // the two, then it is a non-outlier (common).
  if (arr[0] != arr[1] && arr[0] != arr[2]) return arr[0];

  const common = arr[0];
  return arr.find(n => n != common);
}

score 0 · Answer 2 · answered Sep 03 '21 at 14:15

You can easily solve this problem without sorting (given the array fulfills the condition):

If the first two elements of the (unsorted) array are equal, return the first element in the array, that differs from them.
If the first two elements of the (unsorted) array are different, check the third element and return whichever of the first two is different from the third.

function unique(arr) {
  return (arr[0] === arr[1])
    ? arr.find(x => x !== arr[0])
    : (arr[0] === arr[2] ? arr[1] : arr[0])
}

Is there another way to sort integers in arrays?

2 Answers2