Kth Largest Element in an Array

Kth Largest Element in an Array - LeetCode

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:

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

Example 2:

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

Here, We can sort this array and return value.

Time complexity of above code is O(nlogn). To optimize it further we can use Priority Queue (HEAP) which decrease its time complexity to O(nlogk) where k = kth number of smallest / largest element you want to get.

When there is Problem like Find Xth Largest / Smallest elements, At that time its better to use Priority Queue where you don’t require to sort all the elements.