Majority Element in an Array

Given an integer array nums of size n, the task is to find the majority element. A majority element is defined as the element that appears more than ⌊n / 2⌋ times in the array.

It is guaranteed that the majority element always exists.

Problem Example

Input:  nums = [3, 2, 3]
Output: 3

Input:  nums = [2,2,1,1,1,2,2]
Output: 2
  

---

Approach 1: Using Counter (Easy to Understand)

A straightforward approach is to count the frequency of each element and return the one with the maximum count.

Python Code

from collections import Counter

class Solution:
    def majorityElement(self, nums):
        freq = Counter(nums)
        max_count = max(freq.values())
        for key in freq:
            if freq[key] == max_count:
                return key
  

Complexity Analysis

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

Although this solution is simple and readable, it uses extra memory to store the frequency of all elements. Therefore, it does not satisfy the follow-up requirement of O(1) space.

---

Approach 2: Boyer–Moore Voting Algorithm (Optimal)

This problem can be solved in O(n) time and O(1) space using the Boyer–Moore Voting Algorithm.

The key idea is based on cancellation. Since the majority element appears more than half the time, it cannot be completely canceled out by other elements.

Algorithm Explanation

• Maintain a variable candidate for the potential majority element
• Maintain a counter count
• If count == 0, choose the current element as the candidate
• If the current element equals the candidate, increment the count
• Otherwise, decrement the count

Python Code

class Solution:
    def majorityElement(self, nums):
        candidate = None
        count = 0

        for num in nums:
            if count == 0:
                candidate = num
            if num == candidate:
                count += 1
            else:
                count -= 1

        return candidate
  

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

This solution works because every non-majority element cancels out one occurrence of the majority element. Since the majority element appears more than ⌊n / 2⌋ times, it will remain as the final candidate.

---

Conclusion

While the Counter-based solution is intuitive and easy to implement, it requires extra memory. The Boyer–Moore Voting Algorithm is the optimal solution that meets the follow-up requirement of linear time and constant space, making it the preferred approach in interviews and competitive programming.