Q: Write a function that takes a list of integers and returns the 4 highest in O(n) time.
A: Here, I use the merge sort algorithm since it uses O(n) space complexity and O(log(n)) runtime complexity. The following is my approach:
- First, divide the array into halves:
arr = [1, 5, 6, 11, 3, 4, 8, 13];
const mergeSort = (arr) => {
// end function when array consists of only one element
if (arr.length === 1){
return arr
}
// divide the array in half, taking into account the length of the array may be an odd number
const middle = Math.floor(arr.length / 2);
// create two arrays called left and right
const left = arr.slice(0, middle);
const right = arr.slice(middle, arr.length);
// pass the two arrays into the merge helper function
return merge(left, right)
}
- Then, merge the individual arrays using a helper function merge algorithm:
// O(n) algorithms have out of place complexity and need an extra array into which to sort the elements
let result = [];
let idxLeft = 0
let idxRight = 0
// iterate over the left and right arrays as long as the index is less than the length of the array
while (idxLeft < left.length && idxRight < right.length) {
// compare the elements in each array starting from index 0
// if the number on the left is less than the number on the right
if (left[idxLeft] <= right[idxRight]) {
// push the left element into the result array
result.push(left[idxLeft]);
// increment the index
idxLeft++
} else {
// otherwise, push the right element into the result array
result.push(right[idxRight]);
// increment the index (0 becomes 1, 1 becomes 2 ... )
idxRight++
}
// in the result concatenate the sorted left and right arrays
let mergedArr = result.concat(left.slice(idxLeft).concat(right.slice(idxRight)))
// pass the newly merged array and number of items to return, into the helper function
fourLargest(mergedArr, 4)
}
- Finally, return the 4 largest elements in the now sorted and merged array:
const fourLargest = (arr, n) => {
// the slice method is used to return the four elements from the end of the sorted array
let sliced = arr.slice(-n);
console.log(sliced)
}
- Don't forget to call the mergeSort function :-)
// call the mergeSort function and pass in the array to be sorted
mergeSort(arr)
Hi Mark, Here is the link to the repo for the merge-sort algorithm -- with instructions. Thanks.