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)