Kth Largest Element In An Array
The briefingthe full drill, in my own words
The drill: Find the kth biggest value in an unsorted array — k=1 is the max, but any k should come back without fully sorting everything first.
An unsorted array of integers arrives along with a rank k, and the task is naming the kth biggest value if the whole array were sorted in descending order.
k=1 asks for the plain maximum, but any k in range should come back without necessarily sorting the entire array first — the array's own order is otherwise irrelevant, only the one answer matters.
Duplicate values are counted by position, not collapsed — a repeated value occupies its own separate slot in the ranking, the same as any other value would.
- k always falls within the array's length
- array sizes run up to tens of thousands of elements
- values can repeat and be negative, zero, or positive
- duplicates occupy separate ranks, not a single shared one
The hintstake only what you need
HINT 1 THE NUDGE
A full sort answers this immediately, but it also ranks every element the question never asked about — think about how little of the array actually decides the kth-largest answer.
HINT 2 THE STRUCTURE
Only the k largest values ever matter, and among just those k, the smallest one is exactly the answer being asked for.
HINT 3 ONE STEP FROM THE ANSWER
Keep a min-heap capped at size k as you scan the array: push each value, pop the smallest once the heap overflows past k. When the scan ends, the heap's top is the kth largest.
Coach's boardthe pattern, step by step
k=2. Scan once, keeping a min-heap capped at size 2 — its root always holds the 2nd largest seen so far.
The splitstwo paces, two languages
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
heap = []
for v in nums:
heapq.heappush(heap, v)
if len(heap) > k:
heapq.heappop(heap)
return heap[0]class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return sorted(nums, reverse=True)[k - 1]class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int v : nums) {
heap.offer(v);
if (heap.size() > k) {
heap.poll();
}
}
return heap.peek();
}
}class Solution {
public int findKthLargest(int[] nums, int k) {
int[] sorted = nums.clone();
Arrays.sort(sorted);
return sorted[sorted.length - k];
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED