Majority Element II

How it works

This variation uses a hash map to track candidates instead of fixed variables. We allow at most 2 elements in the map. When a third element tries to enter, we decrement all counts and remove elements with count 0. This generalizes the Boyer-Moore approach and can be extended to find elements appearing more than n/k times.

Steps

1. Create a hash map to store candidate counts.
2. For each element, increment its count in the map.
3. If the map has more than 2 entries:
   • Decrement all counts by 1.
   • Remove entries with count 0.
4. After processing, verify each remaining candidate by counting its actual occurrences.
5. Return candidates with count greater than n / 3.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) since output array size will be at most 2.

Things to watch for

Skipping the Verification Pass

The Boyer-Moore voting algorithm only identifies candidates that might appear more than n/3 times. After the first pass, you must verify each candidate by counting its actual occurrences. Skipping this step returns incorrect results when candidates do not actually exceed the threshold. This verification pass is essential, not optional.

Using Wrong Threshold Comparison

The problem asks for elements appearing more than n/3 times, meaning strictly greater than (>), not greater than or equal to (>=). Using count >= n/3 includes elements that appear exactly n/3 times, which is incorrect. Be precise with the comparison operator.

Incorrect Candidate Selection Order

When implementing Boyer-Moore with two candidates, the order of conditions matters. You must first check if the current element matches an existing candidate before checking if a slot is empty. If you check for empty slots first, you might assign the same element to both candidate slots, wasting one slot and missing potential majority elements.

from typing import List
from collections import defaultdict

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        count = defaultdict(int)

        for num in nums:
            count[num] += 1

            if len(count) <= 2:
                continue

            new_count = defaultdict(int)
            for num, c in count.items():
                if c > 1:
                    new_count[num] = c - 1
            count = new_count

        res = []
        for num in count:
            if nums.count(num) > len(nums) // 3:
                res.append(num)

        return res

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        unordered_map<int, int> count;

        for (int num : nums) {
            count[num]++;

            if (count.size() > 2) {
                unordered_map<int, int> newCount;
                for (auto& entry : count) {
                    if (entry.second > 1) {
                        newCount[entry.first] = entry.second - 1;
                    }
                }
                count = newCount;
            }
        }

        vector<int> res;
        for (auto& entry : count) {
            int frequency = 0;
            for (int num : nums) {
                if (num == entry.first) frequency++;
            }
            if (frequency > nums.size() / 3) {
                res.push_back(entry.first);
            }
        }

        return res;
    }
};