Algorithm Day98 - Majority Element

🧩 Problem

LeetCode 169 - 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.

Example:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

💡 Idea

There are multiple approaches:

1. Sorting → The middle element is the majority.
2. HashMap counting → Count frequencies.
3. Boyer–Moore Majority Vote Algorithm → O(n) time, O(1) space (most optimal).

Boyer–Moore Explanation

We maintain a candidate and a count.

• If count is 0, set the current number as candidate.
• If the current number equals candidate, increment count; otherwise, decrement count.
  At the end, candidate is the majority element.

Example

nums = [2,2,1,1,1,2,2]
candidate=2, count=1
=> final candidate = 2

💻 Java Code

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

🧠 Complexity

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

🏁 Summary

The Boyer–Moore algorithm is elegant and efficient — it eliminates the need for extra storage by leveraging the majority element’s dominance in occurrence.