Skip to main content

90. Kth Largest Element in an Array

mediumAsked at Ola

Find the kth largest element in an unsorted array.

By Alex Chen, 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 = 2
Output
5

Example 2

Input
nums = [3,2,3,1,2,4,5,5,6], k = 4
Output
4

Approaches

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.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Kth Largest Element in an Array and other Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →