Skip to main content

215. Kth Largest Element in an Array

mediumAsked at Anduril

Find the kth largest element without fully sorting the array. Anduril asks this to see whether you know Quickselect — an O(n) average-time selection algorithm that demonstrates in-place partitioning discipline, the same technique used in real-time ranking systems for sensor-priority queues.

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

Source citations

Public interview reports confirming this problem appears in Anduril loops.

  • Glassdoor (2026-Q1)— Listed in Anduril SWE onsite reports as a selection-algorithm question with expected Quickselect knowledge.
  • Blind (2025-11)— Anduril candidates confirm Kth Largest as a medium that probes Quickselect vs heap tradeoffs.

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
5

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

Example 2

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

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

Approaches

1. Min-heap of size k

Maintain a min-heap of the k largest elements seen so far. The root is always the kth largest.

Time
O(n log k)
Space
O(k)
// JavaScript simulation using a sorted structure (no built-in heap).
// In a production setting, use a proper min-heap.
function findKthLargest(nums, k) {
  // Sort descending and return the k-th element (0-indexed at k-1)
  return nums.sort((a, b) => b - a)[k - 1];
  // Note: This is O(n log n). Mention the heap or Quickselect approach.
}

Tradeoff: O(n log n) with sort. A proper min-heap implementation would give O(n log k). Present this as a stepping stone, then pivot to Quickselect.

2. Quickselect (average O(n))

Partition the array around a pivot (like Quicksort). Recurse only into the half containing the kth-largest rank. Average O(n), worst O(n^2) without randomization.

Time
O(n) average, O(n^2) worst
Space
O(1) in-place
function findKthLargest(nums, k) {
  // We want the kth largest, which is the (n-k)th smallest (0-indexed)
  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 select(left, right) {
    if (left === right) return nums[left];
    // Randomize pivot to avoid O(n^2) worst case
    const pivotIdx = Math.floor(Math.random() * (right - left + 1)) + left;
    [nums[pivotIdx], nums[right]] = [nums[right], nums[pivotIdx]];
    const p = partition(left, right);
    if (p === target) return nums[p];
    if (p < target) return select(p + 1, right);
    return select(left, p - 1);
  }
  return select(0, nums.length - 1);
}

Tradeoff: O(n) average with random pivot selection. Randomization is critical — without it, a sorted input triggers O(n^2) worst case. Mention both the average and worst case proactively.

Anduril-specific tips

Name Quickselect and describe the key insight: 'After partitioning, the pivot is in its final sorted position. If that position equals n-k, we're done. Otherwise recurse into one side.' Anduril systems engineers appreciate knowing the worst case and the randomized-pivot mitigation. Mention that for large k and small n, a min-heap of size k may outperform Quickselect in practice due to cache behavior — this kind of nuance impresses.

Common mistakes

  • Confusing kth largest with kth smallest — the kth largest is at index n-k in 0-indexed sorted order.
  • Not randomizing the pivot — sorted or reverse-sorted input degrades Quickselect to O(n^2).
  • Recursing into both halves after partitioning — Quickselect recurses into only one half, which is the key performance advantage.
  • Returning nums[p] when p != target before recursing — only return when p == target.

Follow-up questions

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

  • Find the kth smallest element — the same algorithm with a different target index.
  • What if the input array doesn't fit in memory?
  • How would you maintain the kth largest element dynamically as new elements arrive (LC 703)?

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 O(n) average for Quickselect?

On average, each partition splits the array roughly in half. Work done is n + n/2 + n/4 + ... = O(n). Only one recursive call is made per level, unlike Quicksort's two.

Is Quickselect or the heap approach preferred at Anduril?

Both are valid. Quickselect is O(n) average and O(1) space, which aligns with Anduril's preference for lean solutions. The heap approach is more predictable (O(n log k) guaranteed) — mention both.

What does 'kth largest in sorted order, not distinct' mean?

Duplicates count. In [3,3,3,3], the 2nd largest is 3, not undefined.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →