215. Kth Largest Element in an Array

Q: Heap or quickselect — which is the 'right' answer?

Depends on what Cisco's grading. For streaming data (data arrives one at a time), heap wins because you don't need to hold all n elements. For batch processing with no streaming, quickselect's O(n) expected beats O(n log k). Both are valid; the interviewer's response to 'what's the input scenario?' tells you which to write.

Q: Why is JavaScript a poor fit for heap problems?

Because JS has no built-in priority queue. You either hand-roll a binary heap (the version above) or fake it with a sorted array (O(n) per op). Cisco interviewers know this and just want you to acknowledge it — 'in production JS code I'd reach for a library like @datastructures-js/priority-queue.'

mediumAsked at Cisco

Kth Largest at Cisco is a heap problem masquerading as a sort problem. The interviewer is checking whether you reach for a size-K min-heap (O(n log k)) instead of full-sort (O(n log n)), and whether you can articulate why the heap trick wins on streaming data.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Cisco loops.

Glassdoor (2026-Q1)— Cisco SDE-II onsite reports cite Kth Largest as a 30-minute coding round.
Blind (2025-10)— Cisco interview thread lists Kth Largest as a recurring heap problem.

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

Explanation: Sorted descending: [6,5,4,3,2,1]; 2nd largest is 5.

Example 2

Input

nums = [3,2,3,1,2,4,5,5,6], k = 4

Output

Approaches

1. Brute-force: sort descending, return index k-1

Sort the whole array, take the (k-1)th element.

Time: O(n log n)
Space: O(1) or O(n) depending on sort impl

function findKthLargestBrute(nums, k) {
  nums.sort((a, b) => b - a);
  return nums[k - 1];
}

Tradeoff: Correct one-liner. Cisco accepts this as a starting point but always asks 'can you do better than O(n log n)?' — pivot to the heap or quickselect.

2. Size-K min-heap (optimal for streaming)

Maintain a min-heap of size K. For each element: push, and if heap size > K, pop. The top of the heap at the end is the Kth largest.

Time: O(n log k)
Space: O(k)

// Minimal binary min-heap implementation
class MinHeap {
  constructor() { this.h = []; }
  size() { return this.h.length; }
  peek() { return this.h[0]; }
  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[i], this.h[p]] = [this.h[p], this.h[i]];
      i = p;
    }
  }
  pop() {
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length) {
      this.h[0] = last;
      let i = 0;
      const n = this.h.length;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let s = i;
        if (l < n && this.h[l] < this.h[s]) s = l;
        if (r < n && this.h[r] < this.h[s]) s = r;
        if (s === i) break;
        [this.h[i], this.h[s]] = [this.h[s], this.h[i]];
        i = s;
      }
    }
    return top;
  }
}
function findKthLargest(nums, k) {
  const heap = new MinHeap();
  for (const v of nums) {
    heap.push(v);
    if (heap.size() > k) heap.pop();
  }
  return heap.peek();
}

Tradeoff: O(n log k) — much better than full sort when k << n. The big win is on STREAMING data: you can process numbers one at a time without holding the whole input. Cisco interviewers specifically value this framing.

3. Quickselect (expected O(n))

Pick a pivot, partition the array into elements >= pivot and < pivot. Recurse only on the half containing the answer.

Time: O(n) expected, O(n^2) worst case
Space: O(log n) recursion

function findKthLargestQS(nums, k) {
  const target = nums.length - k;
  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++;
      }
    }
    [nums[i], nums[hi]] = [nums[hi], nums[i]];
    return i;
  }
  function select(lo, hi) {
    if (lo === hi) return nums[lo];
    // Randomized pivot to defend against adversarial inputs
    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: Optimal expected time, but worst-case O(n^2) on already-sorted input unless you randomize the pivot (which the code above does). Cisco interviewers love the awareness of the worst case and the randomization defense.

Cisco-specific tips

Cisco interviewers want you to articulate the THREE options with their tradeoffs: (1) full sort O(n log n) — fine if you only run once, (2) min-heap of size K — O(n log k) AND works on streaming inputs, (3) quickselect — O(n) expected but quadratic worst case. State all three before writing code, then ask 'which constraint matters most here?' If the interviewer says 'streaming', you write the heap. If they say 'fastest', you write quickselect.

Common mistakes

Building a max-heap of size N instead of a min-heap of size K — O(n log n), same as sort, defeats the optimization.
Forgetting to RANDOMIZE the pivot in quickselect — adversarial sorted inputs become O(n^2).
Mixing up 'Kth largest' with 'Kth smallest' — for Kth largest, the target index after sort-ascending is `n - k`.

Follow-up questions

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

Kth Smallest Element in a Sorted Matrix (LC 378) — heap or binary-search-on-value.
Top K Frequent Elements (LC 347) — heap or bucket sort by frequency.
K Closest Points to Origin (LC 973) — same heap pattern with a different key.
Running median of a stream (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

Heap or quickselect — which is the 'right' answer?

Depends on what Cisco's grading. For streaming data (data arrives one at a time), heap wins because you don't need to hold all n elements. For batch processing with no streaming, quickselect's O(n) expected beats O(n log k). Both are valid; the interviewer's response to 'what's the input scenario?' tells you which to write.

Why is JavaScript a poor fit for heap problems?

Because JS has no built-in priority queue. You either hand-roll a binary heap (the version above) or fake it with a sorted array (O(n) per op). Cisco interviewers know this and just want you to acknowledge it — 'in production JS code I'd reach for a library like @datastructures-js/priority-queue.'

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →