Skip to main content

19. Kth Largest Element in an Array

mediumAsked at Palantir

Find the kth largest element in an unsorted array. Palantir asks this to test whether you reach for a min-heap of size k — the same streaming primitive their dashboards use to compute top-k entities by row count without scanning the whole dataset twice.

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

Source citations

Public interview reports confirming this problem appears in Palantir loops.

  • Glassdoor (2026-Q1)— Palantir FDE — explicitly asked 'don't sort the whole array'.
  • Blind (2025-11)— Tagged as a streaming question — interviewer cared about extra space.

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. You must solve it in O(n) time complexity (follow-up).

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 the array; return nums[n - k].

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

Tradeoff: Trivial but wasteful — you sort all n elements when you only need to know the top k. Palantir will push back.

2. Min-heap of size k

Maintain a min-heap of the largest k values seen. For each new value: push, then if size > k, pop. Top of heap is the kth largest.

Time
O(n log k)
Space
O(k)
class MinHeap {
  constructor() { this.data = []; }
  push(x) { this.data.push(x); this._up(this.data.length - 1); }
  pop() { const top = this.data[0]; const last = this.data.pop(); if (this.data.length) { this.data[0] = last; this._down(0); } return top; }
  top() { return this.data[0]; }
  size() { return this.data.length; }
  _up(i) { while (i > 0) { const p = (i - 1) >> 1; if (this.data[p] <= this.data[i]) break; [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; i = p; } }
  _down(i) { const n = this.data.length; while (true) { const l = 2*i+1, r = 2*i+2; let s = i; if (l < n && this.data[l] < this.data[s]) s = l; if (r < n && this.data[r] < this.data[s]) s = r; if (s === i) break; [this.data[s], this.data[i]] = [this.data[i], this.data[s]]; i = s; } }
}
function findKthLargest(nums, k) {
  const heap = new MinHeap();
  for (const n of nums) {
    heap.push(n);
    if (heap.size() > k) heap.pop();
  }
  return heap.top();
}

Tradeoff: O(n log k) — much faster than sort when k << n. Works on a streaming input where you can't see the whole array twice. This is the Palantir signal.

Palantir-specific tips

Palantir grades this on whether you choose the heap AND can articulate why: the top-k pattern works on infinite streams, which is how Foundry computes 'top 100 most-edited entities this hour' without buffering everything. Mention quickselect (O(n) average) as the textbook answer to the follow-up, but only code it if asked — coding a correct partition under interview pressure is the most common drop point.

Common mistakes

  • Building a MAX-heap then popping k times — works but is O(n + k log n), worse memory profile.
  • Using JS built-in sort then nums[k-1] — that's the kth SMALLEST, off by one.
  • Quickselect with deterministic pivot choice — adversarial inputs degrade to O(n^2). Always randomize.

Follow-up questions

An interviewer at Palantir may pivot to one of these next:

  • Top K Frequent Elements (LC 347) — same heap trick keyed on frequency.
  • K Closest Points to Origin (LC 973) — same heap shape, distance comparator.
  • Streaming median (LC 295) — two heaps.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why min-heap of size k, not max-heap of size n?

A min-heap of size k discards anything smaller than the current threshold in O(log k) per element. A max-heap of size n needs O(n) build time plus k extractions — same asymptotic but worse memory and worse for streaming.

When is quickselect the right answer?

When you have the whole array in memory AND k is comparable to n (say k = n/2). It's O(n) average but with randomization. For streaming or small k, stick with the heap.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →