1958. The k Most Frequent So Far

Values arrive one at a time and are never removed. At any point you must be able to list the k most frequent so far.

add x one more occurrence of x arrives top list the k most frequent values so far, most frequent first

## What every operation prints

Every operation prints exactly one line.

• add x prints x's new count.
• top prints the values on one line separated by single spaces, most frequent
• first. If fewer than k distinct values have arrived, it prints all of them.
• If none have arrived, it prints none.

Where two values have the same count, the one that FIRST arrived earlier comes first. Not the smaller value: the earlier arrival.

That tie rule is deliberately different from problem 295, which is the same question over a fixed array and breaks ties by the smaller value. The rule there exists because a hash map has no iteration order to lean on; the rule here exists because arrival order is information a stream has and an array does not. Running the two side by side on the same multiset gives different output, which is the point.

``` k = 2

top -> none add 5 -> 1 add 7 -> 1 top -> 5 7 both have count 1, and 5 arrived first add 7 -> 2 top -> 7 5 7 now leads on count add 5 -> 2 top -> 5 7 tied again at 2, so first arrival decides ```

## What most people try first

Sort the distinct values on every top. Correct, and O(D log D) per query with D distinct values, so 200000 queries cost far too much.

A heap of (count, value) does not work for the reason given in problem 1956: the count changes while the entry sits inside the heap. Here, though, something is true that was not true there, and it is the key to the problem.

## Counts only ever RISE

Nothing is removed. So a value that is not in the top k can only get in by being added, and at the moment it is added we are already looking at it.

That gives an incremental rule. Keep the top k as a short sorted list:

``` TOP at most k values, best first cnt[x] how many times x has arrived first[x] the index of x's first arrival

add x: cnt[x] += 1 if x is in TOP: nothing to admit else if |TOP| < k: append x else: let w be the WORST member of TOP if x now beats w, replace w with x re-sort TOP at most k elements ```

## Why it is correct

The claim is that TOP always holds the best k values by (count descending, first arrival ascending).

Suppose it holds before an add x. Only cnt[x] changed, and it increased, so the only value whose standing improved is x. Every other value's relative order is unchanged. If x was already in TOP, the set of the best k cannot have lost a member and x can only have moved up, so re-sorting is enough. If x was outside, then the only way the best k changes is for x to enter, displacing the worst current member, which is exactly what the rule checks.

The argument relies completely on counts never falling. The moment a removal is allowed, a value outside TOP can become eligible without being touched, and nothing short of a full re-examination finds it. Problem 1959 is that problem.

## The boundary that breaks a careless implementation

Admitting a value only while TOP has room. A value that starts outside a full TOP then never gets in however often it arrives, which passes every test with at most k distinct values.

The second is the tie. Comparing by value rather than by first arrival gives the answer to problem 295 instead of to this one, and the two agree whenever the values happen to arrive in increasing order.

The third is a tie at the boundary of TOP. A value equal on count to the worst member enters only if it arrived FIRST earlier, so the comparison is on the pair and not on the count alone.

## Overflow

A value reaches 1000000000, which fits in a signed 32 bit integer since the limit is 2147483647. Counts and arrival indices are bounded by q, so at most 200000. Nothing is multiplied.

## Cost

O(k) per add and O(k) per top, with k at most 10, so O(qk) overall, and O(D) memory. The judge cannot enforce the per-operation bound, so sorting every distinct value on each top passes every declared test.

Constraints - `1 ≤ k ≤ 10` - `1 ≤ q ≤ 200000` - `1 ≤ x ≤ 1000000000` - `add` and `top` each run in `O(k)` - the judge cannot enforce that: the declared tests are small and there is no test generator yet, so sorting every distinct value on each `top` passes them while doing about `3 * 10^11` comparisons at the stated limits