Skip to main content

18. Kth Largest Element in an Array

mediumAsked at Chegg

Find the kth largest element without full sorting — a selection algorithm Chegg applies when ranking educational content by relevance score.

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. 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. Sort and index

Sort descending, return index k-1 — simple but O(n log n).

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

Tradeoff:

2. QuickSelect

Partition around a pivot (Lomuto/Hoare) and recurse only on the side containing the target index — O(n) average, O(n^2) worst without randomization.

Time
O(n) average
Space
O(1)
function findKthLargest(nums, k) {
  const target = nums.length - k;
  function partition(lo, hi) {
    const pivot = nums[hi];
    let p = lo;
    for (let i = lo; i < hi; i++)
      if (nums[i] <= pivot) [nums[p], nums[i]] = [nums[i], nums[p++]];
    [nums[p], nums[hi]] = [nums[hi], nums[p]];
    return p;
  }
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const idx = partition(lo, hi);
    if (idx === target) return nums[idx];
    if (idx < target) lo = idx + 1;
    else hi = idx - 1;
  }
  return nums[lo];
}

Tradeoff:

Chegg-specific tips

Chegg interviewers appreciate knowing QuickSelect but will ask about worst-case guarantees — discuss median-of-medians as a follow-up if asked about O(n) worst-case.

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

Practice these live with InterviewChamp.AI →