Majority Element II

Intuitionwhy only two candidates need to survive

A value must appear more than n/3 times, so three different values cannot all cross that threshold: their combined occurrences would exceed n. Therefore the answer has at most two elements. The algorithm keeps two candidate slots, because no valid answer needs a third slot.

When the current number matches a candidate, that candidate gains support. When a candidate slot is empty, the number takes it. If both slots already hold different values and the current number matches neither, remove one unit of support from both candidates. This cancels a group of three different values. Removing such a group cannot eliminate a value that occurs more than n/3 times, because that value cannot be part of enough cancellations to disappear completely.

The first pass leaves possible candidates, not guaranteed answers. A candidate can survive because of the cancellation process even when its actual frequency is too small. The second pass counts the two survivors in the original array and applies the exact condition count > floor(n/3).

Approachtwo passes: preserve possibilities, then prove them

1. 1Set up two candidate values and two support counts, because at most two values can exceed the one-third threshold and every later decision needs to compare against both slots.
2. 2For each number, increase the count of the matching candidate first, because an existing candidate must keep its support instead of being replaced by a later empty-slot check.
3. 3If the number matches neither candidate and one count is zero, place it in that empty slot with count one, because an unused slot is available to represent a new possible answer.
4. 4If the number matches neither candidate and both counts are positive, decrease both counts, because the three different values form one removable group and equal cancellation must affect both surviving candidates.
5. 5Scan the array again and count occurrences of the two final candidates, because surviving a cancellation pass is only a possibility and does not prove the original frequency threshold.
6. 6Append each candidate whose verified count is greater than n/3, checking the candidates independently because the answer may contain zero, one, or two values.

Complexityconstant working memory despite two passes

Annotated solutionC++ · two-candidate Boyer-Moore voting

#include <vector>

using namespace std;

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
        int candidate1 = 0;
        int candidate2 = 0;
        int count1 = 0;
        int count2 = 0;

        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }

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

        vector<int> result;
        if (count1 > n / 3) {
            result.push_back(candidate1);
        }
        if (count2 > n / 3) {
            result.push_back(candidate2);
        }

        return result;
    }
};

The order of the first four conditions matters. A matching candidate must be counted before an empty slot is reused, and the two candidates must be checked before a replacement is attempted. The final pass deliberately resets both counts: the first-pass counts measure uncancelled support, not the true frequencies required by the statement.

The hashing alternativesimpler bookkeeping in exchange for linear extra space

A frequency map is the direct approach: count every value, then collect the entries whose counts exceed n/3. It is easier to explain and less sensitive to the order of candidate checks, but it stores up to n distinct values. The voting solution is an optimisation from O(n) extra space to O(1); hashing is still a reasonable choice when memory is not the concern.

#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> frequency;
        vector<int> result;

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

        for (const auto& entry : frequency) {
            if (entry.second > n / 3) {
                result.push_back(entry.first);
            }
        }

        return result;
    }
};

The map version takes expected O(n) time and O(n) extra space, because it visits the array once and may keep one entry for every distinct value. It buys simpler reasoning and removes the need for verification candidates, while the two-candidate method buys the constant-space bound without changing the linear time.

Common mistakesthree lines that change the proof