90. Kth Largest Element in an Array
mediumAsked at OlaFind the kth largest element in an unsorted array.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
Given an integer array nums and an integer k, return the kth largest element in the array. Can you solve it without sorting?
Constraints
1 <= k <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
Examples
Example 1
Input
nums = [3,2,1,5,6,4], k = 2Output
5Example 2
Input
nums = [3,2,3,1,2,4,5,5,6], k = 4Output
4Approaches
1. Sort and index
Sort descending and return nums[k-1].
- Time
- O(n log n)
- Space
- O(1)
nums.sort((a,b)=>b-a);
return nums[k-1];Tradeoff:
2. Min-heap of size k
Keep a min-heap of size k; the heap top after processing all elements is the answer.
- Time
- O(n log k)
- Space
- O(k)
function findKthLargest(nums, k) {
// simple inline min-heap behavior using sort to keep example compact
const heap = [];
for (const x of nums) {
heap.push(x); heap.sort((a,b)=>a-b);
if (heap.length > k) heap.shift();
}
return heap[0];
}Tradeoff:
Ola-specific tips
Ola interviewers ask the heap version; tie it to keeping the top-k trips by fare in a rolling window without scanning all history.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.