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. The algorithm works as follows:

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.

The algorithm works because the majority element will have a frequency greater than \(\Bigl\lfloor\frac{n}{2}\Bigr\rfloor\) - say x and all other elements will have a frequency less than or equal to x. The Boyer-Moore Voting Algorithm ensures that the majority element is the only element left at the end of the iteration.

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.