Majority Element II

Problem Description

Given an integer array nums of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Examples

Constraints

• 1 <= nums.length <= 5 * 10⁴
• -10⁹ <= nums[i] <= 10⁹

Extended Boyer-Moore Voting Algorithm

If an element must appear more than ⌊n / 3⌋ times, there can be at most two such elements in the array. This allows us to extend the Boyer-Moore Voting Algorithm. Instead of tracking one candidate, we track two candidates with separate counters. In the first pass, identify the two most frequent candidates. In a second pass, verify that these two candidates actually appear more than ⌊n / 3⌋ times, since the voting algorithm only guarantees candidates, not their absolute frequencies.

Solution 1: Extended Boyer-Moore Voting

Track two potential candidates and verify their frequencies in a second pass.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;

        int cand1 = 0, cand2 = 0, count1 = 0, count2 = 0;
        for (int num : nums) {
            if (num == cand1) {
                count1++;
            } else if (num == cand2) {
                count2++;
            } else if (count1 == 0) {
                cand1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                cand2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }

        // Second pass: verify frequencies
        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (num == cand1) count1++;
            else if (num == cand2) count2++;
        }

        int n = nums.length;
        if (count1 > n / 3) result.add(cand1);
        if (count2 > n / 3) result.add(cand2);

        return result;
    }
}

class Solution:
    def majorityElement(self, nums: list[int]) -> list[int]:
        if not nums:
            return []

        cand1, cand2, count1, count2 = 0, 0, 0, 0
        for num in nums:
            if num == cand1:
                count1 += 1
            elif num == cand2:
                count2 += 1
            elif count1 == 0:
                cand1 = num
                count1 = 1
            elif count2 == 0:
                cand2 = num
                count2 = 1
            else:
                count1 -= 1
                count2 -= 1

        # Verify counts
        count1, count2 = 0, 0
        for num in nums:
            if num == cand1:
                count1 += 1
            elif num == cand2:
                count2 += 1

        result = []
        n = len(nums)
        if count1 > n // 3:
            result.append(cand1)
        if count2 > n // 3:
            result.append(cand2)
        return result

#include <vector>

class Solution {
public:
    std::vector<int> majorityElement(std::vector<int>& nums) {
        std::vector<int> result;
        if (nums.empty()) return result;

        int cand1 = 0, cand2 = 0, count1 = 0, count2 = 0;
        for (int num : nums) {
            if (num == cand1) {
                count1++;
            } else if (num == cand2) {
                count2++;
            } else if (count1 == 0) {
                cand1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                cand2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }

        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (num == cand1) count1++;
            else if (num == cand2) count2++;
        }

        int n = nums.size();
        if (count1 > n / 3) result.push_back(cand1);
        if (count2 > n / 3) result.push_back(cand2);

        return result;
    }
};

Complexity Analysis

• Time Complexity: O(n) because we perform exactly two passes over the array.
• Space Complexity: O(1) auxiliary space as we track a fixed number of candidate variables.

Where It Breaks

If the problem asks for elements appearing more than ⌊n / k⌋ times, this solution scales to tracking k - 1 candidates. If k is dynamic, the number of candidate variables is not fixed, and a hash map is required, increasing space complexity to O(k).

Common Mistakes

• Incorrect check ordering: Checking for a zero count before verifying if the current element matches the other candidate. If candidate 2 matches candidate 1 when candidate 1’s count is zero, it can duplicate candidates.
• Forgetting the second pass: Assuming Boyer-Moore candidates are always majority elements. The second pass is mandatory because candidates are not guaranteed to have met the frequency threshold.

Frequently Asked Questions

Why can there be at most two majority elements? If three elements appeared more than ⌊n / 3⌋ times, their combined count would exceed 3 * (n / 3) = n, which is mathematically impossible for an array of size n.

What happens if all array elements are identical? Only one candidate will receive votes, and the second candidate will have a count of 0. The final validation pass will filter out the unused candidate.

← All Problems