087. Top K Frequent Values

Why this mechanism works

Count first, then rank distinct candidates. A bounded min-heap retains the best k by a key where larger is better: (frequency,-first_index). The negative index makes earlier appearances stronger. Sorting only the final heap gives the specified output order.

State and boundaries

counts and first contain complete statistics. heap stores the strongest at-most-k distinct candidates under the two-part ranking key.

Protocol

1. Count frequencies and first indices.
2. Push each distinct candidate with its ranking key.
3. Evict the weakest when size exceeds k.
4. Sort retained keys descending.
5. Return their values.

Visualization

nums: 2,1,2,1,3
keys: 2 -> (2,0), 1 -> (2,-1), 3 -> (1,-4)
frequency tie favors value 2

Python implementation

import heapq

def top_k_frequent(nums, k):
    if k <= 0:
        return []
    counts, first = {}, {}
    for i, value in enumerate(nums):
        counts[value] = counts.get(value, 0) + 1
        first.setdefault(value, i)
    heap = []
    for value, count in counts.items():
        heapq.heappush(heap, (count, -first[value], value))
        if len(heap) > k:
            heapq.heappop(heap)
    return [value for count, position, value in sorted(heap, reverse=True)]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 top_k_frequent: if k <= 0:
nums=[2, 1, 2, 1, 3]; k=2

L6 top_k_frequent: counts, first = {}, {}
nums=[2, 1, 2, 1, 3]; k=2; counts={}; first={}

L7 top_k_frequent: for i, value in enumerate(nums):
nums=[2, 1, 2, 1, 3]; k=2; counts={}; first={}; i=0; value=2

L8 top_k_frequent: counts[value] = counts.get(value, 0) + 1
nums=[2, 1, 2, 1, 3]; k=2; counts={2:1}; first={}; i=0; value=2

L9 top_k_frequent: first.setdefault(value, i)
nums=[2, 1, 2, 1, 3]; k=2; counts={2:1}; first={2:0}; i=0; value=2

L7 top_k_frequent: for i, value in enumerate(nums):
nums=[2, 1, 2, 1, 3]; k=2; counts={2:1}; first={2:0}; i=1; value=1

L8 top_k_frequent: counts[value] = counts.get(value, 0) + 1
nums=[2, 1, 2, 1, 3]; k=2; counts={2:1, 1:1}; first={2:0}; i=1; value=1

L9 top_k_frequent: first.setdefault(value, i)
nums=[2, 1, 2, 1, 3]; k=2; counts={2:1, 1:1}; first={2:0, 1:1}; i=1; value=1

... 14 intermediate state changes omitted ...

L14 top_k_frequent: heapq.heappop(heap)
nums=[2, 1, 2, 1, 3]; k=2; counts={2:2, 1:2, 3:1}; first={2:0, 1:1, 3:4}; i=4; value=3; heap=[(2, -1, 1), (2, 0, 2)]; count=1

L15 top_k_frequent: return [value for count, position, value in sorted(heap, reverse=True)]
nums=[2, 1, 2, 1, 3]; k=2; counts={2:2, 1:2, 3:1}; first={2:0, 1:1, 3:4}; i=4; value=2; heap=[(2, -1, 1), (2, 0, 2)]; count=2; position=0

L15 top_k_frequent: return [value for count, position, value in sorted(heap, reverse=True)]
nums=[2, 1, 2, 1, 3]; k=2; counts={2:2, 1:2, 3:1}; first={2:0, 1:1, 3:4}; i=4; value=1; heap=[(2, -1, 1), (2, 0, 2)]; count=2; position=-1

L15 top_k_frequent: return [value for count, position, value in sorted(heap, reverse=True)]
nums=[2, 1, 2, 1, 3]; k=2; counts={2:2, 1:2, 3:1}; first={2:0, 1:1, 3:4}; i=4; value=3; heap=[(2, -1, 1), (2, 0, 2)]; count=1

L4 top_k_frequent: if k <= 0:
nums=[1, 1, 2]; k=5

L6 top_k_frequent: counts, first = {}, {}
nums=[1, 1, 2]; k=5; counts={}; first={}

L7 top_k_frequent: for i, value in enumerate(nums):
nums=[1, 1, 2]; k=5; counts={}; first={}; i=0; value=1

L8 top_k_frequent: counts[value] = counts.get(value, 0) + 1
nums=[1, 1, 2]; k=5; counts={1:1}; first={}; i=0; value=1

L9 top_k_frequent: first.setdefault(value, i)
nums=[1, 1, 2]; k=5; counts={1:1}; first={1:0}; i=0; value=1

L7 top_k_frequent: for i, value in enumerate(nums):
nums=[1, 1, 2]; k=5; counts={1:1}; first={1:0}; i=1; value=1

L8 top_k_frequent: counts[value] = counts.get(value, 0) + 1
nums=[1, 1, 2]; k=5; counts={1:2}; first={1:0}; i=1; value=1

L7 top_k_frequent: for i, value in enumerate(nums):
nums=[1, 1, 2]; k=5; counts={1:2}; first={1:0}; i=2; value=2

... 6 intermediate state changes omitted ...

L12 top_k_frequent: heapq.heappush(heap, (count, -first[value], value))
nums=[1, 1, 2]; k=5; counts={1:2, 2:1}; first={1:0, 2:2}; i=2; value=2; heap=[(1, -2, 2), (2, 0, 1)]; count=1

L15 top_k_frequent: return [value for count, position, value in sorted(heap, reverse=True)]
nums=[1, 1, 2]; k=5; counts={1:2, 2:1}; first={1:0, 2:2}; i=2; value=1; heap=[(1, -2, 2), (2, 0, 1)]; count=2; position=0

L15 top_k_frequent: return [value for count, position, value in sorted(heap, reverse=True)]
nums=[1, 1, 2]; k=5; counts={1:2, 2:1}; first={1:0, 2:2}; i=2; value=2; heap=[(1, -2, 2), (2, 0, 1)]; count=1; position=-2

L15 top_k_frequent: return [value for count, position, value in sorted(heap, reverse=True)]
nums=[1, 1, 2]; k=5; counts={1:2, 2:1}; first={1:0, 2:2}; i=2; value=2; heap=[(1, -2, 2), (2, 0, 1)]; count=1

Why the solution is correct

The ranking key exactly represents the stated priority. Bounded-heap eviction preserves the top k keys after each candidate. Sorting those winners by the same key gives descending frequency with the required earliest-appearance tie rule.

Time and space

O(n+u log(k+1)+k log k) expected time and O(u+k) space, with output size capped at u distinct values.

Common mistakes

Counting and selecting individual occurrences duplicates output values. A value-based tie breaker silently changes first-appearance semantics.

Reasoning card

Transfer exercise

Use frequency buckets instead of a heap, retaining the same deterministic tie order.