Kth Largest Element in an Array

Problem

Given an integer array nums and an integer k, return the kth largest element. (The kth largest is the one in sorted order at index n-k, not the kth distinct.)

Constraints

• 1 ≤ k ≤ nums.length ≤ 10⁵

Approach — Heaps / Top-K

This is a Heaps / Top-K problem. The idea: use a heap so the min, max, or top-k element stays reachable in O(log n) per operation. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n log k) time.

Solution code

Python

class Solution:
    def findKthLargest(self, nums, k):
        import heapq
        return heapq.nlargest(k, nums)[-1]

Java

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // Keep a min-heap of size k. After processing, the smallest
        // element in the heap IS the kth largest in nums.
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int num : nums) {
            heap.offer(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        return heap.peek();
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.