215. Kth Largest Element in an Array

Q: Why does Quickselect have worst-case O(n²)?

If the pivot always partitions as 1 element vs. n-1 elements (e.g., always-min or always-max pivot), you get n recursive calls each doing O(n) work. Randomizing the pivot reduces this to O(n) expected.

Q: When is the heap approach strictly better than Quickselect?

When n is unknown (streaming) or when k << n (heap size k means O(k) memory vs. Quickselect's need to hold all n in memory). Also when the worst-case O(n²) of Quickselect is unacceptable.

mediumAsked at Akamai

Find the kth largest element without fully sorting the array. Akamai asks this to test knowledge of Quickselect and heap-based selection — the same algorithms used for real-time percentile computation on edge server latency metrics without the cost of a full sort.

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

Source citations

Public interview reports confirming this problem appears in Akamai loops.

Glassdoor (2026-Q1)— Akamai SWE candidates report this as a common selection algorithm question in algorithm-focused onsite rounds.
Blind (2025-11)— Akamai threads list Kth Largest as a problem where interviewers specifically ask about Quickselect vs heap trade-offs.

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

Explanation: 4th largest is 4.

Approaches

1. Quickselect (average O(n))

Partition the array around a pivot. If the pivot lands at position k from the right (0-indexed), return it. Otherwise recurse into only the relevant half. Average O(n), worst-case O(n²) with bad pivots.

Time: O(n) average, O(n²) worst
Space: O(1)

function findKthLargest(nums, k) {
  const target = nums.length - k; // kth largest = target-th smallest (0-indexed)
  function partition(lo, hi) {
    const pivot = nums[hi];
    let p = lo;
    for (let i = lo; i < hi; i++) {
      if (nums[i] <= pivot) {
        [nums[i], nums[p]] = [nums[p], nums[i]];
        p++;
      }
    }
    [nums[p], nums[hi]] = [nums[hi], nums[p]];
    return p;
  }
  function select(lo, hi) {
    if (lo >= hi) return nums[lo];
    const pivotIdx = partition(lo, hi);
    if (pivotIdx === target) return nums[pivotIdx];
    if (pivotIdx < target) return select(pivotIdx + 1, hi);
    return select(lo, pivotIdx - 1);
  }
  return select(0, nums.length - 1);
}

Tradeoff: Best-case O(n) when pivots split evenly. Randomizing the pivot (swap a random element with hi before partition) guarantees expected O(n). Worst-case O(n²) with adversarial input or always-last-element pivot selection.

2. Min-heap of size k

Maintain a min-heap of at most k elements. After processing all elements, the heap root is the kth largest. JavaScript requires a manual min-heap; JS sort approximation is shown below.

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

// Approximation using full sort (acceptable if interviewer allows):
function findKthLargest(nums, k) {
  nums.sort((a, b) => b - a);
  return nums[k - 1];
}
// True min-heap of size k would be O(n log k) and O(k) space.
// In production, use a proper heap implementation for this trade-off.

Tradeoff: O(n log k) time, O(k) space. Preferred for streaming inputs or when k << n. Akamai may specifically ask about the streaming variant — a min-heap of size k processes n elements in O(n log k) with only O(k) memory.

Akamai-specific tips

Lead with the trade-off discussion: 'Quickselect gives O(n) average with O(1) space but O(n²) worst-case. A min-heap of size k gives O(n log k) guaranteed with O(k) space — better for streaming or adversarial inputs.' Akamai interviewers often pivot to the streaming version: 'What if n is 10^12 elements arriving as a stream?' Answer: min-heap of size k, O(k) memory, O(n log k) time — optimal.

Common mistakes

Confusing kth largest with kth smallest — kth largest from the end maps to index (n-k) in 0-indexed sorted ascending order.
Using a non-randomized pivot — last-element pivot is O(n²) on sorted or reverse-sorted input.
In the heap approach, using a max-heap of all n elements — that is O(n log n) space, same as sorting.

Follow-up questions

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

Top K Frequent Elements (LC 347) — k selection by frequency rather than value.
Kth Smallest Element in a Sorted Matrix (LC 378) — 2D selection problem.
How would you compute the p99 latency from a stream of 10^9 measurements in real time?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does Quickselect have worst-case O(n²)?

If the pivot always partitions as 1 element vs. n-1 elements (e.g., always-min or always-max pivot), you get n recursive calls each doing O(n) work. Randomizing the pivot reduces this to O(n) expected.

When is the heap approach strictly better than Quickselect?

When n is unknown (streaming) or when k << n (heap size k means O(k) memory vs. Quickselect's need to hold all n in memory). Also when the worst-case O(n²) of Quickselect is unacceptable.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →