Majority Element

Intuitionwhy cancellation leaves the majority behind

The majority element appears more than every other element combined. That means you can pair one occurrence of the majority with one occurrence of a different value, cancel both, and still have some majority occurrences left over. Repeating this cancellation cannot eliminate the majority completely, because there are not enough non-majority values to pair with all of it.

Boyer-Moore simulates those cancellations without storing the pairs. candidate is the value currently surviving, and count is its unmatched balance. Matching values increase the balance; different values decrease it. When the balance reaches zero, all values in that cancelled group are irrelevant, so the next value can start a fresh candidate group.

Approachtrack one candidate and its unmatched balance

1. 1Start count at zero and leave candidate uncommitted, because a zero balance means no earlier value currently has an advantage.
2. 2Scan each number from left to right. When count is zero, make the current number the candidate, because the previous candidate and its opponents have completely cancelled.
3. 3Increase count when the number equals candidate and decrease it otherwise, because each different value cancels one unmatched candidate occurrence.
4. 4Continue using the same balance instead of resetting it after a mismatch, because a mismatch removes only one vote and the remaining candidate votes still matter.
5. 5Return candidate after the scan. The guaranteed majority cannot be fully cancelled, so the value left in the surviving group must be the majority element.

Complexityone pass and constant working memory

Annotated solutionC++ · Boyer-Moore majority vote · constant extra space

#include <vector>
using namespace std;

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int candidate = 0;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }

            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
};

The placement of the count-zero check is the key detail. You choose the new candidate before processing the current number, then immediately give that number a count of one. A mismatch subtracts one rather than resetting the count, because the current balance represents real unmatched occurrences that still need to be cancelled.

The frequency-map alternativeclearer bookkeeping, but it spends O(n) extra space

A hash map provides a direct solution: count each value while scanning, and return as soon as one count exceeds n / 2. This is a reasonable choice when the cancellation idea is unfamiliar or when you need the frequencies for another part of a larger task. For this problem it is an arrangement rather than an optimisation, because it keeps more information than the answer requires.

#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> frequency;
        int required = static_cast<int>(nums.size()) / 2;

        for (int num : nums) {
            ++frequency[num];
            if (frequency[num] > required) {
                return num;
            }
        }

        return 0;
    }
};

The map version takes O(n) expected extra space in the worst case, when many distinct values appear, while its expected time is O(n). Boyer-Moore is preferable here because the problem asks only for the majority value and guarantees that one exists; the map is preferable only when retaining exact frequency information is useful.

Common mistakeswrong code shapes that break the cancellation argument