215. Kth Largest Element in an Array

Prompt

You are given an integer array and an integer and your task is to return the largest element in the array. An important detail is that the largest element in the array refers to the largest element in the sorted order, not the distinct element.

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
If we were to sort the nums array, the array would look as follows:
nums: [1,2,2,3,3,4,5,5,6]
index: 0 1 2 3 4 5 6 7 8
The 4th largest element would be 4 instead of 3 as we would include counting any duplicates (in this case, 5).

Approach

The challenge to this problem is that you need to be able to solve this problem using an algorithm that runs in 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 largest element. The problem behind this approach is that by calling the built-in sort method, the worst-case time complexity is 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 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 largest element. Extracting the element with the maximum value from a max-heap takes worst-case time. The problem behind this approach is that might be the length of the input or so in the worst-case, the total time complexity might result in being .

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 element by comparing it with where the final pivot index is located at.

If 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 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 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.

Code

Python

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.

Discord

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 cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub

--

--

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
John Kim

John Kim

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com