Space-Saving Stream Summary

Problem

Summarize a stream with the Space-Saving algorithm and return the tracked items sorted by estimated count.

Tracked items increment; new items fill free capacity; once full, the item with the smallest (count, name) pair is evicted and the new item inherits its count plus one. Return a list of [item, count] pairs ordered by descending count then item name; capacity <= 0 returns [].

Hint

The replacement count carries the evicted item's count forward, which upper-bounds new items.

Test cases

case 1

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

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

case 2

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

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

case 3

in: [[],3]

expected: []

case 4

in: [["x","x","y"],1]

expected: [["y",3]]

case 5

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

expected: []

Starter codePython

def space_saving_summary(items, capacity):
    # Your code here
    pass

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