Possible to use Math.min to get second smallest number from array?

Viewed 10710

I am using Math.min to get the smallest number out of an array of numbers. However, I also need to get the second smallest number as well. Wondering if there is a way to do this using Math.min as well, otherwise looking for the best way to get this number.

Here's what I have:

var arr = [15, 37, 9, 21, 55];
var min = Math.min.apply(null, arr.filter(Boolean));
var secondMin; // Get second smallest number from array here

console.log('Smallest number: ' + min);
console.log('Second smallest number: ' + secondMin);

13 Answers

I see you are using Array.filter (but why?) on your first min. So, if we are using ES6 features you can find the second lowest value by first removing min from the array.

var secondMin = Math.min.apply(null, arr.filter(n => n != min));

edit: for clarity, unless you are doing something very clever with Array.filter(Boolean) while calculating the first min, you should just pass it the array without filtering:

var min = Math.min.apply(null, arr);

just to make that thread completed: the fastest way is to iterate all the elements just like you can do to find minimum. But up to your needs there will be two variables used: first minimum (candidate) and second one.

This logic is O(N) while sorting approach is O(N lg(N)).

But maybe you shouldn't care if this is just for practice.

In case repeatition should be processed as independant value(just like it would be for .sort(...)[1]) then it should <= be used instead of <.

var arr = [15, 37, 9, 21, 55];
var min = Infinity, secondMin = Infinity; 
for (var i= 0; i< arr.length; i++) {
    if (arr[i]< min) {
        secondMin = min;
        min = arr[i]; 
    } else if (arr[i]< secondMin) {
        secondMin = arr[i]; 
    }
}

console.log('Smallest number: ' + min);
console.log('Second smallest number: ' + secondMin);

If you are not worried about performance you could simply sort the array.

arr.sort(function(a, b) {
  return a - b;
});

@skyboyer provides what is probably the fastest algorithm for finding the two smallest elements. Another type algorithm that runs in O(n) time is selection (in the general comp-sci definition, not how it is normally used in JavaScript), which will find the kth smallest element of an array and separate the elements into those larger and those smaller than the kth.

Even though most partitioning selection algorithms (quickselect, Floyd-Rivest, introselect) run in O(n) time, @skyboyer's answer will be faster because of the specific nature of the partition you are looking for, and because all those algorithms come with a heavy constant factor.

There is a javascript library implementing Floyd-Rivest, but named quickselect that can do the partitioning for you, in place:

quickselect(arr, 1)

arr will be rearranged so that arr[0] is the minimum, arr[1] is the second smallest element, and the remaining elements are in some arbitrary order.

This the @skyboyer version that will handle repeats correctly:

function secondSmallest(x) {
  if (x.length < 2) return 0;

  let first = Number.MAX_VALUE;
  let second = Number.MAX_VALUE;

  for (let i = 0; i < x.length; i++) {
    let current = x[i];
    if (current < first) {
      second = first;
      first = current;
    } else if (current < second && current !== first) {
      second = current;
    }
  }
  return second;
}

console.log(secondSmallest([1, 1, 1, 1, 2]));
console.log(secondSmallest([1, 2, 1, 1, 1]));
console.log(secondSmallest([6, 3, 4, 8, 4, 5]));

var arr=[1,0,-1,-2,-8,5];
var firstmin=arr[0];
var secondmin=arr[1];
for(i=0;i<=arr.length;i++) {
     if(arr[i]<firstmin){
          secondmin=firstmin;
          firstmin=arr[i];
     }
     else if(i>=1 && arr[i]<secondmin) {
         secondmin=arr[i];
     }
}

console.log(firstmin);
console.log(secondmin);

var arr = [15, 37, 9, 21, 55];
var min = Infinity, secondMin = Infinity; 
for (var i= 0; i< arr.length; i++) {
    if (arr[i]< min) {
        secondMin = min;
        min = arr[i]; 
    } else if (arr[i]< secondMin) {
        secondMin = arr[i]; 
    }
}

console.log('Smallest number: ' + min);
console.log('Second smallest number: ' + secondMin);

var arr=[1,1,1,1,1,-1,-2];
var firstmin=arr[0];
var secondmin=arr[1];
for(i=0;i<=arr.length;i++){
  if(arr[i]<firstmin){
    secondmin=firstmin;
    firstmin=arr[i];

  }else if(i>=1 && arr[i]<secondmin) {
    secondmin=arr[i];
  }

}
console.log(firstmin);
console.log(secondmin);`

A recursive approach with ternary operators would look like this. If the array has duplicates it would give you a non duplicated second min.

For example if you have have [1, 1, 2] the second min would be 2 not 1.

function findMinimums(arr, min, secondMin, i) {
  if (arr.length === i) {
    return {
      min,
      secondMin
    }
  }
  return findMinimums(
    arr,
    min = arr[i] < min ? arr[i] : min,
    arr[i] < secondMin && min !== arr[i] ? arr[i] : secondMin,
    ++i
  )
}

const arr = [5, 34, 5, 1, 6, 7, 9, 2, 1];
console.log(findMinimums(arr, arr[0], arr[1], 0))

var arr = [15, 37, 9, 21, 55];
const [secondMin, min] = arr.sort((a,b) => b - a).slice(-2)

console.log('Smallest number: ' + min);
console.log('Second smallest number: ' + secondMin);

function secondSmallest(arr){
  let firstSmallest = Infinity, secondSmallest = Infinity; 
  // if the length is 1; return the element
  if(arr.length == 1){
    return arr[0]
  }
  for (let i= 0; i< arr.length; i++) {
      if (arr[i]< firstSmallest) {
          secondSmallest = firstSmallest;
          firstSmallest = arr[i]; 
      } else if (arr[i]< secondSmallest) {
          secondSmallest = arr[i]; 
      }
  }

  console.log(firstSmallest, secondSmallest)
  return secondSmallest
}

function findTwoSmallestNumbersFromArray(num) {
let min = Math.min(...num) let secondMin = Math.min(...num.filter(numbers => !min.toString().includes(numbers)))

console.log(min, secondMin) }

let num = [4,12,99,1,3,123,5];
let sort = num.sort((a,b) => {return a-b})

console.log(sort[1])

Related