Finding the Kth Largest Element in an Unsorted Array

In data analysis, it's often crucial to quickly identify specific ranked elements within a dataset without fully sorting it. For instance, finding the top 5 highest scores, the median value, or the lowest 10% of prices. This challenge focuses on a fundamental version of this problem: efficiently locating the Kth largest element in an array that is not pre-sorted.

Problem Description

You are given an array of integers, nums, and an integer, k. Your task is to find and return the Kth largest element in the array. It is important to note that this refers to the Kth largest element when the array is sorted, not the Kth distinct element. For example, in the array [3, 2, 3, 1, 2, 4, 5, 5, 6], if k=4, the sorted order is [1, 2, 2, 3, 3, 4, 5, 5, 6]. The 4th largest element is 4. Your solution should be efficient, especially for large input arrays. You cannot modify the input array permanently if a copy is not explicitly allowed (though for this problem, in-place modification or temporary copies are generally acceptable).

Examples

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Explanation: If sorted, the array is [1,2,3,4,5,6]. The 2nd largest element is 5.

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Explanation: If sorted, the array is [1,2,2,3,3,4,5,5,6]. The 4th largest element is 4.

Example 3:

Input: nums = [7,6,5,4,3,2,1], k = 1
Output: 7
Explanation: If sorted, the array is [1,2,3,4,5,6,7]. The 1st largest element (i.e., the maximum) is 7.

Constraints

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• The solution should aim for a time complexity better than O(N log N) in the average case, where N is the length of nums.
• The input nums will always be a valid array of integers, and k will always be a valid positive integer within the bounds of nums.length.

Notes

• Consider various algorithmic paradigms that might be suitable: sorting (though aim for better than a full sort), selection algorithms (like Quickselect), or data structures designed for order statistics (like min-heaps/priority queues).
• Standard library sorting functions often run in O(N log N) time. While this might pass for smaller constraints, an optimal solution for larger N would typically avoid a full sort.
• Think about how to maintain a "window" of the largest k elements seen so far without storing the entire sorted list.
• Space complexity is also a consideration; try to optimize for both time and space.