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.

Hint: Separate selection from ordering

Locate the boundary between selected and unselected values first. The required output order only concerns the k selected occurrences.

Select and Order the Largest k Value Occurrences

Approach

Copy the input and select the ascending rank n-k, which separates the k largest occurrences into the final suffix. Use three-way partitioning into less than, equal to and greater than a pivot, narrowing only the part containing that rank. Equal values occupy a middle band, so duplicates neither disappear nor cause repeated one-element partitions. To avoid adversarial pivot behavior, choose a deterministic median-of-medians pivot: sort groups of at most five, move their medians into a prefix, recursively select the median of that prefix, then partition the active range. This guarantees a constant fraction can be discarded apart from a fixed-size remainder; the standard T(n)<=T(n/5)+T(7n/10+O(1))+O(n) recurrence yields worst-case O(n) selection. Only groups of at most five and the selected suffix are sorted, not the whole input unnecessarily. Finally sort the suffix descending and return exactly k values. The empty selection returns immediately; a full selection skips partitioning because all values are output. Total time is O(n+k log k) with O(n) copied storage and O(log n) selection recursion. A simpler randomized quickselect offers expected linear selection with less machinery but quadratic worst-case behavior; naive fixed pivots also admit quadratic examples. A size-k min-heap instead costs O(n log(k+1)) selection work and O(k) state, attractive for streaming or very small k. Full sorting costs O(n log n) and is simplest when all or nearly all values are needed.

• Time complexity: O(n + k log(k+1)) worst-case using median-of-medians selection
• Space complexity: O(n) copied input plus O(log n) selection stack and O(k) output