Skip to main content

14. Kth Largest Element in an Array

mediumAsked at Flipkart

Find the kth largest value in an unsorted array — Flipkart uses it to test heap vs quickselect fluency, mirroring their search ranking top-K problems.

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 in sorted order, not the kth distinct element.

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 descending and return nums[k-1].

Time
O(n log n)
Space
O(1)
return [...nums].sort((a,b) => b - a)[k - 1];

Tradeoff:

2. Min-heap of size k

Maintain a min-heap of the k largest values seen so far. Each element costs O(log k); top is the answer at the end.

Time
O(n log k)
Space
O(k)
function findKthLargest(nums, k) {
  const heap = []; // min-heap, root at index 0
  const up = i => {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p] <= heap[i]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]]; i = p;
    }
  };
  const down = i => {
    const n = heap.length;
    while (true) {
      let s = i, l = 2*i+1, r = l+1;
      if (l < n && heap[l] < heap[s]) s = l;
      if (r < n && heap[r] < heap[s]) s = r;
      if (s === i) break;
      [heap[s], heap[i]] = [heap[i], heap[s]]; i = s;
    }
  };
  for (const x of nums) {
    if (heap.length < k) { heap.push(x); up(heap.length - 1); }
    else if (x > heap[0]) { heap[0] = x; down(0); }
  }
  return heap[0];
}

Tradeoff:

Flipkart-specific tips

Flipkart panels reward you for naming quickselect as the O(n) average upgrade — they ask follow-ups on its worst case and median-of-three pivot choice.

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

Practice these live with InterviewChamp.AI →