Find top-K frequent values with tiebreaks

Question

Given an integer array nums and an integer k, return the k values with the highest frequency. The array can contain up to 10^6 elements.

When multiple values share the same frequency, break ties deterministically:

1. First by smaller numeric value (for string inputs, break ties lexicographically instead).
2. Then by earlier first-occurrence index in the array.

Your solution should address all of the following:

1. Return the correct k values under the tie-breaking rules above. If k exceeds the number of distinct values, return all of the distinct values.
2. Provide an algorithm faster than O(n log n) — for example O(n) or O(n log k) — and justify why it stays correct under the tie rules.
3. Discuss and compare the trade-offs among the main approaches: bucket counting by frequency, a size-k heap, and a selection/quickselect-based partition. State the time and space complexity of each.
4. Follow-up: For an array of length n, derive the maximum possible number of distinct frequency values achievable across its unique elements, and justify your formula.
5. Follow-up: How would you validate and guard against invalid inputs (e.g. non-integer elements, negative or non-integer k, an extremely large n) while keeping the service robust?

Find top-K frequent values with tiebreaks

Given an integer array nums and an integer k, return the k values with the highest frequency.

When multiple values share the same frequency, break ties deterministically:

1. First by smaller numeric value.
2. Then by earlier first-occurrence index in the array.

Rules:

• Return the result as a list ordered from highest rank to lowest under the rules above (frequency descending, then smaller value, then earlier first occurrence).
• If k is greater than or equal to the number of distinct values, return all of the distinct values (still in ranked order).
• If k <= 0, return an empty list.

Aim for an algorithm faster than O(n log n) overall (counting is O(n); only the relevant tie tiers need ordering).

Constraints

• 0 <= len(nums) <= 10^6
• Elements are integers (may be negative).
• k may be 0, negative, or larger than the number of distinct values.
• If k <= 0, return [].
• If k >= number of distinct values, return all distinct values in ranked order.

Examples

Example 1

Input: ([1, 1, 1, 2, 2, 3], 2)
Output: [1, 2]

Explanation: Frequencies: 1->3, 2->2, 3->1. Top 2 by frequency are 1 then 2.

Example 2

Input: ([4, 4, 5, 5, 6], 2)
Output: [4, 5]

Explanation: 4 and 5 both have frequency 2; tie broken by smaller value (4 before 5). 6 has frequency 1.

Hints

1. Count each value's frequency in one O(n) pass, and record its first-occurrence index in the same pass.
2. Define a single total order over the distinct values: frequency descending, then smaller numeric value, then earlier first-occurrence index. Sort or select by that key.
3. Two distinct integers can never be equal, so the first-occurrence tiebreak only ever resolves ties between a value's own equal keys — it is a stable secondary key, harmless to keep.
4. For an O(n)-style speedup over O(n log n), bucket values by frequency (buckets[f] = values seen f times) and walk buckets from high frequency to low, ordering only the tier you are currently emitting from.
5. Handle k <= 0 (return []) and k >= distinct count (return all distinct, still ranked) as explicit branches.

Solution

Count frequencies in O(n), then select the top k by a fully-specified total order: frequency descending, then smaller value, then earlier first-occurrence index (lexicographic for strings). Bucket-counting by frequency gives O(n) time / O(n) space and is the headline approach; a size-k min-heap gives O(n log k) with O(k) space (best when k << n); quickselect gives expected-linear selection but is non-stable so needs an explicit total-order comparator. If k exceeds the number of distinct values, return all uniques. Follow-up 1: the max count of distinct frequencies is floor((sqrt(8n+1)-1)/2), from 1+2+...+m <= n. Follow-up 2: validate k (non-integer/negative/zero, clamp when too large) and elements at the boundary, stream input, and cap memory for huge n.

Approach

The task decomposes into three stages: (1) count frequencies, (2) select the top k by frequency, and (3) impose the deterministic tie-break order. Counting is unavoidably O(n). The interesting part is doing selection in better than O(n log n) while still honoring the tie rules.

Define a total order on candidate values that the whole solution sorts/selects by, so "top-k" is unambiguous:

Value x ranks higher than value y if freq[x] > freq[y], OR (freq[x] == freq[y] AND x < y), OR (freq[x] == freq[y] AND x == y is impossible since values are distinct keys). For strings, replace x < y with lexicographic comparison.

The second tie-break (earlier first-occurrence index) only matters when two different values have both equal frequency AND equal numeric value, which cannot happen — distinct values are distinct numbers. So in the pure-integer case the first-occurrence rule is effectively redundant and is included to fully specify behavior; it becomes load-bearing only if values are compared by some coarser key (e.g. case-insensitive strings) where two distinct keys can compare equal. Handle it by storing each value's first-occurrence index during the counting pass and using it as the final comparator field.

Reference implementation (bucket counting, O(n))

from collections import defaultdict

def topKFrequent(nums, k):
    if k <= 0:
        return []
    freq = defaultdict(int)
    first_idx = {}
    for i, x in enumerate(nums):
        freq[x] += 1
        if x not in first_idx:
            first_idx[x] = i

    if k >= len(freq):
        # k exceeds the number of distinct values -> return all of them,
        # still in the well-defined ranked order.
        candidates = list(freq)
        candidates.sort(key=lambda x: (-freq[x], x, first_idx[x]))
        return candidates

    # Bucket by frequency: bucket[f] holds all values seen exactly f times.
    n = len(nums)
    buckets = [[] for _ in range(n + 1)]
    for x, f in freq.items():
        buckets[f].append(x)

    result = []
    # Walk buckets from highest frequency to lowest.
    for f in range(n, 0, -1):
        if not buckets[f]:
            continue
        # Within a frequency tier, apply tie-breaks: smaller value, then
        # earlier first-occurrence index.
        buckets[f].sort(key=lambda x: (x, first_idx[x]))
        for x in buckets[f]:
            result.append(x)
            if len(result) == k:
                return result
    return result

Why this is correct and meets the speed bound

• Counting and bucketing are O(n). Frequencies are integers in [1, n], so bucket counting is an exact distribution sort over the frequency key with no comparison log factor.
• We collect values strictly in descending frequency order, so the first k we emit are exactly the k highest-frequency values.
• Within a single frequency tier we sort that tier by (value, first_index) to enforce the tie rules. The total work of these per-tier sorts is bounded by sorting the distinct values that actually tie; in the worst case (all distinct values share one frequency) this degrades to O(d log d) over d distinct values, but in practice ties are small and the dominant term is the O(n) count. If a strict O(n) worst case is required even under pathological ties, replace the per-tier comparison sort with a radix/counting sort on the value key (when values are bounded integers).

Approach trade-offs

• Bucket counting (above): O(n) time, O(n) space. Best asymptotics; needs O(n) buckets. Tie-breaks handled per tier. Ideal for n up to 10^6.
• Size-k min-heap: push each (freq, tie-key) and keep the heap at size k, evicting the smallest. O(d log k) time (d = distinct values), O(k) space. Wins when k is tiny relative to n and memory is tight; comfortably beats O(n log n) as O(n log k). The heap comparator must encode the full ranked order so evictions respect the tie rules.
• Quickselect / partition: partition the d distinct values around the k-th best by the ranked key in expected O(d) time, then sort just the chosen k (O(k log k)) if an ordered output is required. Expected linear, but worst-case O(d^2) and not stable, so tie-breaks need an explicit total-order comparator (no equal keys) to stay deterministic.

Rule of thumb: bucket counting for the asymptotically-best O(n); the size-k heap when k << n and you want bounded memory; quickselect when you want expected-linear selection and can afford a non-stable partition.

Follow-up 1: maximum number of distinct frequency values

We want the largest set of distinct positive frequencies {f_1, f_2, ...} that can be realized by the unique elements of an array of length n, where the frequencies must sum to at most n (each element occurs f_i >= 1 times and total occurrences = n).

To maximize the count of distinct frequencies, use the smallest distinct positive integers: 1 + 2 + 3 + ... + m <= n. The largest such m satisfies m(m+1)/2 <= n, giving

max distinct frequencies = floor((sqrt(8n + 1) - 1) / 2).

Any leftover count n - m(m+1)/2 can be absorbed by bumping the largest frequency, which does not change the number of distinct frequencies. Example: for n = 10, 1+2+3+4 = 10, so up to 4 distinct frequency values; for n = 6, 1+2+3 = 6, up to 3.

Follow-up 2: input validation and robustness

Validate at the service boundary and fail fast with clear errors rather than corrupting the count:

• k: reject non-integer or negative k; treat k == 0 as an empty result; clamp k to the number of distinct values (return all uniques) rather than erroring when k is merely large.
• Elements: if the contract is integers (or strings), reject or coerce non-conforming elements; never let a stray type silently change the hash/equality semantics of the frequency map.
• Scale: for extremely large n, guard memory (the O(n) bucket array and the frequency map are both O(n)); stream the input in one pass so you never hold two copies, and consider a configurable size cap / backpressure so a hostile input can't exhaust memory.
• General: validate before allocation, return typed errors, and add a fast path for empty input. Property-test the comparator (antisymmetry/transitivity) so the tie order is provably total.