Skip to main content

20. Kth Largest Element in an Array

easyAsked at Spotify

Find the kth largest value in an unsorted array — Spotify uses this pattern when ranking the 50th-percentile stream count across a catalog of millions of tracks.

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. Note that it is the kth largest in sorted order, not the kth distinct element. You must 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 descending

Sort the array in descending order and return index k-1.

Time
O(n log n)
Space
O(log n)
function findKthLargest(nums, k) {
  nums.sort((a, b) => b - a);
  return nums[k - 1];
}

Tradeoff:

2. Min-heap of size k

Maintain a min-heap of exactly k elements; the root is always the kth largest seen so far. O(n log k) time — critical when k << n, such as keeping a live top-50 chart.

Time
O(n log k)
Space
O(k)
function findKthLargest(nums, k) {
  // Simulate min-heap with a sorted array (interview-grade; use a real heap in prod)
  const heap = [];
  const heapPush = (val) => {
    heap.push(val);
    heap.sort((a, b) => a - b);
    if (heap.length > k) heap.shift();
  };
  for (const n of nums) heapPush(n);
  return heap[0];
}

Tradeoff:

Spotify-specific tips

Spotify interviewers want to hear you talk about streaming data — what happens when a new track lands and you must update a live chart without re-ranking the full catalog? That framing makes the heap approach feel inevitable rather than memorised.

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

Practice these live with InterviewChamp.AI →