0215.md

215. Kth Largest Element in an Array

Level:

Topic:

Question

Given an integer array nums and an integer k, return the kth largest element in the array.

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Intuition

Keep a min heap of size k, whenever heap is > k, it will remove the smallest and remains the largest. Lastly, the first remove value from heap is the kth largest.

Code

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

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();

    for (int num: nums) {
        pq.add(num);
        if (pq.size() > k)
            pq.poll();
    }

    return pq.peek();
}