Majority Element

The problem description can be found in LeetCode.

Approach

For the optimal solution in terms of space and time, you can check the Boyer–Moore majority vote algorithm. Here, we are going to check a slightly simpler solution, which requires more space compared to the algorithm cited above.

As usual, let's derive some examples. As per the requirements, we are sure to have a majority element, so we cannot have lists like:

wrong_lst1 = [1, 2]     # counter = {1: 1, 2: 1}, len(lst1) = 2
wrong_lst2 = [1, 2, 3]  # counter = {1: 1, 2: 1, 3: 1}, len(lst1) = 3

In fact, in these cases the number of occurrences of a certain number is always the same.

So, let's use some valid ones:

lst1 = [1]              # counter = {1: 1}, len(lst1) = 1
lst2 = [1, 1, 2]        # counter = {1: 2, 2: 1}, len(lst2) = 3
lst3 = [1, 1, 1, 2, 2]  # counter = {1: 3, 2: 2}, len(lst3) = 5

It is clear that the majority element has the highest number of repetitions. In particular, the number of occurrences is always $>\frac{n}{2}$, where $n$ is the size of the input list.

Hence, it will be enough to count the number of elements and then return the number that has a number of occurrences $>\frac{n}{2}$.

Solution

from collections import defaultdict
from typing import DefaultDict, List


class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counter = self.get_nums_counter(nums)

        for num, occ in counter.items():
            if occ > len(nums) // 2:
                return num

        raise Exception("expected one solution")

    def get_nums_counter(self, nums: List[int]) -> DefaultDict[int, int]:
        counter: DefaultDict[int, int] = defaultdict(int)

        for num in nums:
            counter[num] += 1

        return counter

Complexity

• Time: $O(n)$
• Space: $O(n)$

Where $n$ is the size of the nums list.