Understanding the Problem

The majority element in an array is defined as the element that appears more than n/2 times, where n is the size of the array. Given an array of elements, the task is to find the majority element, if one exists.

For example:

Let array be {1, 5, 6, 7, 9, 7, 5, 1, 7}

Majority Element = 7

Algorithms

Hash Map Approach:

• This approach uses a hash map to store the frequency of each element.
• It then finds the element with a frequency greater than n/2.

Boyer-Moore Voting Algorithm:

• This algorithm uses two variables, candidate and count, to keep track of the current potential majority  element and its count.
• It iterates through the array, updating the candidate and count based on certain conditions.
• If the count becomes zero, it updates the candidate to the current element.
• After the iteration, the candidate is a potential majority element, but it needs verification.

Code Implementation

Hash Map Approach

int majorityElement(vector<int>& nums) {
    unordered_map<int, int> count;
    int n = nums.size();
    for (int num : nums) {
        if (++count[num] > n / 2) {
            return num;
        }
    }
    return -1; // No majority element
}

Boyer-Moore Voting:

int majorityElement(vector<int>& nums) {
    int candidate, count = 0;
    for (int num : nums) {
        if (count == 0) {
            candidate = num;
        }
        count += (num == candidate) ? 1 : -1;
    }
    return candidate;
}

Complexity Analysis

Hash Map Approach:

• Time Complexity - O(n)
• Space Complexity - O(n)

Boyer-Moore Voting Algorithm:

• Time Complexity - O(n)
• Space Complexity - O(1)