Find the K Most Frequent Values

Given a nonempty integer array and an integer `k`, return any valid collection of the `k` distinct values with the highest occurrence frequencies. A selected value's frequency must be at least as high as every unselected value's frequency. If several values tie at the selection boundary, any choice of the required number of tied values is valid. The order of the returned values does not matter. ### Constraints & Assumptions - Frequency counts occurrences in the input, not numeric magnitude. - Return each selected value once even if it occurs many times. - The source gives no tie-breaking rule or uniqueness guarantee; do not impose numeric order as a selection requirement. - **Practice input convention:** `1 <= k <= d`, where `d` is the number of distinct input values. The array is nonempty and contains integers. No numeric magnitude or length limit is supplied. - Compare approaches in terms of input length `n`, distinct-value count `d`, and `k`. ### Illustrative Example For `[1, 1, 2, 2, 3]` with `k = 1`, either `[1]` or `[2]` is valid because both values occur twice. `[3]` is invalid because a value with greater frequency is excluded. With `k = 2`, the selected set must be `{1, 2}`, in either order. ### Clarifying Questions to Ask - Can the kth-highest frequency be shared by several values? This exercise permits such ties and accepts any valid selection. - Is input mutation allowed, and is memory usage more constrained than running time? - Is `k` guaranteed to be valid? Use the stated practice convention here. ```hint Separate counting from selection Once each distinct value has a frequency, repeated input occurrences no longer need to compete individually for the k output positions. ``` ### What a Strong Answer Covers - A frequency map over distinct values and a selection method that returns exactly k of them. - Correct handling of boundary ties without an invented numeric tie-break requirement. - A proof that no unselected value has greater frequency than a selected value. - Time and space trade-offs for a bounded heap, frequency buckets, or another justified method. ### Follow-up Questions - How would your choice change when k is much smaller than the number of distinct values? - Why is a frequency bucket array bounded by n even when the integer values themselves are very large? - How can a checker validate an arbitrary tied answer without comparing it to one fixed ordered list?