Retain Top K Elements
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a list of integers `nums` and an integer `k`, return a new list formed from the original list after removing every element except the `k` largest elements.
Requirements:
- Preserve the relative order of the retained elements from the original list.
- Duplicates are treated as separate elements.
- If multiple equal values are tied at the cutoff, keep the leftmost occurrences needed to retain exactly `k` elements.
- If `k <= 0`, return an empty list.
- If `k >= nums.length`, return the original list.
Example:
```text
nums = [5, 1, 3, 5, 2, 4], k = 3
The 3 largest elements are 5, 5, and 4.
Output: [5, 5, 4]
```
Example with a tie:
```text
nums = [4, 1, 4, 3, 4], k = 2
The cutoff value is 4. Keep the leftmost two occurrences of 4.
Output: [4, 4]
```
Quick Answer: This question evaluates array manipulation and order-statistics skills, specifically stable selection, handling duplicates with leftmost tie-breaking, and edge-case reasoning for k values and list bounds.
Given a list of integers `nums` and an integer `k`, return a new list formed by removing every element except the `k` largest elements.
Rules:
- Preserve the relative order of the retained elements from the original list.
- Duplicates are treated as separate elements.
- If multiple equal values are tied at the cutoff, keep the leftmost occurrences needed to retain exactly `k` elements.
- If `k <= 0`, return an empty list.
- If `k >= len(nums)`, return a copy of the original list.
Example:
- `nums = [5, 1, 3, 5, 2, 4]`, `k = 3` -> `[5, 5, 4]`
- `nums = [4, 1, 4, 3, 4]`, `k = 2` -> `[4, 4]`
Constraints
- 0 <= len(nums) <= 200000
- -10^9 <= nums[i] <= 10^9
- -10^9 <= k <= 10^9
Examples
Input: ([5, 1, 3, 5, 2, 4], 3)
Expected Output: [5, 5, 4]
Explanation: The 3 largest elements are 5, 5, and 4. Keeping them in original order gives [5, 5, 4].
Input: ([4, 1, 4, 3, 4], 2)
Expected Output: [4, 4]
Explanation: The cutoff value is 4. Three 4s exist, but only two should be kept, so keep the leftmost two occurrences.
Hints
- If you sort a copy of the array in descending order, the first `k` values tell you exactly which multiset of values must be kept.
- Use a frequency map for those top `k` values, then scan the original list from left to right and keep an element only while its remaining frequency is positive.