Kth Largest Element in an Array

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

LeetCode: Kth Largest Element in an Array

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

Example:

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

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

Hints

Hint 1

Think about using a heap. Do you want a min heap or max heap? And what size should it be?

Hint 2

Use a min heap of size k. Keep only the k largest elements. The smallest of those k elements (at the root) is your answer.

Hint 3

For each new element, if it's larger than the heap's minimum, replace the minimum with it. This maintains the k largest elements.