LeetCode 169: Majority Element Solution in Python Explained

Problem Statement

In LeetCode 169, you’re given an integer array nums of size n. Your task is to return the majority element—the element appearing more than n/2 times—guaranteed to exist in the array. You should aim for O(n) time complexity and O(1) space if possible. This differs from Excel column conversion like LeetCode 168: Excel Sheet Column Title, focusing on frequency analysis rather than number-to-string mapping.

Constraints

• 1 <= nums.length <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9
• Majority element exists (appears > n/2 times)

Example

Let’s see some cases:

Copy codeInput: nums = [3,2,3]
Output: 3
Explanation: 3 appears 2 times, > 3/2 = 1.5, majority element.

Copy codeInput: nums = [2,2,1,1,1,2,2]
Output: 2
Explanation: 2 appears 4 times, > 7/2 = 3.5, majority element.

Copy codeInput: nums = [1]
Output: 1
Explanation: 1 appears once, > 1/2 = 0.5, majority element.

These examples show we’re identifying the most frequent element.

Understanding the Problem

How do you solve LeetCode 169: Majority Element in Python? Take nums = [3,2,3]. Here, 3 appears twice, more than 3/2 = 1.5, so return 3. For [2,2,1,1,1,2,2], 2 appears 4 times, more than 7/2 = 3.5, so return 2. The guarantee of a majority element (> n/2) allows optimizations beyond simple counting, aiming for O(n) time and O(1) space. This isn’t a two-sum task like LeetCode 167: Two Sum II - Input Array Is Sorted; it’s about frequency dominance. We’ll use: 1. Boyer-Moore Voting Algorithm: O(n) time, O(1) space—our best solution. 2. Hash Map Counting: O(n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Boyer-Moore Voting Algorithm

Explanation

Boyer-Moore Voting Algorithm finds the majority element by leveraging its dominance:

• Maintain a candidate (potential majority element) and a count.
• Traverse the array:
• If count = 0, set candidate to the current element.
• If current element equals candidate, increment count.
• Otherwise, decrement count.
• Since the majority element appears > n/2 times, it will remain the candidate.

This achieves O(n) time complexity (single pass), O(1) space, and elegance by avoiding explicit counting, making it the optimal solution.

For [3,2,3]:

• Start: candidate=3, count=1.
• 2: count=0, candidate=2.
• 3: candidate=3, count=1, return 3.

Step-by-Step Example

Example 1: nums = [3,2,3]

Goal: Return 3.

• Start: candidate = 3, count = 0.
• Step 1: num = 3, count = 0, set candidate = 3, count = 1.
• Step 2: num = 2, 2 != 3, count = 0.
• Step 3: num = 3, count = 0, set candidate = 3, count = 1.
• Finish: Return candidate = 3.

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

Goal: Return 2.

• Start: candidate = 2, count = 0.
• Step 1: 2, candidate = 2, count = 1.
• Step 2: 2, count = 2.
• Step 3: 1, count = 1.
• Step 4: 1, count = 0.
• Step 5: 1, candidate = 1, count = 1.
• Step 6: 2, count = 0.
• Step 7: 2, candidate = 2, count = 1.
• Finish: Return 2.

Example 3: nums = [1]

Goal: Return 1.

• Start: candidate = 1, count = 0.
• Step 1: num = 1, candidate = 1, count = 1.
• Finish: Return 1.

How the Code Works (Boyer-Moore Voting Algorithm) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef majorityElement(nums: list[int]) -> int:
    # Line 1: Initialize candidate and count
    candidate = nums[0]
    # Start with first element (e.g., 3)
    count = 0
    # Initial count (e.g., 0)

    # Line 2: Traverse array
    for num in nums:
        # Process each element (e.g., 3, 2, 3)

        # Line 3: Reset candidate if count is 0
        if count == 0:
            # No dominant candidate (e.g., after 2 cancels 3)
            candidate = num
            # Set new candidate (e.g., 2, then 3)

        # Line 4: Update count
        if num == candidate:
            # Matches candidate (e.g., 3 == 3)
            count += 1
            # Increment (e.g., 1)
        else:
            # Doesn’t match (e.g., 2 != 3)
            count -= 1
            # Decrement (e.g., 0)

    # Line 5: Return majority element
    return candidate
    # Guaranteed majority (e.g., 3)

This detailed breakdown clarifies how Boyer-Moore efficiently identifies the majority element.

Alternative: Hash Map Counting Approach

Explanation

Hash Map Counting counts occurrences of each element:

• Build a hash map with element frequencies.
• Find the element with count > n/2.
• Return that element.

It’s a practical alternative, O(n) time (single pass), O(n) space (hash map), but less space-efficient than Boyer-Moore.

For [3,2,3]:

• Map: {3:2, 2:1{, 3 > 3/2, return 3.

Step-by-Step Example (Alternative)

For [2,2,1,1,1,2,2]:

• Step 1: Map: {2:4, 1:3{.
• Step 2: 4 > 7/2 = 3.5, return 2.
• Finish: Return 2.

How the Code Works (Hash Map)

Copy codedef majorityElementHash(nums: list[int]) -> int:
    n = len(nums)
    count = {{
    for num in nums:
        count[num] = count.get(num, 0) + 1
        if count[num] > n // 2:
            return num
    return 0  # Unreachable due to guarantee

Complexity

• Boyer-Moore Voting Algorithm:
• Time: O(n) – single pass.
• Space: O(1) – constant space.
• Hash Map Counting:
• Time: O(n) – single pass.
• Space: O(n) – hash map.

Efficiency Notes

Boyer-Moore Voting Algorithm is the best solution with O(n) time and O(1) space, leveraging the majority guarantee optimally—Hash Map Counting matches time complexity but uses O(n) space, making it straightforward but less space-efficient.

Key Insights

• Boyer-Moore: Cancels minorities.
• Hash Map: Explicit counts.
• Majority: > n/2 guarantee.

Additional Example

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

• Goal: 1.
• Boyer-Moore: 1 persists, count=3, return 1.

Edge Cases

• Single Element: [1] → 1.
• All Same: [2,2,2] → 2.
• Bare Majority: [1,1,2] → 1.

Both solutions handle these well.

Final Thoughts

LeetCode 169: Majority Element in Python is a clever frequency challenge. The Boyer-Moore Voting Algorithm excels with its linear efficiency and minimal space, while Hash Map Counting offers a clear counting approach. Want more? Try LeetCode 229: Majority Element II for multiple majorities or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 169 on LeetCode with [3,2,3], aiming for 3—test your skills now!