Find the Largest K Elements with Partitioning

Return the largest k values from an array, preserving duplicate occurrences. Compare a heap solution with a partition-based selection approach and explain when each is attractive.

Implement largest_k(values: int[], k: int) -> int[]. Return the selected values in nonincreasing order. The sorted output is a practice presentation convention; the selection itself should not require sorting the entire array.

Constraints & Assumptions

• 0 <= len(values) <= 200000, 0 <= k <= len(values), and values lie in signed 32-bit range.
• Duplicate values count separately. Return exactly k values; no distinct-value deduplication.
• k=0 returns an empty list. k equal to the input length returns all values sorted descending.
• The input may be modified internally, or copied if you state the additional memory cost.
• Aim for expected O(n + k log k) time using selection plus output sorting. Discuss worst-case behavior rather than claiming a naive quickselect implementation is always linear.

Examples

values = [7,1,9,9,3], k = 3
result = [9,9,7]

values = [-4,-1,-3], k = 1
result = [-1]

The reported interview discussed a heap but preferred quickselect/quicksort-style partitioning. Explain pivot choice, duplicate handling, how the selected partition is identified, and why only that partition needs output sorting. Compare with O(n log k) heap work and full sorting, including streaming or very small-k cases.