Skip to main content

21. Kth Largest Element in an Array

mediumAsked at Activision

Return the kth largest element without sorting the entire array — Activision uses this to gauge heap fluency before leaderboard top-K read questions.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array nums and integer k, return the kth largest element in the array. Note this is the kth largest by value, not the kth distinct.

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. Full sort

Sort descending; return index 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. After scanning, the heap root is the kth largest. Use quickselect for O(n) average if heap is unavailable.

Time
O(n log k)
Space
O(k)
// minHeap: push if size<k, else if num > top, pop+push
function findKthLargest(nums, k) {
  const heap = new MinHeap();
  for (const n of nums) {
    if (heap.size() < k) heap.push(n);
    else if (n > heap.peek()) { heap.pop(); heap.push(n); }
  }
  return heap.peek();
}

Tradeoff:

Activision-specific tips

Activision wants you to call out the heap-vs-quickselect tradeoff aloud — same calculus they apply when caching leaderboard top-K reads under live-service load.

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 Activision interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →