Skip to main content

215. Kth Largest Element in an Array

medium

Find the kth largest element in an unsorted array. The canonical interview question for picking between sort, heap, and quickselect — and explaining your tradeoff.

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 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

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Sorting is O(n log n) — fine as a baseline answer, but the interviewer's follow-up will ask for better.

Hint 2

A min-heap of size k holds the 'top k so far'. The root is your answer once you've seen every element.

Hint 3

Iterate through nums. Push each number into a min-heap; if its size exceeds k, pop the smallest. At the end, the root is the kth largest.

Hint 4

For O(n) average time, quickselect: partition around a pivot like quicksort, but recurse only into the side that contains rank k.

Solution approach

Reveal approach

Two strong approaches. Min-heap of size k: scan nums once, push each value, pop when size exceeds k. At the end the heap holds the k largest values and its root is the kth largest. O(n log k) time, O(k) space — the right answer to give first. For the O(n) average follow-up, quickselect: pick a pivot, partition into less / equal / greater, and recurse only into whichever side contains the kth-largest rank. Worst case O(n^2) but expected O(n) — mention you'd shuffle the input or use median-of-medians to defend against adversarial inputs.

Complexity

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

Related patterns

  • heap
  • quickselect
  • top-k

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft
  • LinkedIn
  • Apple

Practice these live with InterviewChamp.AI

Drill Kth Largest Element in an Array and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →