Practice/Salesforce/Leetcode 215. Kth Largest Element in an Array

Leetcode 215. Kth Largest Element in an Array

CodingMust

Problem

Given an unsorted array of integers and a positive integer k, find and return the kth largest element in the array. Note that this is the kth largest element in sorted order, not the kth distinct element. Duplicate values should be counted separately.

Your solution should be more efficient than sorting the entire array for large inputs.

Requirements

1. Return the kth largest element considering duplicates as separate occurrences
2. The array may contain duplicate values
3. k is guaranteed to be valid (1 ≤ k ≤ array length)
4. Implement a solution more efficient than O(n log n) sorting for average cases

Constraints

• 1 ≤ nums.length ≤ 105
• -104 ≤ nums[i] ≤ 104
• 1 ≤ k ≤ nums.length
• Aim for better than O(n log n) average time complexity

Examples

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2 Output: 5 Explanation: When sorted in descending order [6,5,4,3,2,1], the 2nd position contains 5.

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4 Explanation: The sorted array is [6,5,5,4,3,3,2,2,1]. The element at position 4 is 4.

Example 3:

Input: nums = [1], k = 1 Output: 1 Explanation: The only element is the 1st largest.