Majority Element

Problem Statement

LeetCode-169: Given an array nums of size n, return the majority element.

The majority element is the element that appears more than \(\Bigl\lfloor\frac{n}{2}\Bigr\rfloor\) times. You may assume that the majority element always exists in the array.

Approach

The majority element is the element that appears more than \(\Bigl\lfloor\frac{n}{2}\Bigr\rfloor\) times. This means that the majority element will have a frequency greater than \(\Bigl\lfloor\frac{n}{2}\Bigr\rfloor\).

A simple approach to find the majority element is to use a HashMap to store the frequency of each element in the array. We can iterate over the array and store the frequency of each element in the HashMap. Finally, we can iterate over the HashMap and return the element with a frequency greater than \(\Bigl\lfloor\frac{n}{2}\Bigr\rfloor\).

But a better approach is to use the Boyer-Moore Voting Algorithm to find the majority element in the array. It works based on the intuition of canceling out non-majority elements, leaving only the majority element in the end.

Why It Works?

1. If an element appears more than \(\Bigl\lfloor\frac{n}{2}\Bigr\rfloor\) times, it means its count is greater than all other elements combined.
2. When processing the array, every time a non-majority element is encountered, it “cancels out” one occurrence of the majority element.
3. Since the majority element is present in the array more than all others combined, it will always survive in the end.

Two-Step Process

First Pass (Finding a Candidate):

1. Initialize a variable majorityCandidate to the first element of the array and a variable freq to 1.
2. Iterate over the array from the second element.
3. If the current element is equal to the majorityCandidate, increment the freq by 1.
4. If the current element is not equal to the majorityCandidate, decrement the freq by 1.
5. If the freq becomes 0, update the majorityCandidate to the current element and set the freq to 1.
6. The majorityCandidate at the end of the iteration will be the majority element.

Second Pass (Verification):

1. We count occurrences of the candidate to confirm that it appears more than \(\Bigl\lfloor\frac{n}{2}\Bigr\rfloor\) times.
2. This is necessary because the first pass only guarantees a potential majority element, not a definite one.

Implementation

Here is the code implementation for the approach:

public int majorityElement(int[] nums) {
    int majorityCandidate = nums[0];
    int freq = 1;

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

Complexity Analysis

The time complexity for this approach is \(O(N)\), where \(N\) is the number of elements in the array nums.

When Does It Fail?

It is given in the problem statement that the majority element always exists in the input array. But just in case, there is no majority element, the algorithm will still return a candidate. Example: [1, 2, 3, 4] (no element appears more than ⌊4/2⌋ = 2 times).

In such cases, the optional verification should be able to handle.