LeetCode 215 Kth Largest Element in an Array - Problem Statement

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

With [3, 2, 1, 5, 6, 4] and k = 2, the answer is 5. Sorted: [6, 5, 4, 3, 2, 1]. The 2nd largest is 5.

With [3, 2, 3, 1, 2, 4, 5, 5, 6] and k = 4, the answer is 4. Note: duplicate values count separately.

Can you solve this without fully sorting the array?

Constraints: $1 \le k \le n \le 10^5$.