Skip to main content

31. Kth Largest Element in an Array

mediumAsked at Apple

Find the kth largest element without full sorting — Apple Fitness+ and HealthKit stream millions of events and must surface top-k rankings in real time; this heap/quickselect problem is a direct analog of that competitive-leaderboard challenge.

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 element in sorted order, not the kth distinct element. Can you solve it without sorting the full array?

Constraints

  • 1 <= k <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • k is guaranteed to be valid

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

Sort descending and return index k-1. Simple but O(n log n) — suboptimal.

Time
O(n log n)
Space
O(1)
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 the k largest elements seen so far. After scanning all elements, the heap's minimum is the answer. Optimal for streaming inputs.

Time
O(n log k)
Space
O(k)
// Min-heap implementation (JavaScript has no built-in)
class MinHeap {
  constructor() { this.h = []; }
  push(v) {
    this.h.push(v);
    let i = this.h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[p] <= this.h[i]) break;
      [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
      i = p;
    }
  }
  pop() {
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length) {
      this.h[0] = last;
      let i = 0;
      while (true) {
        let s = i, l = 2*i+1, r = 2*i+2;
        if (l < this.h.length && this.h[l] < this.h[s]) s = l;
        if (r < this.h.length && this.h[r] < this.h[s]) s = r;
        if (s === i) break;
        [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
        i = s;
      }
    }
    return top;
  }
  peek() { return this.h[0]; }
  size() { return this.h.length; }
}

function findKthLargest(nums, k) {
  const heap = new MinHeap();
  for (const n of nums) {
    heap.push(n);
    if (heap.size() > k) heap.pop();
  }
  return heap.peek();
}

Tradeoff:

Apple-specific tips

Apple interviewers ask the heap approach specifically to probe streaming-data fluency — Fitness+ rankings and HealthKit metric aggregation consume unbounded event streams where you cannot buffer the entire dataset. The min-heap of size k keeps memory bounded to O(k), which is the real constraint in production. If the interviewer pushes for O(n) average, present QuickSelect (partitioning around a pivot) — Apple's STL-equivalent C++ teams use it in low-latency paths. Always clarify whether duplicates are allowed before coding; Apple interviewers penalize assumptions.

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

Practice these live with InterviewChamp.AI →