# #2 Find Three Largest Numbers

###### tags:`Searching` `Easy`

## Problem
Write a function that takes in an array of at least three integers and, without sorting the input array, returns a sorted array of the three largest integers in the input array.
The function should return duplicate integers if necessary; for example, it should return `[10, 10, 12]` for an input array of `[10, 5, 9, 10, 12]`

### Sample Input

array = [141, 1, 17, -7, -17, -27, 18, 541, 8, 7, 7]

### Sample Output

[18, 141, 541]

<br>

:::spoiler **Optimal Space & Time Complexity**

O(n) time | O(1) space - where n is the length of the input array

:::

<br>

:::spoiler Hint 1
Can you keep track of the three largest numbers in an array as you traverse the input
array?
:::

<br>

:::spoiler Hint 2
Following the suggestion in Hint #1, try traversing the input array and updating the three largest numbers if necessary by shifting them accordingly.
:::

<br>

<hr/>

## Solutions

### Official
<br>

---

### Everyone's

Declare an answer array and update the value while iteraion

:::spoiler 月

/* Time: O(n), Space: O(1)
   n is the length of array
*/
function findThreeLargestNumbers(array) {
    const ans = [-Infinity, -Infinity, -Infinity];
    for (const num of array){
        if(num > ans[2]){
            [ans[0], ans[1]] = [ans[1], ans[0]];
            [ans[2], ans[1]] = [ans[1], ans[2]];
            ans[2] = num;
        }else if(num > ans[1]){
            [ans[0], ans[1]] = [ans[1], ans[0]];
            ans[1] = num;
        }else if(num > ans[0]){
            ans[0] = num;
        }
    }
    return ans
  }

:::

<br>

:::spoiler 東

// Time O(n) | Space O(1) - n is the length of input array
function findThreeLargestNumbers(array) {
  const ans = [array[0], array[1], array[2]];
  ans.sort((a, b) => a - b);
  for(let i = 3; i < array.length; i++){
    if(array[i] > ans[2]){
      [ans[0], ans[1], ans[2]] = [ans[1], ans[2], array[i]];
    } else if(array[i] > ans[1]){
      [ans[0], ans[1]] = [ans[1], array[i]];
    } else if(array[i] > ans[0]) ans[0] = array[i];
  }
  return ans;
}

:::

<br>

:::spoiler Hao
Solution A: use merge sort
(but this quesion ask us not to sort input array)

/**
 * Time complexity: O(nlogn) which n stands for array.length;
 * Space complexity: O(n) which n stands for array.length;
 */

const mergeSort = (array) => {
    const sortedArr = [Number.NEGATIVE_INFINITY, Number.POSITIVE_INFINITY];

    for (let i = 0; i < array.length; i += 1) {
        let start = 0;
        let end = sortedArr.length - 1;

        while (end - start > 1) {
            const mid = Math.ceil((start + end)/2);

            if (array[i] > sortedArr[mid]) start = mid;
            else end = mid;
        }

        sortedArr.splice(start + 1, 0, array[i]);
    }

    return sortedArr.slice(1, -1);
}

function findThreeLargestNumbers(array) {
    return mergeSort(array).slice(-3);
}

Solution B: update `largestThree` in every iteration

/**
 * Time complexity: O(n) which n stands for array.length;
 * Space complexity: O(1);
 */

function findThreeLargestNumbers(array) {
    const largestThree = Array(3).fill(Number.NEGATIVE_INFINITY);
    
    for (let i = 0; i < array.length; i += 1) {
        let candidate = array[i];

        for (let j = largestThree.length - 1; j >= 0; j -= 1) {
            if (candidate > largestThree[j]) {
                [candidate, largestThree[j]] = [largestThree[j], candidate];
            };
        }
    }

    return largestThree;
}

:::

<br>

The most general approach(Better than official solution)

:::spoiler YC

/* 
  time: O(n) - where n is the length of the given array
  space: O(1)
*/

function findThreeLargestNumbers(array) {
  const LENGTH = 3;
  const ans = new Array(LENGTH).fill(Number.NEGATIVE_INFINITY);
  for(let num of array){
    for(let i = LENGTH - 1; i >= 0; i--){
      if(num > ans[i]){
        shiftPos(num, i, ans)
        ans[i] = num;
        break;
      }
    }
  }
  return ans;
}


function shiftPos(num, endPos, ans){
  for(let i = 0; i < endPos; i++){
    ans[i] = ans[i+1];
  }
}

:::

<br>

---

## Supplement / Discussion