Majority Element — Boyer-Moore Voting O(n) O(1) [Amazon, Google Easy]

Problem Statement

Given an array of size n, find the majority element. The majority element always appears more than ⌊n/2⌋ times.

Input: [3,2,3] → 3 Input: [2,2,1,1,1,2,2] → 2

Intuition — Boyer-Moore Voting
C Solution
C++ Solution
Java Solution
JavaScript Solution
Python Solution
Complexity: O(n) time, O(1) space

Intuition — Boyer-Moore Voting

Maintain a candidate and a count. Walk through:

If count == 0: adopt current element as candidate
If current == candidate: count++
Else: count--

Why it works: Every time we decrement (a non-candidate neutralizes one candidate vote), both elements are "eliminated." Since the majority element has more than n/2 votes, it outlasts everything.

C Solution

int majorityElement(int* nums, int numsSize) {
    int candidate = nums[0], count = 1;
    for (int i = 1; i < numsSize; i++) {
        if (count == 0) { candidate = nums[i]; count = 1; }
        else if (nums[i] == candidate) count++;
        else count--;
    }
    return candidate;
}

C++ Solution

#include <vector>
using namespace std;

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = nums[0], count = 1;
        for (int i = 1; i < (int)nums.size(); i++) {
            if (count == 0) candidate = nums[i];
            count += (nums[i] == candidate) ? 1 : -1;
        }
        return candidate;
    }
};

Java Solution

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

JavaScript Solution

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

Python Solution

from typing import List

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

Complexity: O(n) time, O(1) space

Follow-up — Majority Element II: Find all elements appearing more than n/3 times. Use two candidate slots with Boyer-Moore. At most 2 such elements can exist.