Kth Largest Element in an Array
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.
Can you solve it without sorting?
Example 1:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Explanation: The sorted 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: The sorted array is [1,2,2,3,3,4,5,5,6]. The 4th largest element is 4.
Examples
Example 1
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Explanation: The sorted 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: The sorted array is [1,2,2,3,3,4,5,5,6]. The 4th largest element is 4.
Example 3
Input: nums = [1], k = 1
Output: 1
Explanation: There is only one element, so the 1st largest is 1.
Constraints
- -1 <= k <= nums.length <= 10^5
- --10^4 <= nums[i] <= 10^4
Optimal Complexity
Time
O(n)
Space
O(1)
Choose between solo practice and interview simulation
Practice Mode keeps things simple with code + tests. AI Interview Mode adds voice, pressure, and a post-round score summary.