Kth Largest Element in an Array — LC Medium

Companies: Facebook, Amazon, Spotify

215. Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

You must solve it in O(n) time complexity.

Example 1:

Example 2:

Constraints:

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104

My first approach: using min heap as max heap

logic is quite straightforward, convert the min heap library to max heap and apply.

Time complexity: O(N + klogN)

Space complexity: O(1)

My second approach: using quickselect / quicksort algorithm

quite complicated, but the quicksort algorithm is as follows

lets say we have unsorted array such as: [5,3,5,7,2,3,5,8,9]

then ideally what we do is we pick a random element and call that as pivot.

then what we do is we iterate over the values and check if the value is smaller/larger than the pivot. as we are iterating, we keep a track of the pointer that tracks the index of the element that is larger than the pivot.

algorithm steps:

  1. select pivot (rightmost)
  2. left = 0, right = len(nums) -1, pointer = left
  3. iterate over from the left to right, if we find elements that are less than the pivot, we swap the values of the nums[left] with nums[pointer]. and we move up a pointer
  4. continue this till loop ends
  5. when the loop is ended, we swap the pivot value with the last pointer position.
  6. if the pointer position is less than len(nums) — k, do a recursion over step 1–5 of the right side of the pointer (since this means that the current pointer has not up to a level that is equal to the kth position)
  7. if the pointer position is greater than len(nums) — k do a recursion over step 1–5 of the left side of the pointer
  8. if the pointer position is equal to len(nums) — k, then return the element from nums with the index of p

code:

Time complexity: O(N) average case, worst case O(N²)

Space complexity: O(1)

--

--

Data Scientist, SWE + MLE

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store