4 Ways To Find k-th Largest Element In An Unsorted Array

July 12, 2021

Bubble Sort

Swaps pair of elements until array is sorted.
Swapping pairs for k times is enough to find the k-th largest element.

var findKthLargest_bubbleSort = function (nums, k) {
    for (let j = 1; j <= k; j++) {
        for (let i = 0; i < nums.length - j; i++) {
            if (nums[i] > nums[i + 1]) {
                const temp = nums[i];
                nums[i] = nums[i + 1];
                nums[i + 1] = temp;
            }
        }
    }
    return nums[nums.length - k]
};

32/32 cases passed (132 ms)
Your runtime beats 19.46 % of javascript submissions
Your memory usage beats 95.62 % of javascript submissions (38.8 MB)

Insertion Sort

const findKthLargest = function (nums, k) {
    let i = nums.length
    while (i--) {
        let j = i;
        while (j < nums.length && nums[j] > nums[j - 1]) {
            const temp = nums[j - 1];
            nums[j - 1] = nums[j]
            nums[j] = temp;
            j++;
        }
    }
    return nums[k - 1]
};

swipe each element with previous elements while it is bigger.

32/32 cases passed (528 ms)
Your runtime beats 5.13 % of javascript submissions
Your memory usage beats 95.2 % of javascript submissions (38.9 MB)

Selection Sort

Moves maximum element to end until array is sorted.
Since we don’t really need to sort the array, we just remove the max element k times and return it in the last time.

var findKthLargest_selectionSort = function (nums, k) {
    let max = 0;
    for (let j = 0; j < k; j++) {
        max = 0;
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] > nums[max]) {
                max = i;
            }
        }
        max = nums.splice(max, 1);
    }
    return max;
};

32/32 cases passed (108 ms)
Your runtime beats 31.26 % of javascript submissions
Your memory usage beats 39.45 % of javascript submissions (40.2 MB)

Merge Sort

const mergeSort = (array) => {
    if (array.length < 2) {
        return array;
    }

    return merge(mergeSort(array.splice(0, array.length / 2)), mergeSort(array));
}

const merge = (left, right) => {
    const sorted = [];
    while (left.length && right.length) {
        if (left[0] > right[0]) {
            sorted.push(left.shift());
        } else {
            sorted.push(right.shift());
        }
    }
    return [...sorted, ...left, ...right];
}

const findKthLargest = function (nums, k) {
    return mergeSort(nums)[k - 1]
};

Use a divide & conquer approach to sort elements. Divides arrays to length 1 & compares from bottom to top.

32/32 cases passed (100 ms)
Your runtime beats 43.03 % of javascript submissions
Your memory usage beats 5.71 % of javascript submissions (45.7 MB)