Majority Element

Description

Majority Element
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Approach 1: Brute Force (HashMap / Counting)

Intuition
Count the occurrences of each element using a frequency map and return the element whose frequency is strictly greater than $\lfloor n/2\rfloor$.

import java.util.HashMap;
 
class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> counts = new HashMap<>();
        int n = nums.length;
        
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
            if (counts.get(num) > n / 2) {
                return num;
            }
        }
        
        return -1;
    }
}
 

• Time Complexity: $O(n)$ — Single pass through the array.
• Space Complexity: $O(n)$ — Hash map stores up to $n$ elements.

---

Approach 2: Most Optimal & Intuitive (Boyer-Moore Voting Algorithm)

Intuition
Think of this as a battle royale:

• Pick a candidate: When count is $0$, pick the current element as your new candidate.

• Traverse through the array:

• If the next number matches your candidate, increment count ($+1$).

• If it’s different, decrement count ($-1$).

• If count drops to $0$, it means all previous elements canceled each other out. Pick the current element as the new candidate and reset count to $1$.

Because the majority element appears more than half the time ($>n/2$), its total count will always survive all canceling pairs and be left standing at the end.

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

• Time Complexity: $O(n)$ — Single pass through the array.
• Space Complexity: $O(1)$ — Only requires two integer variables.

The Mathematical Guarantee

• In Majority Element I ($>n/2$), a true majority candidate owns more than $50\%$ of the entire array.
• Every time a candidate’s count decreases (or they get replaced when count == 0), it requires a 1-on-1 mutual cancellation with a different element.
• Since non-majority elements make up less than $50\%$ of the total array, there literally aren’t enough non-majority elements in existence to cancel out every single copy of the true majority candidate.
  Even if the majority candidate gets wiped off the stage temporarily (count = 0), the remaining array contains a massive “reservoir” of their voters down the line. They will inevitably storm back, clear out any impostors, and hold the seat at the very end.