Kth Largest Element in an Array

Today we are going to discuss another LeetCode problem.

The Problem

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.

Example 1

1
2
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2

1
2
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

The Solution

We will be using Hoare’s Quick Select Algorithm to solve this problem,

• Quick Select algorithm will return kth smallest element. To adjust that with the question, we pass n-k as the target index, where n is the total number of elements of the array because (n-k)th smallest element is the kth largest element.
• The partition algorithm will divide the array into two(one with all elements less than the pivot and the other greater than the pivot) and move the pivot element to its original position when the array is sorted.
• The pivot will be now the kth largest element, where k is the position of the pivot from the right side of the array.
• We can compare our target index value with this k value. if the target index is greater than k, we will repeat the process in the right partition only and the left partition only otherwise.
• At any point, if the k value matches with the target index, the element will be returned.

The JavaScript implementation of the above logic is,

Find Target Index

Quick Select Algorithm

Partition Algorithm

Swap Function

The best and average-case running time complexity of this program will be O(n) whereas the worst-case time complexity will be O(n²)

References

• Kth Largest Element in an Array on LeetCode