nth-smallest-number.js

// nth smallest number from an array
// [6, 3, 2, 7, 12, 4]

// 1-st smallest number = 2
// 2-nd smallest number = 3
// 3-rd smallest number = 4

function nthsmallest(arr, n) {
    let min = arr[0];
    let min2 = arr[0];

    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min2 = min;
            min = arr[i];
        } else if (arr[i] < min2) {
            min2 = arr[i];
        }
    }

    if (n == 1) {
        return min;
    } else if (n == 2) {
        return min2;
    }
}

// [6, 3, 2, 7, 12, 4] n = 3

// [3, 2, 4, 12, 7, 6]
// [      _          ]

// [6, 3, 2, 7, 12, 4] n = 5

// special value = 6
// [3, 2, 4], [7, 12]

let myArray = [6, 3, 2, 7, 12, 4]

function split(arr, specialValue) {
    const smaller = [];
    const bigger = [];

    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < specialValue) {
            smaller.push(arr[i]);
        }

        if (arr[i] > specialValue) {
            bigger.push(arr[i]);
        }
    }

    return [smaller, bigger];
}

function smartNthSmallest(arr, n) {
    // [1] [2, 6, 9, 7, 8, 9, 20, 54]
    const specialValue = arr[0]; // 1.

    const [smaller, bigger] = split(arr, specialValue); // O(n)

    if (n < smaller.length + 1) {
        return smartNthSmallest(smaller, n) // O(n-1)
    } else if (smaller.length + 1 == n) {
        return specialValue;
    } else if (n > smaller.length + 1) {
        return smartNthSmallest(bigger, n - (smaller.length + 1));
    }
}

console.log(smartNthSmallest(myArray, 1) == 2);
console.log(smartNthSmallest(myArray, 2) == 3);
console.log(smartNthSmallest(myArray, 3) == 4);
console.log(smartNthSmallest(myArray, 4) == 6);

// n + n/2 + n/4 + n/8 -> O(N)

// n + n - 1 + n - 2 + n - 3 -> (N*(N-1)/2) ~ O(N^2) 

// sorting is O(N * logN)

// function cheating(arr, n) {
//     let copy = [...arr];

//     copy.sort((a, b) => a - b);

//     return copy[n - 1];
// }

// cheating(myArray, 0);