MediumHeapAI interview only
Kth Largest Element in an Array
Asked atmetaamazongooglemicrosoftapplelinkedinuberbloomberg
01 · Problem
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?
02 · Examples
Example 01
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 02
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 03
Input
nums = [1], k = 1
Output
1
There is only one element, so the 1st largest is 1.
03 · Constraints
- 011 <= k <= nums.length <= 105
- 02-104 <= nums[i] <= 104
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.