Misra-Gries Decrement

Problem

Run the Misra-Gries algorithm with k-1 counters.

For each stream item, increment its counter when present, add a new counter when fewer than k-1 exist, and otherwise decrement every counter by one, dropping any that reach zero. The surviving counters are candidates for items occurring more than n/k times.

Return the surviving counters as [item, count] pairs sorted by item.

Hint

A full table triggers a global decrement instead of a new counter.

Test cases

case 1

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

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

case 2

in: [["x"],2]

expected: [["x",1]]

case 3

in: [[],3]

expected: []

case 4

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

expected: []

Starter codePython

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

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