Elements Appearing More Than n/k Times

Elements Appearing More Than n/k Times generalizes the classic majority-element problem. Instead of one value that occupies more than half the array, we hunt for every value that occupies more than a 1/k share — and we do it with a clever voting trick that uses only a constant number of counters.

The slow way first

The obvious idea: count everything. Walk the array, tally each value in a hash map, then return every key whose tally is above n/k. That is O(n) time but O(n) extra space — the map can hold every distinct value.

Can we do better on space? The question to ask: how many values can possibly clear the bar? If a value appears more than n/k times, you can fit at most k − 1 such values before their counts would sum past n. So the answer never has more than k − 1 elements — and that cap is the whole reason a constant-space trick exists.

The idea: generalized Boyer-Moore voting

The classic majority trick keeps one (candidate, count) slot and cancels opposing votes. Generalize it to k − 1 slots. As we scan, for each value num we do exactly one of three things:

When a count hits 0 its slot frees up. After the pass, the k − 1 slots hold the only possible answers — but voting can leave false positives, so a second pass re-counts each survivor and keeps just the ones whose true frequency exceeds n/k.

Walk through it

Step through the animation with nums = [3, 1, 2, 2, 1, 2, 3, 3] and k = 3 (so 2 slots). The pointer i scans left to right and the counts slots fill, drain, and reset:

• 3 and 1 each grab a slot. Then 2 finds no free slot, so all counts drop — 3 and 1 both hit 0 and vanish.
• 2 and 1 grab the freed slots; the next 2 matches and bumps to count 2.
• A 3 with no free slot decrements all again — 1 falls out, 2 survives. The final 3 takes the open slot.
• Survivors are {2, 3}. The second pass counts each in the full array: both appear 3 times, both clear the threshold of 2, so the answer is [2, 3].

Pseudocode

counts = empty map           # at most k-1 (value -> running count) slots
for num in nums:
    if num is already a candidate:
        counts[num] += 1
    else if fewer than k-1 candidates so far:
        counts[num] = 1                 # claim a free slot
    else:
        for every candidate c:
            counts[c] -= 1              # cancel one vote each
            if counts[c] == 0: drop c   # free that slot
res = []
for c in counts:                        # second pass: verify
    if real count of c in nums > n // k:
        res.append(c)
return res

The Python solution

def majority_n_k(nums, k):
    counts = {}
    for num in nums:
        if num in counts:
            counts[num] += 1
        elif len(counts) < k - 1:
            counts[num] = 1
        else:
            for c in list(counts):
                counts[c] -= 1
                if counts[c] == 0:
                    del counts[c]
    res = []
    for c in counts:
        if nums.count(c) > len(nums) // k:
            res.append(c)
    return res

• counts holds at most k − 1 candidate slots — that bound is what keeps space constant.
• If num is already a candidate, we just bump its count (a confirming vote).
• Otherwise, if there is room (len(counts) < k - 1), we open a new slot for it.
• Otherwise every slot is taken, so we decrement all counts; any candidate that reaches 0 is deleted, freeing its slot for later values.
• The second loop is the verification: nums.count(c) re-counts the survivor across the whole array, and we keep it only if that true frequency beats len(nums) // k.

Complexity

The payoff is the O(k) space: we never hold more than k − 1 counters, versus O(n) for a plain frequency map. For the usual small k (often 3), that is effectively constant extra space.

When this pattern shows up

Practice