Compile Ready
Module 2 · Top K Pattern

Kth Largest Element in an Array

MediumProblem 1 of 14 9 min read ~20 min to solve LeetCode
HeapPriority QueueTop KQuickselectArray
Asked atMicrosoftAmazonGoogleMetaAppleBloomberg

Problem Statement

Given an integer array nums and an integer k, return the k-th largest element in the array. The answer is based on sorted order, not on distinct values.

Input

An integer array nums and an integer k asking for the k-th largest value by position.

Output

A single integer: the value that would appear at index nums.length - k if the array were sorted ascending.

Constraints

  • •1 <= k <= nums.length <= 100000
  • •-10000 <= nums[i] <= 10000

Examples

Example 1

Input: 
nums = [3,2,1,5,6,4], k = 2
Output: 5
Explanation: Sorted ascending gives [1,2,3,4,5,6], so the 2nd largest value is 5.

Example 2

Input: 
nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Explanation: Sorted ascending gives [1,2,2,3,3,4,5,5,6]. Counting from the largest side, 4 is the 4th largest.

Learning Objectives

  • Recognise k-th largest as a fixed-size top-k heap problem.
  • Explain why the efficient heap is a size-k min-heap, not a max-heap of all values.
  • Use the heap root as the boundary between the current top k and everything smaller.
  • Compare the heap solution with average-linear quickselect.

Intuition

Pattern Recognition

The signal is k-th largest, top k largest, or return the boundary value after keeping only the best k elements. You do not need to sort the whole array. You only need the k largest values seen so far, and among those k values the smallest one is exactly the current k-th largest candidate.

The classic trap is reaching for a max-heap because the word largest appears. A max-heap of all n values works, but it pays O(n log n) or O(n + k log n). The interview pattern is the opposite: keep a size-k min-heap. The root is the smallest among the retained largest values, so after the scan it is the k-th largest.

Common mistakes

  • ×Using a max-heap of every value and losing the O(n log k) bound.
  • ×Letting the heap grow beyond k, so the root no longer represents the k-th largest candidate.
  • ×Thinking duplicates should be removed even though this problem counts positions, not distinct values.
  • ×Writing subtraction-based comparators that can overflow on wider integer ranges.

Algorithm Explanation

Key idea

Maintain a min-heap containing the largest k values seen so far. Whenever a new number enters, push it into the heap. If the heap grows to k + 1, remove the root, which is the smallest value among the candidates and therefore not part of the current top k. After all numbers are processed, the heap contains exactly the k largest values, and the root is the k-th largest.

Heap walkthrough

Use nums = [3,2,1,5,6,4] and k = 2. Start with an empty min-heap. See 3, heap becomes [3]. See 2, heap becomes [2,3]; the root 2 is the 2nd largest among values seen so far. See 1, push to get [1,3,2], then pop 1 because the heap is too large, returning to [2,3]. See 5, push to get [2,3,5], pop 2, and keep [3,5]. See 6, push to get [3,5,6], pop 3, and keep [5,6]. See 4, push to get [4,6,5], pop 4, and finish with [5,6]. The root 5 is the 2nd largest.

Algorithm

  1. Create a min-heap of integers.
  2. Scan every value in nums.
  3. Push the current value into the heap.
  4. If the heap size exceeds k, pop the root.
  5. After the scan, return the root because it is the smallest value inside the top-k set.

Solutions

Solution 1: Size-k min-heap

When to prefer this:

Use this when you want deterministic O(n log k) time, especially when k is much smaller than n or when values arrive as a stream.

Keep only the best k values in a min-heap. The heap root is the weakest value still retained, so removing the root whenever the heap becomes too large preserves exactly the largest k values.

Step-by-step

  1. Create an empty PriorityQueue using Java's natural min-heap ordering.
  2. Add each number from nums.
  3. If the heap size becomes greater than k, remove the smallest retained number.
  4. When the loop ends, return peek() because it is the smallest among the k largest values.
Time

O(n log k)

Space

O(k)

Each of n values may perform a heap push and sometimes a pop, while the heap size never exceeds k + 1.

Java implementation

Loading…

Solution 2: Quickselect by target index

When to prefer this:

Use this when the interviewer asks for average O(n) selection and the input can be rearranged in place.

The k-th largest value is the element that would land at index n - k in ascending order. Quickselect partitions the array around a pivot and continues only on the side that contains that target index.

Step-by-step

  1. Convert the request to target index nums.length - k.
  2. Partition the current range into values smaller than the pivot, equal to the pivot, and larger than the pivot.
  3. If the target index falls inside the equal band, return that value.
  4. If the target index is left of the equal band, search the left range; otherwise search the right range.
  5. Randomising the pivot keeps the expected running time linear, and the equal band handles duplicates cleanly.
Time

O(n) average, O(n^2) worst case

Space

O(1)

Each partition keeps only one side on average; the implementation mutates the input array in place.

Java implementation

Loading…

Dry Run

Sample input

nums = [3,2,1,5,6,4], k = 2. Track the size-k min-heap during the scan.

stepvalueheap after pushactionheap after trim
13[3]size <= k, keep it[3]
22[2,3]size <= k, keep it[2,3]
31[1,3,2]pop 1[2,3]
45[2,3,5]pop 2[3,5]
56[3,5,6]pop 3[5,6]
64[4,6,5]pop 4[5,6]

The heap finishes with the two largest values 5 and 6. Its root is 5, so the answer is 5.

Interview Tips

Say the confusion out loud: for k-th largest, the efficient fixed-size heap is a min-heap, because the smallest value among the retained top k is the answer. If the interviewer asks about faster average time, transition cleanly to quickselect and mention its worst-case risk unless pivot choice is controlled.

Likely follow-ups

  • How would the solution change for the k-th smallest element?
  • What if numbers arrive in an infinite stream and you need to query the k-th largest repeatedly?
  • How would you make quickselect deterministic in worst-case linear time?
  • What changes if the problem asks for the k-th distinct largest value?

Similar Problems

Top K Frequent Elements
MediumAlso keeps only k winners, but orders candidates by frequency.
K Closest Points to Origin
MediumUses a fixed-size heap and evicts the worst candidate.
Find K Closest Elements
MediumAnother top-k boundary problem with a tie-break rule.
Find Median from Data Stream
HardA streaming selection problem that maintains heap roots as boundaries.

Key Takeaways

  • A size-k min-heap is the standard heap pattern for k-th largest.
  • The heap root represents the weakest retained top-k candidate.
  • Duplicates count as separate positions unless the statement says distinct.
  • Quickselect is the average O(n) alternative when input mutation is allowed.
Reusable template: For k-th largest, scan once with a size-k min-heap; push each value, evict the smallest when over capacity, then return the root.