Introduction

The problem of finding an element that appears more than n / k times is a useful generalization of the majority-element problem. When k = 2, you are looking for an element that appears more than half the time. For larger k, there can be multiple valid answers, but never too many, and that observation drives the efficient solution.

The Key Observation

In an array of length n, there can be at most k - 1 elements that appear more than n / k times. If there were k such elements, the total number of occurrences would exceed n, which is impossible.

That means you do not need to track every distinct value. You only need to track up to k - 1 candidate elements and then verify them.

This is the generalized Boyer-Moore voting idea.

The Simple Hash Map Solution

If memory is not a concern, the easiest implementation is a frequency map:

1def find_frequent_elements(nums, k):
2    if k <= 1:
3        raise ValueError("k must be greater than 1")
4
5    counts = {}
6    threshold = len(nums) // k
7
8    for value in nums:
9        counts[value] = counts.get(value, 0) + 1
10
11    return [value for value, count in counts.items() if count > threshold]
12
13
14print(find_frequent_elements([3, 1, 2, 2, 1, 2, 3, 3], 4))

This runs in O(n) time and O(n) space in the worst case. It is often the best answer in production code when clarity matters more than minimizing auxiliary memory.

The O(k) Space Approach

To reduce space, keep at most k - 1 candidate counters. The algorithm works in two passes:

1. find possible candidates
2. count them again to verify which ones really exceed n / k

1def find_frequent_elements_optimized(nums, k):
2    if k <= 1:
3        raise ValueError("k must be greater than 1")
4
5    candidates = {}
6
7    for value in nums:
8        if value in candidates:
9            candidates[value] += 1
10        elif len(candidates) < k - 1:
11            candidates[value] = 1
12        else:
13            to_delete = []
14            for key in list(candidates):
15                candidates[key] -= 1
16                if candidates[key] == 0:
17                    to_delete.append(key)
18            for key in to_delete:
19                del candidates[key]
20
21    verified = {key: 0 for key in candidates}
22    for value in nums:
23        if value in verified:
24            verified[value] += 1
25
26    threshold = len(nums) // k
27    return [value for value, count in verified.items() if count > threshold]
28
29
30print(find_frequent_elements_optimized([3, 1, 2, 2, 1, 2, 3, 3], 4))

The cancellation step is the important idea. When the candidate set is full and a new different value appears, you reduce every candidate count by one. Conceptually, that removes one occurrence from k different elements, which cannot eliminate a truly frequent element permanently.

Why Verification Is Required

After the first pass, the tracked values are only candidates. They survived repeated cancellations, but they are not yet guaranteed to appear more than n / k times.

For example, a value can remain in the candidate map simply because the distribution of other values happened to cancel differently. That is why the second counting pass is mandatory.

This is the same pattern as the ordinary majority-element voting algorithm: candidate selection first, proof by recount second.

When to Use Which Method

Use the hash map method when:

• the array fits comfortably in memory
• readability matters most
• 'k is not especially small relative to n'

Use the optimized method when:

• you want O(k) extra space
• you are solving an interview-style problem
• the input is large and the frequency map would be wasteful

For many real applications, the hash map version is easier to maintain. The optimized algorithm is elegant, but it is easier to get wrong.

Common Pitfalls

The biggest mistake is returning candidates immediately after the first pass. Those values must be verified.

Another mistake is misreading the condition. The problem asks for elements appearing more than n / k times, not greater than or equal to n / k.

People also forget that there can be multiple valid answers. This is not always a single-element problem.

Finally, validate k. If k <= 1, the threshold is not meaningful for this algorithm and the function should reject the input.

Summary

• The n / k repetition problem generalizes the majority-element problem.
• At most k - 1 elements can appear more than n / k times.
• A hash map gives a clear O(n) time solution with higher space usage.
• The generalized Boyer-Moore approach reduces extra space to O(k).
• Candidate verification in a second pass is essential for correctness.