Majority Element — Editorial

Opening the reading…

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

Start count at zero and leave candidate uncommitted, because a zero balance means no earlier value currently has an advantage.

Scan 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.

Increase count when the number equals candidate and decrease it otherwise, because each different value cancels one unmatched candidate occurrence.

Continue 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.

Return 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

MEASURE	BOUND	WHY
Time	O(n)	The loop examines each array element exactly once and performs a constant amount of work for it. No element is rescanned, and candidate changes do not start another traversal.
Space	O(1) extra	Only candidate and count are maintained; the input array is not copied, and the required returned integer is output rather than working memory. The bound remains O(1) even for the worst arrangement of values.

Here n is the number of elements in nums.

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

CPPBoyer-Moore majority vote with one candidate and one cancellation count.

#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.

CPPHash-map counting alternative that returns when a value passes the majority threshold.

#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.