Majority Element (Boyer-Moore Voting Algorithm)

Problem

Given an array where an element appears more than n/2 times, find that majority element (Boyer-Moore Voting Algorithm).

Input:  nums = [2, 2, 1, 1, 1, 2, 2]
Output: 2

Python Solution

def majority_element(nums):
    candidate = None
    count = 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    return candidate

C++ Solution

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

Java Solution

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0, count = 0;
        for (int num : nums) {
            if (count == 0) candidate = num;
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

Complexity

Time: O(n) — one pass, incrementing or decrementing a counter per element. Space: O(1) — only the candidate and its count are stored; correctness relies on the majority element outnumbering every other value combined.