Skip to main content

215. Kth Largest Element in an Array

mediumAsked at IBM

Kth Largest Element is IBM's heap/quickselect screener. The interviewer is grading whether you ship the O(n log k) min-heap solution under time pressure, whether you mention Quickselect for O(n) average, and whether you handle the duplicate-friendly definition correctly.

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

Source citations

Public interview reports confirming this problem appears in IBM loops.

  • Glassdoor (2026-Q1)— IBM SWE-2 / SWE-3 onsite recurring problem (heap / selection track).
  • LeetCode (2026-Q1)— Top-20 IBM-tagged problem (medium tier).
  • GeeksforGeeks (2025-12)— Listed in IBM interview-experience archive (Quickselect + heap variants).

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

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

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

Tradeoff: Two-liner. Acceptable when n is small and the language has a fast sort. The interviewer will follow with 'can you do it without sorting?' — that's the cue for the heap or Quickselect approach.

2. Min-heap of size k (optimal for streaming)

Maintain a min-heap of size k. For each new number, push; if size > k, pop. At the end, the heap's min is the answer.

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

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: O(n log k) time, O(k) space. The IBM-preferred answer because it generalizes to streaming inputs (the heap can run online as data flows in). The space win matters when n is huge but k is small.

3. Quickselect (optimal average-case)

Partition around a pivot (Lomuto or Hoare). Recurse only into the side containing the target index.

Time
O(n) average, O(n^2) worst
Space
O(log n) stack
function findKthLargestQuickselect(nums, k) {
  const target = nums.length - k;
  const 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++;
      }
    }
    [nums[i], nums[hi]] = [nums[hi], nums[i]];
    return i;
  };
  const select = (lo, hi) => {
    if (lo === hi) return nums[lo];
    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: O(n) expected time — the asymptotic optimal. Risk: adversarial inputs (sorted arrays) hit O(n^2) without randomized pivot selection. For interview-quality code, randomize the pivot with a swap to nums[hi] from a random index in [lo..hi]. Mention this defensively.

IBM-specific tips

IBM grades the explicit awareness of three solutions: sort (baseline), heap (streaming-friendly), Quickselect (asymptotic optimal). State the full landscape, then pick the heap for the final code if asked 'which would you use in production?' The heap wins because: (1) predictable O(n log k) — no worst-case spike, (2) works on streaming inputs, (3) extends to top-k follow-ups. Mention randomized-pivot Quickselect as the academic optimum.

Common mistakes

  • Confusing 'kth largest' with 'kth distinct largest' — duplicates count separately.
  • Using a max-heap of size n instead of a min-heap of size k — wastes O(n) space for no benefit.
  • Forgetting to randomize the Quickselect pivot — O(n^2) on sorted inputs.
  • Off-by-one: nums[n - k] vs nums[n - k - 1] — 'kth largest' is the (n-k)th index after ascending sort (0-indexed).
  • Using Math.max repeatedly inside a loop with a comparison — O(n) per call when not destructured.

Follow-up questions

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

  • Top K Frequent Elements (LeetCode 347) — heap on frequencies.
  • Kth Smallest Element in a Sorted Matrix (LeetCode 378) — heap on coordinates.
  • What if the array doesn't fit in memory? (External sort + reservoir; heap of size k streams.)
  • Median from a data stream (LeetCode 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

Heap or Quickselect — which would IBM prefer?

Heap. IBM has streaming and distributed workloads (Watson telemetry, Cloud monitoring) where Quickselect's O(n^2) tail and lack of streaming support are disqualifying. The heap solution generalizes to the 'data is too big for memory' follow-up; Quickselect requires random access.

Why min-heap of size k instead of max-heap of all n?

Because you only ever care about the top k elements. Maintaining a min-heap of size k keeps memory bounded to k. The smallest element in the heap is the kth largest seen so far; any new element smaller than that can't be in the top k and is discarded immediately.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →