LeetCode 169: Majority Element - All Solutions Explained

Problem Statement

The Majority Element problem, LeetCode 169, is an easy-difficulty challenge where you’re given an array of integers nums. Your task is to find the majority element, which is the element that appears more than ⌊n/2⌋ times, where n is the array length. The problem guarantees that a majority element always exists.

Constraints

• 1 ≤ nums.length ≤ 5 * 10⁴
• -10⁹ ≤ nums[i] ≤ 10⁹
• A majority element (appearing > n/2 times) exists.

Example

Copy codeInput: nums = [3,2,3]
Output: 3
Explanation: 3 appears 2 times, n/2 = 1.5, so 3 is the majority.

Copy codeInput: nums = [2,2,1,1,1,2,2]
Output: 2
Explanation: 2 appears 4 times, n/2 = 3.5, so 2 is the majority.

Copy codeInput: nums = [1]
Output: 1
Explanation: 1 appears 1 time, n/2 = 0.5, so 1 is the majority.

Understanding the Problem

We need to identify an element that appears more than half the time in the array. Since a majority is guaranteed, we can use this property to find it efficiently. We’ll cover:

• Boyer-Moore Voting : Best solution, detailed below.
• Hash Map : Alternative, explained concisely.

Solution 1: Boyer-Moore Voting (Best Solution)

Explanation of the Best Solution

This method, known as the Boyer-Moore Voting Algorithm, finds the majority element by maintaining a candidate and a counter. Since the majority element appears more than n/2 times, it will always remain after “canceling out” pairs of different elements. Here’s the step-by-step process:

1. Define a method in a class. Create a Solution class with a majorityElement method that takes nums as input and returns an integer.
2. Set initial values. Start with the first element as the candidate and set count to 1, assuming it’s the majority at first.
3. Iterate through the array. Loop through nums starting from the second element to process each number.
4. Check the counter. If count is 0, it means previous candidates have been canceled out, so pick the current element as the new candidate.
5. Update the counter. If the current element equals the candidate, increment count by 1 (reinforcing the candidate). If it’s different, decrement count by 1 (canceling one occurrence of the candidate).
6. Continue until the end. The loop processes all elements, and the final candidate will be the majority element due to its guaranteed frequency.
7. Return the result. Return the candidate as the majority element.

Step-by-Step Example

For nums = [2,2,1,1,1,2,2]:

• candidate = 2, count = 1.
• Element 2: 2 == 2 → count = 2.
• Element 1: 1 != 2 → count = 1.
• Element 1: 1 != 2 → count = 0, candidate = 1.
• Element 1: 1 == 1 → count = 1.
• Element 2: 2 != 1 → count = 0, candidate = 2.
• Element 2: 2 == 2 → count = 1.
• Result: candidate = 2 (appears 4 times > 3.5).

Python Code (Boyer-Moore Solution)

Copy codeclass Solution:
    def majorityElement(self, nums: list[int]) -> int:
        candidate = nums[0]
        count = 1
        for num in nums[1:]:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1
        return candidate

# Test cases
sol = Solution()
print(sol.majorityElement([3,2,3]))          # Output: 3
print(sol.majorityElement([2,2,1,1,1,2,2]))  # Output: 2
print(sol.majorityElement([1]))              # Output: 1

Complexity

• Time Complexity : O(n), single pass through the array.
• Space Complexity : O(1), only uses two variables.

Why It’s the Best

• Extremely efficient with no extra space.
• Leverages the majority property cleverly.
• Preferred in interviews for its elegance.

Solution 2: Hash Map

Explanation

This method counts the frequency of each element using a hash map and identifies the one exceeding n/2 occurrences.

• Initialize a hash map. Use a dictionary to store the count of each number.
• Count frequencies. Loop through the array, incrementing the count for each element.
• Check for majority. Return the element whose count exceeds n/2 (optimized by returning early).

Step-by-Step Example

For nums = [2,2,1,1,1,2,2]:

• count = {}.
• 2: count = {2: 1}.
• 2: count = {2: 2}.
• 1: count = {2: 2, 1: 1}.
• 1: count = {2: 2, 1: 2}.
• 1: count = {2: 2, 1: 3}.
• 2: count = {2: 3, 1: 3}.
• 2: count = {2: 4, 1: 3}, 4 > 3.5 → return 2.
• Result: 2.

Python Code (Hash Map Solution)

Copy codeclass Solution:
    def majorityElement(self, nums: list[int]) -> int:
        count = {}
        n = len(nums)
        for num in nums:
            count[num] = count.get(num, 0) + 1
            if count[num] > n // 2:
                return num
        return 0  # Won’t happen due to problem guarantee

# Test cases
sol = Solution()
print(sol.majorityElement([3,2,3]))          # Output: 3
print(sol.majorityElement([2,2,1,1,1,2,2]))  # Output: 2
print(sol.majorityElement([1]))              # Output: 1

Complexity

• Time Complexity : O(n), one pass to build the map.
• Space Complexity : O(n), storing counts in the hash map.

Pros and Cons

• Pros : Straightforward and easy to understand.
• Cons : Uses extra space compared to Boyer-Moore.

Comparison of Solutions

Edge Cases to Consider

• Single Element : [1] → 1.
• All Same : [2,2,2] → 2.
• Barely Majority : [1,1,2] → 1 (2 > 1.5).

Final Thoughts

• Boyer-Moore Voting : Best for its efficiency and minimal space—detailed above. Top choice for interviews.
• Hash Map : Reliable and clear with an example, but less efficient in space. Master Boyer-Moore, then explore LeetCode 229 for a twist!