Skip to main content

73. Kth Largest Element in an Array

mediumAsked at Workday

Find the kth largest element without sorting the entire array. Workday uses this to test heap fluency — same shape as finding the top-k highest-paid employees per department for compensation reports.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2026-Q1)— Workday SDE2 phone screen.
  • Blind (2025)— Workday compensation team question.

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

Example 2

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

Approaches

1. Sort and pick

Sort descending; return nums[k-1].

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

Tradeoff: Easy. Misses the 'without sorting' note.

2. Min-heap of size k

Maintain a min-heap of size k. Push every element; pop when size > k. Heap root is kth largest.

Time
O(n log k)
Space
O(k)
// in JS, no built-in heap — implement or use a library
// pseudocode:
// for each x in nums: heap.push(x); if heap.size > k: heap.pop()
// return heap.peek()

Tradeoff: O(n log k) — better than full sort when k << n. JS lacks built-in heap so you'd code it or use a known impl.

Workday-specific tips

Workday wants the heap approach. Acknowledge JS doesn't have a built-in heap and offer to implement one or use the QuickSelect alternative. QuickSelect gives O(n) expected — mention both.

Common mistakes

  • Sorting when the prompt asks not to.
  • Using a max-heap of size n instead of a min-heap of size k — same correctness but O(n) memory.
  • Off-by-one: kth largest is index k-1 in descending sort, not k.

Follow-up questions

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

  • QuickSelect for O(n) expected time.
  • Top K Frequent Elements (LC 347).
  • Kth Smallest Element in a BST (LC 230).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

QuickSelect?

Partition like quicksort; recurse only into the half containing the kth position. O(n) expected, O(n^2) worst.

Min or max heap?

Min-heap of size k. The smallest in the heap is the kth largest seen so far. Memory = k, not n.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →