Practice Kth Largest Element in an Array
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Kth Largest Element in an Array
Problem Statement
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?
Source: Kth Largest Element in an Array on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
nums = [3,2,1,5,6,4], k = 2
5
# Example 2
nums = [3,2,3,1,2,4,5,5,6], k = 4
4
Constraints
How to solve Kth Largest Element in an Array
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
Only the element at index n-k of the sorted order matters; one partition step places a pivot at its final position and reveals which side holds that index, so quickselect discards the other side and averages linear time.
Why brute force is not enough
Sorting the whole array and reading index n-k is O(n log n), about 1.7 * 10^6 steps for n up to 10^5, which passes but ignores the hint to avoid sorting; extracting the maximum k times is O(n * k), quadratic when k is near n.
Approach
- Translate the kth largest into the element at index n-k of the ascending order; this target index never changes while the search range shrinks.
- Pick a pivot in the current range, preferably at random, and partition so smaller values are left of it and larger values right, placing the pivot at its final sorted index.
- If the pivot's index equals the target, return it; if the target is smaller, repeat on the left part, otherwise on the right part. Only one side is ever explored.
- Stop when the range holds a single element, which must be the answer.
- Alternatively, keep a min-heap of the k largest values seen, evicting the minimum whenever it exceeds size k; its root at the end is the answer in O(n log k).
Walkthrough of Example 1
nums = [3,2,1,5,6,4], k = 2 → 5
- n is 6 and k is 2, so the target is index 4 of the sorted order.
- With 4 as the pivot, partitioning moves 3, 2, 1 to its left and 5, 6 to its right, so the pivot lands at index 3.
- Index 3 is below the target 4, so continue on indices 4 and 5, which hold 5 and 6.
- With 6 as the pivot, 5 is smaller, so 6 settles at index 5; the target lies to its left.
- The range is now the single index 4 holding 5, so the answer is 5.
Time and space
Time O(n) average, O(n^2) worst case · Space O(1). n is nums.length; each partition is linear and a random pivot shrinks the expected range geometrically, while in-place partitioning needs only constant extra memory when written iteratively.
Interview pitfalls
- Confusing kth largest with kth smallest, or using index k instead of n-k, which returns a plausible wrong value.
- Duplicates: example 2 repeats 3, 2, and 5 and expects 4 for k equal to 4, so equal elements count individually; a three-way partition keeps them from degrading performance.
- Always picking the first or last element as the pivot, which turns sorted or all-equal inputs into O(n^2).
- Recursing into both halves after partitioning, which turns quickselect back into quicksort.
Follow-up questions interviewers ask
- How would you find the kth largest in a stream where you cannot store every element?
- Can you guarantee linear worst-case time, and what does median-of-medians cost in practice?
Further reading on the technique: Quickselect
Related LeetCode Problems
Practice more problems similar to Kth Largest Element in an Array.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.