LeetCode 229: Majority Element II Solution in Python – A Step-by-Step Guide

What Is LeetCode 229: Majority Element II?

In LeetCode 229: Majority Element II, you’re given an integer array, and your task is to return a list of all elements that appear more than ⌊n/3⌋ times. This builds on LeetCode 169: Majority Element, which finds elements appearing more than ⌊n/2⌋ times, but here we’re looking for a lower threshold, meaning up to two elements can qualify.

Problem Statement

• Input: An integer array nums.
• Output: A list of integers appearing more than ⌊n/3⌋ times.
• Rules:
• There can be at most two such elements (since 2 * ⌊n/3⌋ < n).

Constraints

• Array length: 1 to 5 * 10^4.
• Numbers: -10^9 to 10^9.

Examples

• Input: [3,2,3]
• Output: [3] (3 appears 2 times, ⌊3/3⌋ = 1, 2 > 1).
• Input: [1,1,1,3,3,2,2,2]
• Output: [1,2] (1 appears 3 times, 2 appears 3 times, ⌊8/3⌋ = 2, 3 > 2).
• Input: [1]
• Output: [1] (1 appears 1 time, ⌊1/3⌋ = 0, 1 > 0).

Understanding the Problem: Finding Majority Elements

To solve LeetCode 229: Majority Element II in Python, we need to identify elements with a frequency exceeding ⌊n/3⌋. This isn’t about ranges like LeetCode 228: Summary Ranges—it’s about frequency analysis. We’ll use two approaches: 1. Best Solution (Boyer-Moore Voting Extension): O(n) time, O(1) space—clever and space-efficient. 2. Alternative Solution (Hash Map): O(n) time, O(n) space—simple and intuitive.

Let’s dive into the best solution.

Best Solution: Boyer-Moore Voting Extension for Majority Element II

Why This Is the Best Solution

The Boyer-Moore Voting extension is our top choice for LeetCode 229 because it finds up to two majority candidates in a single pass with constant space, leveraging a voting mechanism. It’s efficient, elegant, and perfect for tackling frequency problems without extra storage.

How It Works

• Since elements must appear more than ⌊n/3⌋ times, there can be at most two such elements.
• Use two candidates and counters:
• If a number matches a candidate, increment its counter.
• If counters are zero, assign a new candidate.
• If a number matches neither and both counters are non-zero, decrement both.
• Verify candidates’ counts in a second pass.

Step-by-Step Example

Example 1: [3,2,3]

• Candidates: c1 = None, count1 = 0, c2 = None, count2 = 0.
• 3: c1 = 3, count1 = 1.
• 2: c2 = 2, count2 = 1.
• 3: c1 = 3, count1 = 2.
• Verify: 3 appears 2 > ⌊3/3⌋ = 1, 2 appears 1 = 1.
• Output: [3].

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

• c1 = 1, count1 = 1.
• 1: count1 = 2.
• 1: count1 = 3.
• 3: c2 = 3, count2 = 1.
• 3: count2 = 2.
• 2: count1 = 2, count2 = 1 (decrement both).
• 2: count1 = 1, count2 = 0 (decrement, c2 reset).
• 2: c2 = 2, count2 = 1.
• Verify: 1 appears 3 > 2, 2 appears 3 > 2, 3 appears 2 = 2.
• Output: [1,2].

Code with Detailed Line-by-Line Explanation

Here’s the Python implementation:

Copy codeclass Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        # Line 1: Initialize candidates and counters
        c1, count1 = None, 0
        c2, count2 = None, 0

        # Line 2: First pass - find candidates
        for num in nums:
            # Line 3: Match or assign candidates
            if c1 == num:
                count1 += 1
            elif c2 == num:
                count2 += 1
            elif count1 == 0:
                c1, count1 = num, 1
            elif count2 == 0:
                c2, count2 = num, 1
            else:
                # Line 4: Decrement both counters
                count1 -= 1
                count2 -= 1

        # Line 5: Second pass - verify counts
        count1 = count2 = 0
        for num in nums:
            if num == c1:
                count1 += 1
            elif num == c2:
                count2 += 1

        # Line 6: Check threshold and build result
        result = []
        n = len(nums)
        if count1 > n // 3:
            result.append(c1)
        if count2 > n // 3:
            result.append(c2)

        # Line 7: Return the result
        return result

• Time Complexity: O(n) – two passes through the array.
• Space Complexity: O(1) – constant extra space.

Alternative Solution: Hash Map Approach for Majority Element II

Why an Alternative Approach?

The hash map approach counts occurrences explicitly, making it easy to understand and verify. It’s a great alternative if you prefer clarity over space efficiency or want a straightforward solution.

How It Works

• Use a dictionary to count each number’s frequency.
• Filter elements with counts exceeding ⌊n/3⌋.

Step-by-Step Example

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

• Hash map: {1: 0, 2: 0, 3: 0}.
• Count: {1: 3, 2: 3, 3: 2}.
• Threshold: ⌊8/3⌋ = 2.
• Filter: 1 (3 > 2), 2 (3 > 2).
• Output: [1,2].

Code for Hash Map Approach

Copy codeclass Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        # Line 1: Build frequency map
        freq = {}
        for num in nums:
            freq[num] = freq.get(num, 0) + 1

        # Line 2: Find elements exceeding n/3
        result = []
        n = len(nums)
        threshold = n // 3
        for num, count in freq.items():
            if count > threshold:
                result.append(num)

        # Line 3: Return the result
        return result

• Time Complexity: O(n) – single pass to build map and scan it.
• Space Complexity: O(n) – stores frequency map.

Comparing the Two Solutions

• Best Solution (Boyer-Moore Voting Extension):
• Pros: O(1) space, clever voting logic.
• Cons: Requires two passes, less intuitive initially.
• Alternative Solution (Hash Map):
• Pros: Simple, direct frequency check.
• Cons: O(n) space.

The Boyer-Moore extension is our best for its space efficiency and elegance.

Additional Examples and Edge Cases

Single Element

• Input: [1]
• Output: [1] (1 > ⌊1/3⌋ = 0).
• Both handle correctly.

No Majority

• Input: [1,2,3]
• Output: [] (each appears 1 = ⌊3/3⌋).
• Both return empty.

Two Equal Frequencies

• Input: [1,1,2,2]
• Output: [1,2] (both 2 > ⌊4/3⌋ = 1).
• Both work seamlessly.

Complexity Breakdown

• Boyer-Moore Voting Extension:
• Time: O(n).
• Space: O(1).
• Hash Map:
• Time: O(n).
• Space: O(n).

Boyer-Moore wins on space; both are time-optimal.

Key Takeaways for Beginners

• Frequency Threshold: More than ⌊n/3⌋ means max two elements.
• Boyer-Moore: Uses voting to find candidates.
• Hash Map: Counts explicitly.
• Python Tip: Dictionaries are great for counting—see [Python Basics](/python/basics).

Final Thoughts: Find Majority Elements Like a Pro

LeetCode 229: Majority Element II in Python is a brilliant way to tackle frequency problems. The Boyer-Moore Voting extension offers a space-efficient gem, while the hash map approach keeps it simple. Want more array challenges? Try LeetCode 169: Majority Element or LeetCode 347: Top K Frequent Elements. Ready to vote on numbers? Head to Solve LeetCode 229 on LeetCode and find those majority elements today!