Majority Element - (Boyer-Moore-Voting-Algo)

Problem Link

Majority Element – LeetCode

Problem: Majority Element

Problem Statement

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times.
It is guaranteed that the majority element always exists.

Examples

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

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

Constraints

• n == nums.length

• 1 <= n <= 5 * 10⁴

• -10⁹ <= nums[i] <= 10⁹

• A majority element always exists

Intuition

The problem asks for an element that appears more than half the time in the array.

A greedy cancellation approach (Boyer-Moore Voting Algorithm) can be used to solve it in O(n) time and O(1) space.

Approach

Boyer-Moore Voting Algorithm

1. Initialize candidate with the first element and set votes = 1.

2. Iterate over the array:

   • If the current number is equal to the candidate, increment the vote.

   • If it's different, decrement the vote.

   • If the vote drops to 0, change the candidate to the current number and reset vote to 1.

3. At the end, the candidate will be the majority element (guaranteed by the problem).

Code (Java – Optimal O(n) Time, O(1) Space)

class Solution {
    public int majorityElement(int[] nums) {
        int candi = nums[0];
        int vote = 1;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == candi) {
                vote++;
            } else if (vote == 0) {
                candi = nums[i];
                vote = 1;
            } else {
                vote--;
            }
        }

        return candi;
    }
}

Time and Space Complexity

• Time Complexity: O(n)

• Space Complexity: O(1)

Brute Force Approach

Idea

Use a HashMap to count the frequency of each element. Return the one whose count exceeds n / 2.

Code (Java – Brute Force)

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int threshold = nums.length / 2;

        for (int num : nums) {
            int freq = map.getOrDefault(num, 0) + 1;
            map.put(num, freq);
            if (freq > threshold) return num;
        }

        return -1;
    }
}

• Time Complexity: O(n)

• Space Complexity: O(n)

Dry Run of Boyer-Moore

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

Result: 2

Conclusion

The Boyer-Moore Voting Algorithm is a highly efficient and elegant solution for the majority element problem. It leverages the fact that the majority element is guaranteed to exist and cancels out minority elements to find the correct one in linear time and constant space.