The O(n) Club: Majority Element — The Array’s Unbeatable Bully

The O(n) Club: Majority Element — The Array’s Unbeatable Bully

⚡ TL;DR

The Majority Element is the number that turns your array into a one-party system by showing up more than n/2 times. Resist the urge to sort or hash — just use Boyer–Moore for a one-pass, two-variable miracle. Like so:

// Boyer–Moore Voting in Java
int count = 0, candidate = 0;
for (int num : nums) {
    if (count == 0) candidate = num;
    count += (num == candidate) ? 1 : -1;
}
return candidate;

🧠 How Devs Usually Mess This Up

If you think the majority just means “biggest number wins,” welcome to the trap! This isn’t election night in Silicon Valley.
Classic developer faceplants include:

• Assuming “majority” = maximum value—nope, it’s whoever shows up to the party the most, not who’s flashiest.
• Counting elements and stopping at “most frequent”—if it isn’t strictly more than n/2 times, it’s just loud, not a winner.
• Bringing out HashMaps for a guaranteed-majority question and flexing that O(n) space for literally no reason.
• Trusting solutions that never verify counts, especially if the majority isn’t promised (you’ll regret it in the real world).

🔍 What’s Actually Going On

Boyer–Moore’s Majority Vote algorithm isn’t magic, but it sure feels like it. Imagine an endless cafeteria food fight. Every time two different foods (numbers) clash, they both get swept off the table. The only way one food survives until the lunch bell is if it started with more than half the numbers — no other dish stands a chance.
In algorithmic terms: “pair off” anything unequal until there’s only one menu item left. If a majority exists, you’ve found your cafeteria king.

🛠️ PseudoCode

• Set candidate = 0, count = 0. (Yes, your happiest zero-initialization fantasy.)
• For each number in nums:
  • If count == 0: assign this number as the new candidate, and set count = 1.
  • If this number == candidate: count++.
  • If not: count--.
• After looping, congratulate candidate: they’re your clear winner (because the test guarantees a majority).

💻 The Code

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;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Biggest isn’t best: The numerical maximum might show up once and still lose. Always count frequency.
• Don’t settle for almost-popular: The threshold is strictly more than n/2. No participation trophies here.
• Real-world arrays may lie: Boyer–Moore only works without second-pass validation when the majority exists — which LeetCode 169 guarantees, but life rarely does.
• Space and time: If you’re using extra space or sorting, the interviewer might send you home with a debugging duck as a consolation prize.

🧠 Interviewer Brain-Tattoo

“Finding the majority doesn’t require counting everyone—just enough gladiator rounds for one number to be the last in the arena.”