CODEWITHSUNDEEP
javascript
CoreDo
CoreDo

Reputation: 2891

Finding third smallest number in a given set of numbers with least time complexity

Here's a working algorithm that finds the third smallest number in a given set of numbers.

I was looking for another solutions to the given requirement with less time complexity.

Here's the working code: 

Numbers = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
var x = 0;
var y = 0;

function FindThirdSmallestNumber() {


for(var i=0;i<Numbers.length;i++) {

  if (Numbers[i] > Numbers[i+1]) {

    x = Numbers[i];
    y = Numbers[i+1];
      
      Numbers[i] = y; 
      Numbers[i+1] = x;

      i=-1;

  } else {
    //
  }

  

}

console.log(Numbers[2]);

}

FindThirdSmallestNumber();

Upvotes: 0

Views: 993

Answers (5)

RobG
RobG

Reputation: 147403

I think sorting the array is likely the fastest method, but perhaps you want avoid the built–in sort. An alternative is as Chris Li suggests: iterate over the values and just keep the 3 lowest, then return the highest of the three.

I assumed you want to avoid built-in methods, so this only uses some basic array methods and does everything else manually.

// Avoid Math.max
function getMax(arr) {
  var max = -Infinity;
  for (var i=0, iLen=arr.length; i<iLen; i++) {
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

// If data.length < 4, just returns largest value
// Iterates over data once
function get3rdSmallest(data) {

  // Helper to insert value in order
  // Expects arr to be length 3 or smaller
  function insertNum(arr, num) {
    if (!arr.length || num < arr[0]) {
      nums.unshift(num);
    } else if (num > arr[arr.length-1]) {
      arr.push(num);
    } else {
      arr[2] = arr[1];
      arr[1] = num;
    }
  }
  
  var num, nums = [];

  if (data.length < 4) {
    return getMax(data);
  }
  
  for (var i=0, iLen=data.length; i<iLen; i++) {
    num = data[i];
  
    // Insert first 3 values sorted
    if (nums.length < 3) {
      insertNum(nums, num);
      
    // If num is smaller than largest value in nums,
    // remove move largest and insert num
    } else if (num < nums[2]){
      nums.splice(-1);
      insertNum(nums, num);
    }
  }
  // Return highest (last) value in nums
  return nums[2];
}

var data = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];

console.log(get3rdSmallest([-4,-22]));    // -4
console.log(get3rdSmallest([4,0,1,7,6])); //  4
console.log(get3rdSmallest(data));        // -5

Upvotes: 0

Abana Clara
Abana Clara

Reputation: 4650

This one should be a lot simpler. Also not sure about this being any faster but in the most simple/obvious cases less code = better performance.

I just sort the array ascending and get the value based on index. So with this code you can get any place; lowest, second lowest, third lowest, etc as long as your index does not go out of range.

const input = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
    

function getLowestByRank(data, rank) {
   data.sort(function(a, b){ return a - b });
        
   return data[rank - 1];
}
    
console.log(getLowestByRank(input, 3))
console.log(getLowestByRank(input, 2))
console.log(getLowestByRank(input, 4))

Upvotes: 1

Mojo Allmighty
Mojo Allmighty

Reputation: 793

You can use Math.min function to determine the minimum until you find your X smallest number:

Numbers = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];

function FindSmallestNumber(arr, limit) {
   var min = '';
   for(var counter = 1; counter <= limit; counter ++) {
      min = Math.min.apply(Math, arr);
      arr.splice(arr.indexOf(min), 1);
   }   
   console.log(min);
}

FindSmallestNumber(Numbers, 3); //3rd smallest number

Upvotes: 0

CertainPerformance
CertainPerformance

Reputation: 370759

One option would be to have a separate sorted array of the three smallest numbers so far. Whenever you run across a number smaller than the 3rd smallest (the last in the sorted array), reassign that 3rd index to the new number, and sort it again:

const numbers = [3, 2, 55, -10, -55, 5, 3, 2, 1, -5, 33, 9, -1, 4, 5];

const sortNumeric = (a, b) => a - b;
function FindThirdSmallestNumber(input) {
  const [smallestSoFar, numbers] = [input.slice(0, 3), input.slice(3)];
  smallestSoFar.sort(sortNumeric);
  numbers.forEach((num) => {
    if (num < smallestSoFar[2]) {
      smallestSoFar[2] = num;
      smallestSoFar.sort(sortNumeric);
    }
  });
  return smallestSoFar[2];
}

console.log(FindThirdSmallestNumber(numbers));

Note that implementations that sort the whole array (as other answers do) is O(N log N), while sorting here is only ever done on an array of size 3, which is significantly less complex (O(N log 3) I think, which is equivalent to O(N))

Upvotes: 1

Ryan Wilson
Ryan Wilson

Reputation: 10765

Not sure if this is any faster but it's shorter:

//Use a custom sort function and pass it to the .sort() method
Numbers = Numbers.sort(function(x, y){ return x - y; });
if(Numbers.length > 2){
    //At this point, the 3rd item in the array should be the 3rd lowest
    console.log(Numbers[2]);
}else {
    console.log("There are not 3 numbers in the array.");
}

Upvotes: 1

Related Questions