Misra-Gries Summary Pass

Problem

Run one full Misra-Gries pass with k - 1 counters and return the surviving counters.

Increment a tracked item, add a new item while fewer than k - 1 items are tracked, and otherwise decrement every counter by one, dropping any that reach zero. Return a dict mapping surviving items to counts; k <= 0 returns an empty dict.

Hint

The decrement step charges one unit against every tracked candidate when a new item cannot fit.

Test cases

case 1

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

expected: {"a":2,"b":1}

case 2

in: [["x","y","x","z"],2]

expected: {}

case 3

in: [[],3]

expected: {}

case 4

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

expected: {"a":3}

case 5

in: [["p","q","r","p","q","r","p"],4]

expected: {"p":3,"q":2,"r":2}

Starter codePython

def misra_gries_summary(items, k):
    # Your code here
    pass

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