Majority Element

easy array voting

Problem

Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times.

Inputnums = [4, 2, 4, 5, 4, 4, 1]

Output4

4 appears 4 times, more than 7 / 2 = 3.

nums (comma-separated)

def majority_element(nums):
    cand, count = None, 0
    for x in nums:
        if count == 0:
            cand = x
        count += 1 if x == cand else -1
    return cand

function majorityElement(nums) {
  let cand = null, count = 0;
  for (const x of nums) {
    if (count === 0) cand = x;
    count += (x === cand) ? 1 : -1;
  }
  return cand;
}

class Solution {
    public int majorityElement(int[] nums) {
        Integer cand = null;
        int count = 0;
        for (int x : nums) {
            if (count == 0) cand = x;
            count += (x == cand) ? 1 : -1;
        }
        return cand;
    }
}

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

Explanation

The majority element appears more than half the time, and the Boyer-Moore voting trick uses that fact to find it with just one counter and no extra memory.

Picture each element casting a vote. We hold one cand and a count. When count hits 0 we adopt the current value as the new candidate. If the next value matches the candidate, count goes up; if not, it goes down.

Because the majority value occurs more than every other value combined, all the "disagreeing" votes can cancel it down but never knock it out entirely, so it ends up as the survivor.

We do not even need a verification pass here, since the problem guarantees a majority exists — whatever cand holds at the end is the answer.

Example: [4, 2, 4, 5, 4, 4, 1]. Disagreements cancel pairs along the way, but 4 (appearing 4 of 7 times) survives, so the answer is 4.

Time: O(n) Space: O(1)