147. Majority Element

Keep a single candidate and a count. Matching votes raise the count, differing votes lower it; when it hits zero, adopt the current element as the new candidate. The true majority survives because it outnumbers everything else combined.

Idea

The majority element appears more than half the time, so if every occurrence of the majority is a +1 vote and every other element is a -1 vote, the majority's votes strictly outnumber all others combined. Boyer-Moore voting exploits this with O(1) memory: track one candidate and a running count.

Algorithm

1. count = 0, candidate = None.
2. For each num:
   • If count == 0, adopt candidate = num (start fresh — earlier votes cancelled out).
   • Then count += 1 if num == candidate, else count -= 1.
3. Return candidate.

Think of it as pairing off different elements: each -1 cancels one majority vote against one non-majority vote. Because the majority has more than n/2 votes, it can never be fully cancelled, so it is whatever remains as the candidate at the end.

Worked example: [2,2,1,1,1,2,2]

Final candidate = 2, which indeed appears 4 > 7/2 times.

Complexity

• Time: O(n) — one pass.
• Space: O(1) — a candidate and a counter.

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