Majority Element

Intuition

• Since we have a guarantee that the majority element must appear more than floor of $\frac{N}{2}$ times, we can use the Boyer Moore Algorithm, in which once an element surpasses $\frac{N}{2}$, that element can no longer be overridden by a different element.

Complexity

Runtime

$O(N)$

Space

$O(1)$

Code

Boyer Moore

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        boyer = 0
        moore = -1
        for num in nums:
            if boyer == 0:
                moore = num
            if moore == num:
                boyer += 1
            else:
                boyer -= 1
        return moore

Hashmap O(N) Space

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return Counter(nums).most_common(1)[0][0]

---

References

Majority Element - LeetCode