Kth Largest Element in an Array

Top K Frequent Elements

Redundant Connection

Return the kth largest value without requiring a fully sorted array.

Given an integer array `nums` and integer `k`, return the kth largest value in sorted order. Duplicates count as separate positions.

## Example
```
Input: {"nums":[3,2,1,5,6,4],"k":2}
Output: 5
```

**Constraints**
- 1 <= k <= nums.length <= 100000
- -10000 <= nums[i] <= 10000

**Follow-up**
Can you solve it in expected linear time with quickselect?

- Identify the required output and the state that changes.
- Use the examples to rule out tempting but incorrect interpretations.

Understand the Goal

- This problem is best exposed by Maintain a min-heap containing only the k largest values.
- Maintain only the state needed for the next operation.

Choose the Core Pattern

- Process each state once when possible.
- Record state before scheduling dependent work to avoid duplicates.

Build the Algorithm

- Verify the smallest input, impossible cases, and repeated values where allowed.
- Keep output ordering deterministic.

Check Edge Cases

- Time complexity is O(n log k).
- Space complexity is O(k).