Leetcode #:215Kth Largest Element in an Array

Name:Medium

Difficulty:Amazon, Cisco, Google, Meta, Microsoft

Companies asked:https://leetcode.com/problems/kth-largest-element-in-an-array/

Link:

## Prompt

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 = 4Output:4If 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 8The 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 *O(n)* time complexity.

Pre-sorting

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.

Max-heap

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)*.

Quick Select

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.

## Code

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