Skip to main content

27. Kth Largest Element in an Array

mediumAsked at Lyft

Find the k-th largest element without full sorting — Lyft applies quickselect to rank surge-pricing multipliers across zones and identify the k-th highest demand area to allocate driver incentives efficiently.

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

Problem

Given an integer array nums and an integer k, return the k-th largest element in the array. Note that it is the k-th largest element in the sorted order, not the k-th distinct element. You must solve it in O(n) average time complexity.

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. Min-heap of size k

Maintain a min-heap of size k. For each element, push it and pop the minimum if size exceeds k. The heap's min is the k-th largest.

Time
O(n log k)
Space
O(k)
function findKthLargest(nums, k) {
  const heap = [];
  for (const num of nums) {
    heap.push(num);
    heap.sort((a, b) => a - b);
    if (heap.length > k) heap.shift();
  }
  return heap[0];
}

Tradeoff:

2. Quickselect (average O(n))

Partition array around a pivot. If pivot lands at index n-k, that's the answer. Recurse only into the relevant partition. Average O(n), worst O(n^2) but rare with random pivot.

Time
O(n) average, O(n^2) worst
Space
O(1) in-place
function findKthLargest(nums, k) {
  const target = nums.length - k;

  function partition(left, right) {
    const pivot = nums[right];
    let store = left;
    for (let i = left; i < right; i++) {
      if (nums[i] <= pivot) {
        [nums[i], nums[store]] = [nums[store], nums[i]];
        store++;
      }
    }
    [nums[store], nums[right]] = [nums[right], nums[store]];
    return store;
  }

  function quickselect(left, right) {
    if (left === right) return nums[left];
    const pivotIdx = partition(left, right);
    if (pivotIdx === target) return nums[pivotIdx];
    if (pivotIdx < target) return quickselect(pivotIdx + 1, right);
    return quickselect(left, pivotIdx - 1);
  }

  return quickselect(0, nums.length - 1);
}

Tradeoff:

Lyft-specific tips

Lyft specifically wants to see quickselect here — the O(n log k) heap solution is correct but they'll push you toward O(n). Explain that randomizing the pivot prevents adversarial worst-case inputs. In a streaming context (real-time surge data arriving continuously), the heap wins because you maintain the top-k incrementally — mentioning this tradeoff impresses Lyft interviewers who think about live data pipelines.

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

Practice these live with InterviewChamp.AI →