Find Elements Appearing More Than n/3 Times in Python

Return all elements that occur more than len(array)/3 times using a simple dictionary counter.

Easy Python 3.9+ Aug 9, 2026 Algorithms & data structures 12 views 0 copies

majority-element dictionary counting algorithms

Python code

14 lines

Python 3.9+

def majority_third(arr):
    """Return elements appearing more than len(arr)/3 times."""
    cutoff = len(arr) / 3
    counts = {}
    for x in arr:
        counts[x] = counts.get(x, 0) + 1
    return [x for x, c in counts.items() if c > cutoff]


if __name__ == "__main__":
    test1 = [3, 2, 3]
    test2 = [1, 1, 1, 3, 3, 2, 2, 2]
    print(majority_third(test1))  # [3]
    print(majority_third(test2))  # [1, 2]

Output

stdout

[3]
[1, 2]

How it works

The function uses a dictionary to count the frequency of each element in the array. It calculates the cutoff as len(arr)/3 and keeps only those elements whose count is strictly greater than this threshold. Using counts.get(x, 0) avoids a KeyError when a key is seen for the first time. The result is a new list containing the qualifying elements in the order they were first encountered. This approach is straightforward, correct, and runs in O(n) time with O(n) extra space.

Common mistakes

Using >= instead of > when comparing counts to the cutoff
Forgetting that len(arr)/3 may be a float, so comparing integers directly is fine but tests may fail if threshold is miscalculated
Assuming there can be at most one majority third element — but up to two are possible
Not using .get() and triggering a KeyError for unseen keys

Variations

Use collections.Counter from the stdlib for a more concise counter: counts = Counter(arr)
Use a Boyer-Moore majority vote extension for O(1) space, at the cost of more code

Real-world use cases

Filtering out rare tags or categories in a dataset where only very frequent labels matter.
Detecting dominant error types in application logs to prioritize fixes.
Finding the most common products in a sales transaction list when only the top tier is important.

Find Elements Appearing More Than n/3 Times in Python

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Keep learning

Tutorials

Quizzes