Majority Element II | Leetcode 229 | Explained in Python

You’re given an integer array nums of length n.
An element is called a majority element II if it appears strictly more than ⌊ n / 3 ⌋ times.
Because n / 3 ≈ 33 %, at most two such elements can exist.
Return them in any order.

Here’s the [Problem Link] to begin with.

Example

Typical interview follow-ups:

• Show why more than two majority-II elements are impossible.
• Discuss the Boyer-Moore extension that keeps two running candidates.

Brute Force Solution (Double / Triple Loop)

Intuition & Approach

• For every element, count its total occurrences using an inner loop.
• If the count exceeds n // 3 and it’s not already recorded, add it to the answer.
• Stop once two elements are found (the maximum possible).

Code Implementation

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = []
        for i in range(0, n):
            # skip counting if nums[i] already confirmed
            if len(result) == 0 or result[0] != nums[i]:
                count = 0
                for j in range(0, n):         # count how many nums[i]
                    if nums[j] == nums[i]:
                        count += 1
                if count > n // 3:             # majority-II check
                    result.append(nums[i])
            if len(result) == 2:               # early exit (max two answers)
                break
        return result

Code Explanation

• Outer loop picks a potential candidate.
• Inner loop counts its frequency.
• Duplicate work abounds, so runtime balloons.

Dry Run (Input [3,2,3])

1. i = 0, nums[i]=3 → count=2 → 2 > 1 → add 3.
2. i = 1, nums[i]=2 → count=1 → fails threshold.
3. Done → result [3].

Time & Space Complexity

• Time: O(n²) – nested scan.
• Space: O(1) extra.

Conclusion

Simple but painfully slow; unsuitable for anything but toy inputs.

Better Solution (Hash-Map Counting)

Intuition & Approach

• One pass builds a frequency map num → count.
• Second pass (or inline check) collects keys whose count > n // 3.

Code Implementation

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        freq = {}
        for num in nums:                       # frequency table
            freq[num] = freq.get(num, 0) + 1

        result = []
        for k, v in freq.items():              # collect > n//3 keys
            if v > n // 3:
                result.append(k)
            if len(result) == 2:
                break                          # at most two answers
        return result

Code Explanation

• Dictionary insertions/updates are O(1) amortized.
• Memory usage is proportional to the number of distinct elements.

Dry Run (Input [1,1,1,3,3,2,2,2])

• freq={1:3, 3:2, 2:3}
• Threshold = 2 → collect 1, 2.

Time & Space Complexity

• Time: O(n)
• Space: O(k) – k distinct numbers.

Conclusion

Linear time and clear, but still needs a hash-map. We can do constant space next.

Optimal Solution (Extended Boyer–Moore Voting)

Intuition & Approach

• There can be ≤ 2 majority-II elements.
• Maintain two candidates (cand1, cand2) with counters (cnt1, cnt2).
• Cancellation rules:
  • If current number equals one candidate → its counter ++.
  • Else if a counter is 0 → adopt current number as new candidate.
  • Else → decrement both counters (pairwise cancel).
• A final verification pass counts how many times each candidate truly appears.

Code Implementation

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        cand1, cand2 = None, None   # potential majorities
        cnt1, cnt2 = 0, 0           # their vote balances

        # Voting pass
        for num in nums:
            if cand1 == num:
                cnt1 += 1
            elif cand2 == num:
                cnt2 += 1
            elif cnt1 == 0:
                cand1, cnt1 = num, 1
            elif cnt2 == 0:
                cand2, cnt2 = num, 1
            else:                   # pairwise cancellation
                cnt1 -= 1
                cnt2 -= 1

        # Verification pass
        cnt1 = cnt2 = 0
        for num in nums:
            if num == cand1:
                cnt1 += 1
            elif num == cand2:
                cnt2 += 1

        result = []
        if cnt1 > n // 3:
            result.append(cand1)
        if cnt2 > n // 3:
            result.append(cand2)
        return result

Code Explanation

• Voting phase ensures that any non-majority elements are canceled out.
• Because a real majority-II cannot be completely canceled, it remains as cand1 or cand2.
• Verification phase guards against false positives (e.g., when no element exceeds n/3).

Dry Run (Input [1,1,1,3,3,2,2,2])

Verification counts: 1→3, 2→3 → both >8//3 = 2 → [1,2].

Time & Space Complexity

• Time: O(n) – two linear scans.
• Space: O(1) – constant extra variables.

Conclusion

The extended Boyer–Moore algorithm nails the sweet spot: one pass to elect candidates, one pass to confirm, and only a handful of variables. This is the answer interviewers look for when they mention “more than n/3 occurrences.”

Final Thoughts

Remember: whenever the problem says “more than n / k times,” think Boyer–Moore generalized to k − 1 candidates. Master that pattern and majority problems become a breeze.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.