Majority Element

Arrays, Adhoc

Problem Statement:
Given a array of N elements. Find the element that is present majorly in the array(i. e element that is present more than N / 2).

Brute-force Approach:
Since the problem deals with frequency of elements, we can use hash tables to count the frequency of every element present in the array.

Then, let’s iterate through the hash table and check any element count is greater than or equal to N / 2. If an element that satisfies the condition, we’ll return it otherwise just return -1 since we can’t find the required element.

int majorityElement(vector<int>& nums) {
        
    int n = nums.size();

    map<int, int> hash;
    for(auto &el : nums){
        hash[el]++;
    }

    for(auto &pair: hash){
        if(pair.second > n / 2){
            return pair.first;
        }
    }

    return -1;

}

Time Complexity:
O(N) — where N is number of elements in the array

Space Complexity:
O(N) — where N is number of elements in the array that we stored in hash table.

Optimal Approach:
Before jumping to the approach, it is must to know a specific algorithm to move forward. Learn about Boyer-Moore voting algorithm. This strategies shows that we can always find an element which is present majority element using constant space and linear time complexity

1. We can assume first element is the majority element and initialize count variable that’ll hold the frequency of current major element.
2. Iterate through the array. If current element is major element, we’ll increment count by 1 otherwise decrement count by 1.
3. NOTE: If count is exhausted (i.e count = 0), this logically means the major element we considered is no longer a major element. So, let’s updated major to current element in loop. Now increment count by 1, since major is updated to new element.
4. Repeat 2–3 until the entire array is exhausted.
5. Return major.

int majorityElement(vector<int>& nums) {
        
    int major = nums[0], cnt = 0;

    for(int i = 0; i < nums.size(); i++){

        if(nums[i] == major){
            cnt++;
        } else {
            cnt--;
        }

        if(cnt == 0){
            major = nums[i];
            cnt++;
        }

    }

    return major;

}

Time Complexity:
O(n) — where N is number of elements in the array

Space Complexity:
O(1) — no extra space is required.