Kth Largest Element In An Array

Mark as Completed

Lesson

Question: Write a function to find the kth largest element in an unsorted array. Given an array of integers and a value k, return the kth largest element in the array, where k is an index into the sorted array in descending order (not the kth distinct element).

Video Solution

Solution Code:

function findKthLargest(arr, k) {
  const minHeap = createMinHeap(arr.slice(0, k));

  function createMinHeap(array) {
    for (let i = Math.floor(array.length/2) - 1; i >= 0; i--) {
      performHeap(array, i, array.length);
    }
    return array;
  }

  function performHeap(array, i, length) {
    while (true) {
      let x = i * 2 + 1;
      if (x + 1 < length && array[x] > array[x + 1]) {
        x++;
      }
      if (x >= length || array[i] <= array[x]) {
        break;
      }
      [array[i], array[x]] = [array[x], array[i]];
      i = x;
    }
    return array;
  }

  for (let i = k; i < arr.length; i++) {
    if (arr[i] > minHeap[0]) {
      performHeap(minHeap, 0, k);
      minHeap[0] = arr[i];
    }
  }

  return minHeap[0];
}

Solution Walkthrough

The problem is asking us to find the kth largest element in an unsorted array. To solve the problem, we can use a min heap, where we store the k largest elements of the array. The kth largest element in the array will be at the top of the min heap.

We start by creating a min heap with the first k elements of the array using the createMinHeap
function. The createMinHeap
function uses the performHeap
function to build a min heap from the bottom up, starting from the middle of the array. The performHeap
function swaps the current node with its smallest child if the child is smaller than the current node. The function continues until the current node is smaller than both of its children.We then iterate over the remaining elements in the array, starting from index k. For each element, we compare it with the root of the min heap. If the element is larger than the root, we replace the root with the element and perform the heapify operation using performHeap
function to maintain the min heap property.

Finally, we return the root of the min heap, which is the kth largest element in the array.

Big O Complexity Analysis The time complexity of the solution is O(nlogk), where n is the length of the input array and k is the given value. Creating the min heap with k elements takes O(k) time. Iterating over the remaining n-k elements of the array takes O(n-k) time. Performing the heapify operation for each of the n-k elements takes O(logk) time. Therefore, the total time complexity is O(k + (n-k)logk) = O(nlogk).

The space complexity of the solution is O(k), since we are storing only k elements in the min heap.

Code Output:

const arr1 = [32, 15, 64];
console.log(findKthLargest(arr1, 2)); // Output: 15

const arr2 = [3, 3, 1, 2, 4, 5, 5, 6];
console.log(findKthLargest(arr2,

Previous Lesson Next Lesson