majority.py

from collections import defaultdict

def _maj(counts_to_items, items_to_counts, max_count, sequence):
    if not sequence:
        return counts_to_items, items_to_counts, max_count, sequence
    item, new_sequence = sequence[0], sequence[1:]
    count = items_to_counts[item]
    counts_to_items[count].discard(item)
    count += 1
    counts_to_items[count].add(item)
    items_to_counts[item] = count
    if count > max_count:
        max_count = count
    return counts_to_items, items_to_counts, max_count, new_sequence

def major(sequence):
    counts_to_items = defaultdict(set)
    items_to_counts = defaultdict(int)
    max_count = 0

    while sequence:
        counts_to_items, items_to_counts, max_count, sequence = _maj(
                counts_to_items, items_to_counts, max_count, sequence)
    return counts_to_items[max_count].pop()