Top-K Heavy Hitters Space-Saving Step

Problem

Run the Space-Saving algorithm to find heavy hitters in a stream.

Maintain at most k counters. A tracked item increments its counter; an untracked item fills a free counter when one exists, otherwise it evicts the counter with the smallest count and takes over that count plus one (ties broken by the lexicographically smallest item).

Return the final counters as [item, count] pairs sorted by count descending then item ascending.

Hint

The evicting item inherits the victim's count, giving an upper bound on its true frequency.

Test cases

case 1

in: [["a","b","a","c","a","b"],2]

expected: [["a",3],["b",3]]

case 2

in: [["x"],1]

expected: [["x",1]]

case 3

in: [[],3]

expected: []

case 4

in: [["a","b","c","d"],2]

expected: [["c",2],["d",2]]

Starter codePython

def space_saving(stream, k):
    # Your code here
    pass

4 test cases · run your code against them in the editor