Majority Element

Find the value that appears more than n/2 times. Boyer–Moore voting keeps one candidate and a counter: matching values vote for it, others vote against, and when the counter hits zero a new candidate takes over. The true majority always survives.

Traced input: nums = [2, 2, 1, 1, 1, 2, 2] → 2. Original problem: neetcode.io/problems/majority-element

Complexity

Always one full pass with two variables.

Key idea

• Pair each majority element with a different element and cancel them; the majority still has some left over.
• count == 0 means everything so far cancelled out, so start fresh with the current value.
• The final candidate is the majority, as long as one is guaranteed to exist.

Common mistakes

• Without the guarantee, the survivor might not be a majority; verify with a second pass.
• Changing the candidate when count is 1 instead of 0.
• A HashMap of counts works but uses O(n) space; interviewers ask for O(1).

Solution

int majorityElement(int[] nums) {
    int candidate = 0, count = 0;
    for (int i = 0; i < nums.length; i++) {
        if (count == 0) {
            candidate = nums[i];
        }
        count += (nums[i] == candidate) ? 1 : -1;
    }
    return candidate;
}

def majorityElement(nums: List[int]) -> int:
    candidate, count = 0, 0
    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    return candidate

int majorityElement(vector<int>& nums) {
    int candidate = 0, count = 0;
    for (int x : nums) {
        if (count == 0) {
            candidate = x;
        }
        count += (x == candidate) ? 1 : -1;
    }
    return candidate;
}

Edge cases

Each one has its own trace in the interactive view.