Leetcode #: 215
Name: Kth Largest Element in an Array
Companies asked: Amazon, Cisco, Google, Meta, Microsoft
You are given an integer array nums and an integer k and your task is to return the kth largest element in the array. An important detail is that the kth largest element in the array refers to the kth largest element in the sorted order, not the kth distinct element.
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4If we were to sort the nums array, the array would look as follows:
index: 0 1 2 3 4 5 6 7 8The 4th largest element would be 4 instead of 3 as we would include counting any duplicates (in this case, 5).
The challenge to this problem is that you need to be able to solve this problem using an algorithm that runs in O(n) time complexity.
The naive approach would be to pre-sort or call the built-in sort method and once the array has been sorted, you can locate the kth largest element. The problem behind this approach is that by calling the built-in sort method, the worst-case time complexity is O(nlogn) due to most coding languages’ built-in sorting methods typically using Merge Sort or Quick Sort.
The other approach would be to use a max-heap where we could heapify the given nums array and call the black box’s special method of extracting the element with the maximum value k times which should result in getting the kth largest element. Extracting the element with the maximum value from a max-heap takes worst-case O(logk) time. The problem behind this approach is that k might be the length of the input or nums so in the worst-case, the total time complexity might result in being O(nlogk).
Therefore, the Quick Select approach would be ideal as it runs on-average in linear time. Quick Select is a derivative of the Quick Sort algorithm where instead of recursively calling typically 2 partitions, you would select to recursively call only a single partition instead. In this case, we want to choose the partition that would have the kth element by comparing it with where the final pivot index is located at.
If k is smaller than the final pivot index, we want to make & return the recursive call of the left partition, containing values that are less than the pivot value.
If k is greater than the final pivot index, we want to make & return the recursive call of the right partition, containing values that are greater than the pivot value.
If k is equal to the final pivot index, we want to simply return the final pivot index value as we know that the final pivot index value is at its final, correct location within the given input array.
Thank you for reading!
In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.
If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at firstname.lastname@example.org