MediumHeap
Kth Largest Element in an Array
metaamazongooglemicrosoftapplelinkedinuberbloomberg
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?
Examples
Example 1
Input
nums = [3,2,1,5,6,4], k = 2
Output
5
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
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
There is only one element, so the 1st largest is 1.
Constraints
- 1 <= k <= nums.length <= 105
- -104 <= nums[i] <= 104
Optimal complexity
Time
O(n)
Space
O(1)
One problem, two ways to prep
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.