215. Kth Largest Element in an Array
mediumAsked at PinterestPinterest's ranking pipelines need fast top-K selection. Kth Largest Element asks you to find the kth largest in an unsorted array; the interviewer wants either a size-K min-heap or a Quickselect with mid-of-three pivot — bonus if you can articulate when each is appropriate.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Pinterest loops.
- Glassdoor (2026-Q1)— Pinterest backend / recsys onsite reports list Kth Largest as a heap / Quickselect round.
- LeetCode Pinterest tag (2026-Q1)— On the Pinterest company-tagged problem list.
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 the sorted order, not the kth distinct element. Can you solve it without sorting?
Constraints
1 <= k <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
Examples
Example 1
nums = [3,2,1,5,6,4], k = 25Example 2
nums = [3,2,3,1,2,4,5,5,6], k = 44Approaches
1. Sort then index (brute force)
Sort descending, return nums[k-1].
- Time
- O(n log n)
- Space
- O(1) in-place sort
function findKthLargestSort(nums, k) {
nums.sort((a, b) => b - a);
return nums[k - 1];
}Tradeoff: Trivial to write. Wastes work — full sort when we only need the kth element. Anchor with this, then move.
2. Min-heap of size K
Maintain a min-heap of size K. For each number, push; if heap.size > K, pop. The heap root is the answer.
- Time
- O(n log k)
- Space
- O(k)
class MinHeap {
constructor() { this.a = []; }
push(v) { this.a.push(v); this._up(this.a.length - 1); }
pop() {
const top = this.a[0];
const last = this.a.pop();
if (this.a.length > 0) { this.a[0] = last; this._down(0); }
return top;
}
peek() { return this.a[0]; }
size() { return this.a.length; }
_up(i) {
while (i > 0) {
const p = (i - 1) >> 1;
if (this.a[p] > this.a[i]) { [this.a[p], this.a[i]] = [this.a[i], this.a[p]]; i = p; }
else break;
}
}
_down(i) {
const n = this.a.length;
while (true) {
const l = 2 * i + 1, r = 2 * i + 2;
let best = i;
if (l < n && this.a[l] < this.a[best]) best = l;
if (r < n && this.a[r] < this.a[best]) best = r;
if (best === i) break;
[this.a[best], this.a[i]] = [this.a[i], this.a[best]];
i = best;
}
}
}
function findKthLargestHeap(nums, k) {
const heap = new MinHeap();
for (const n of nums) {
heap.push(n);
if (heap.size() > k) heap.pop();
}
return heap.peek();
}Tradeoff: O(n log k) — strictly better than full sort. Works for streaming data and bounded memory. This is the production-shaped answer for Pinterest's ranking pipelines.
3. Quickselect (optimal expected O(n))
Partition around a pivot (Lomuto or Hoare). Recurse only into the side that contains the kth position.
- Time
- O(n) expected, O(n^2) worst case
- Space
- O(log n) recursion
function findKthLargest(nums, k) {
const target = nums.length - k; // index after ascending sort
function partition(lo, hi) {
const pivot = nums[hi];
let i = lo;
for (let j = lo; j < hi; j++) {
if (nums[j] <= pivot) {
[nums[i], nums[j]] = [nums[j], nums[i]];
i += 1;
}
}
[nums[i], nums[hi]] = [nums[hi], nums[i]];
return i;
}
function select(lo, hi) {
if (lo === hi) return nums[lo];
// Random pivot to avoid sorted-input worst case
const r = lo + Math.floor(Math.random() * (hi - lo + 1));
[nums[r], nums[hi]] = [nums[hi], nums[r]];
const p = partition(lo, hi);
if (p === target) return nums[p];
if (p < target) return select(p + 1, hi);
return select(lo, p - 1);
}
return select(0, nums.length - 1);
}Tradeoff: Expected O(n) with random pivot. The variance is real — worst case is O(n^2) on adversarial inputs. Mention the random-pivot mitigation explicitly. Pinterest interviewers will probe whether you understand the worst-case risk.
Pinterest-specific tips
Pinterest likes the two-tier answer: lead with the size-K min-heap (production-friendly, streaming-compatible), then mention Quickselect if asked for sub-O(n log k). The risk pitch is the senior signal: 'Quickselect is expected O(n) but worst-case O(n^2); production rankers prefer the heap because the bound is tight.' If they specifically ask 'can you do it without sorting?' that's your cue for the heap.
Common mistakes
- Sorting full array when the constraint says 'can you solve without sorting' — that's a hint, not optional.
- Quickselect without random pivot — fails the worst-case-input hidden test on LeetCode.
- Off-by-one on the target index: kth largest = (n - k)th smallest = index (n - k) after ascending sort.
- Using a max-heap of size N then popping K — that's O(n + k log n), worse than O(n log k) for k << n.
Follow-up questions
An interviewer at Pinterest may pivot to one of these next:
- Streaming: maintain the Kth largest as numbers arrive.
- Kth smallest instead of largest (mirror the comparator).
- Kth largest distinct value (filter duplicates first).
- Top-K from N sorted arrays (k-way merge with a min-heap).
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Is Quickselect actually used in production?
Rarely. The O(n^2) worst case is a deal-breaker for production rankers. Median-of-medians gives worst-case O(n) but with a large constant factor; in practice the size-K heap wins because the bound is tight.
Why does Pinterest care about this?
Top-K is the primitive behind every Pinterest ranking surface — top pins on a board, top boards for a user, top trending categories. Knowing the heap-vs-Quickselect tradeoff signals that you've thought about ranking infrastructure.
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill Kth Largest Element in an Array and other Pinterest interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →