Find k-th largest element in array
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an unsorted array of integers `nums` and a positive integer `k`.
Design an efficient algorithm to find the **k-th largest** element in the array. The k-th largest element is the element that would appear in position `len(nums) - k` if the array were sorted in non-decreasing order.
- Example:
- Input: `nums = [3, 2, 1, 5, 6, 4]`, `k = 2`
- Output: `5` (the sorted array is `[1, 2, 3, 4, 5, 6]`, so the 2nd largest is 5)
Assumptions and requirements:
- `1 <= k <= len(nums)`.
- The array may contain duplicate values.
- Aim for an algorithm with good **average-case** time complexity (better than fully sorting the array if possible).
Tasks:
1. Describe the algorithm you would use to find the k-th largest element, ideally using an in-place partitioning approach inspired by quicksort.
2. Write the core logic in code (in the language of your choice).
3. Analyze the **average-case time complexity** and **space complexity** of your algorithm, and briefly explain why the average-case complexity holds.
Quick Answer: This question evaluates array manipulation, selection algorithms, in-place partitioning techniques, and complexity analysis within the domain of coding and algorithms.
You are given an unsorted array of integers `nums` and a positive integer `k`. Return the k-th largest element in the array, where duplicates count as separate elements. In other words, if the array were sorted in non-decreasing order, you should return the value at index `len(nums) - k`.
You should aim for an efficient algorithm using an in-place partitioning strategy inspired by quicksort (Quickselect), rather than fully sorting the array.
Constraints
- 1 <= len(nums) <= 100000
- -1000000000 <= nums[i] <= 1000000000
- 1 <= k <= len(nums)
- The array may contain duplicate values
Examples
Input: ([3, 2, 1, 5, 6, 4], 2)
Expected Output: 5
Explanation: Sorted order is [1, 2, 3, 4, 5, 6], so the 2nd largest element is 5.
Input: ([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)
Expected Output: 4
Explanation: Sorted order is [1, 2, 2, 3, 3, 4, 5, 5, 6], so the 4th largest element is 4.
Hints
- The k-th largest element is the same as the element at index `len(nums) - k` in the array sorted in ascending order.
- Use a partition step like quicksort: place one pivot in its final sorted position, then continue only on the side that contains the target index.