Select the K-th Largest Value from an Unsorted Array Without a Heap
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an unsorted array of integers and an integer `k`, return the `k`-th largest value in the array. Duplicates count separately: the answer is the value at position `k` (counting from 1) when the array is sorted from largest to smallest.
### Function Signature
```python
def kth_largest(nums: list[int], k: int) -> int:
```
`nums` is the array, in any order. `k` selects which largest value to return.
### Rules
- Equal values are not merged. In `[5, 5, 3]` the first and second largest values are both 5, and the third largest is 3.
- Do not use a heap or priority queue, including Python's `heapq` module; the interviewer ruled them out.
- The interviewer pressed for the optimal time complexity, so aim for the best bound you can achieve and be ready to justify it. Hidden tests include arrays that are already sorted and arrays with many repeated values.
### Constraints
- `1 <= k <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
### Examples
**Example 1**
```text
Input: nums = [7, 2, 9, 4, 9, 1], k = 2
Output: 9
```
Sorted from largest to smallest the array is `[9, 9, 7, 4, 2, 1]`. The second entry is 9, because the two 9s count separately.
**Example 2**
```text
Input: nums = [7, 2, 9, 4, 9, 1], k = 4
Output: 4
```
The fourth entry of `[9, 9, 7, 4, 2, 1]` is 4.
**Example 3**
```text
Input: nums = [-5, 0, -5, 3], k = 3
Output: -5
```
Sorted from largest to smallest the array is `[3, 0, -5, -5]`, and the third entry is -5.
Overview: Return the k-th largest value in an unsorted integer array, counting duplicates separately, without using a heap or priority queue, and aim for the best achievable time complexity. The coding question tests selection faster than sorting, handling of repeated values, and performance on adversarial inputs.
Given an unsorted array of integers `nums` and an integer `k`, return the `k`-th largest value in the array. Duplicates count separately: the answer is the value at position `k` (counting from 1) when `nums` is sorted from largest to smallest.
`nums` may be in any order, and `k` selects which largest value to return. Return that value as a single integer.
### Rules
- Equal values are not merged. In `[5, 5, 3]` the first and second largest values are both 5, and the third largest is 3.
- Do not use a heap or priority queue, including Python's `heapq` module; the interviewer ruled them out.
- The interviewer pressed for the optimal time complexity, so aim for the best bound you can achieve and be ready to justify it. Hidden tests include arrays that are already sorted and arrays with many repeated values.
### Constraints
- `1 <= k <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
- Every input value and the returned value fit in a signed 32-bit integer (none exceeds 2^31-1), so Java and C++ use `int`.
### Examples
**Example 1**
```text
Input: nums = [7, 2, 9, 4, 9, 1], k = 2
Output: 9
```
Sorted from largest to smallest the array is `[9, 9, 7, 4, 2, 1]`. The second entry is 9, because the two 9s count separately.
**Example 2**
```text
Input: nums = [-5, 0, -5, 3], k = 3
Output: -5
```
Sorted from largest to smallest the array is `[3, 0, -5, -5]`, and the third entry is -5.
Constraints
- 1 <= k <= len(nums) <= 10^5
- -10^9 <= nums[i] <= 10^9
- Every input value and the result fit in a signed 32-bit integer (none exceeds 2^31-1).
- Do not use a heap or priority queue (including Python's heapq module).
Examples
Input: ([42], 1)
Expected Output: 42
Explanation: Minimum valid input: a singleton array with k = 1 returns its only element.
Input: ([7, 2, 9, 4, 9, 1], 2)
Expected Output: 9
Explanation: Source Example 1: sorted descending is [9, 9, 7, 4, 2, 1]; the two 9s count separately, so the answer is 9, not the second distinct value 7.
Hints
- Duplicates count separately: picture nums sorted from largest to smallest and ask which single position k points to (in [5, 5, 3], k = 2 is still 5).
- You only need the value that would land at one sorted position, not the whole array in order; consider how much work that really requires.
- Hidden tests include already-sorted arrays and arrays with many repeated values, so check that your approach does not slow down on either.