Problem Statement

Given an array of integers, the task is to find the majority element. An element is considered a majority element if it appears more than n/2 times in the array, where n is the size of the array.

Examples

Example 1:

Input: arr[] = { 1, 2, 1, 1, 2 }
Output: 1

Example 2:

Input: arr[] = {7, 0, 0, 1, 7, 7, 2, 7, 7}
Output: 7

Explanation: The number 7 appears 5 times in the 9 sized array.

Example 3:

Input: arr[] = {-1, -1, -1, -1}
Output: -1

Different Approaches

1️⃣ Brute Force Approach

This approach involves iterating through all elements of the array and counting the occurrences of each element. After counting, we check if any element occurs more than n/2 times, where n is the size of the array.

Algorithm:

1. Run a loop that select the element of the array one by one.
2. Now for each element, run another loop and count its occurrence in the given array.
3. If any element occurs more than the floor of (N/2), simply return it.

Code:

#include <bits/stdc++.h>
using namespace std;

int majorityElement(vector<int> v) {

    //size of the given array:
    int n = v.size();

    for (int i = 0; i < n; i++) {
        //selected element is v[i]
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            // counting the frequency of v[i]
            if (v[j] == v[i]) {
                cnt++;
            }
        }

        // check if frquency is greater than n/2:
        if (cnt > (n / 2))
            return v[i];
    }

    return -1;
}

int main()
{
    vector<int> arr = {2, 2, 1, 1, 1, 2, 2};
    int ans = majorityElement(arr);
    cout << "The majority element is: " << ans << endl;
    return 0;
}

// Output
The majority element is: 2

Complexity Analysis:

• Time Complexity:O(N^2), where N = size of the given array.
• Space Complexity: O(1), as we are not using any extra space.

2️⃣ Better Approach

Intuition:

The idea is to use a better data structure to reduce the number of look-up operations and hence the reducing the time complexity. Moreover, we have been calculating the count of the same element again and again, so try to reduce that also.

Approach:

1. Use a hashmap and store as (key, value) pairs. Here the key will be the element of the array and the value will be the number of times it occurs.
2. Traverse the array and update the value of the key. Simultaneously check if the value is greater than the floor of N/2. If yes, return the key, otherwise iterate forward.

Code:

#include <bits/stdc++.h>
using namespace std;

int majorityElement(vector<int> v) {

    //size of the given array:
    int n = v.size();

    //declaring a map:
    map<int, int> mpp;

    //storing the elements with its occurnce:
    for (int i = 0; i < n; i++) {
        mpp[v[i]]++;
    }

    //searching for the majority element:
    for (auto it : mpp) {
        if (it.second > (n / 2)) {
            return it.first;
        }
    }

    return -1;
}

int main()
{
    vector<int> arr = {2, 2, 1, 1, 1, 2, 2};
    int ans = majorityElement(arr);
    cout << "The majority element is: " << ans << endl;
    return 0;
}

Complexity Analysis:

Time Complexity: O(N*logN) + O(N) , where N  = size of the given array.

• We are using a map data structure. Insertion in the map takes logN time. Ans we are doing it for N elements. So, it results in the first term O(N * logN). The second O(N) is for checking which element occurs more than floor(N/2) times. If we use unordered_map, the first term will be O(N) for the best and average case and for the worst case, it will be O(N^2).

Space Complexity: O(N) as we are using a map data structure.

3️⃣ Optimal Approach (Moore's Voting Algorithm)

Moore's Voting Algorithm is an efficient algorithm to find the majority element in an array. The key idea behind this algorithm is to cancel out each occurrence of a candidate element with occurrences of other element. After processing all elements in the array, the candidate element that remains will be the majority element.

Intuition:

1. Candidate Selection Phase: You iterate through the array and maintain a candidate for the majority element along with a count. Initially, you assume the first element is the majority candidate and set count = 1. For each subsequent element:
   • If it matches the candidate, increment the count.
   • If it doesn't match, decrement the count. When count reaches zero, pick the current element as the new candidate and reset count to 1.
2. Validation Phase: After finding a candidate in the first pass, you can validate it by counting its occurrences in a second pass to ensure that it occurs more than n/2 times.

Since the problem guarantees the existence of a majority element, we can skip the validation phase if you're confident of the input constraints.

Algorithm:

1. Initialize two variables, candidate and count. Set candidate to the first element of the array and count to 1.
2. Iterate through the array starting from the second element.
3. For each element encountered.
   1. If the current element is equal to the candidate increment count.
   2. If the current element is different from the candidate decrement count.
   3. If count becomes zero, update the candidate to the current element and set count to 1.
4. After iterating through the entire array, the candidate will hold the majority element.

Dry Run:

Initialization

       +-----+-----+-----+-----+-----+-----+-----+
nums = |  2  |  2  |  1  |  1  |  1  |  2  |  2  |
       +-----+-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5     6
          
count = 0
element = null

First Pass

       +-----+-----+-----+-----+-----+-----+-----+
nums = |  2  |  2  |  1  |  1  |  1  |  2  |  2  |
       +-----+-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5     6
          ^
          |
          i
          
count = 1
element = 2

Second Pass

       +-----+-----+-----+-----+-----+-----+-----+
nums = |  2  |  2  |  1  |  1  |  1  |  2  |  2  |
       +-----+-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5     6
                ^
                |
                i
count = 1
element = 2
since, nums[i] == element
       count++
       element = 2

Third Pass

       +-----+-----+-----+-----+-----+-----+-----+
nums = |  2  |  2  |  1  |  1  |  1  |  2  |  2  |
       +-----+-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5     6
                      ^
                      |
                      i
count = 2
element = 2
since, nums[i] != element
       count--
       element = 2

Fourth Pass

       +-----+-----+-----+-----+-----+-----+-----+
nums = |  2  |  2  |  1  |  1  |  1  |  2  |  2  |
       +-----+-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5     6
                            ^
                            |
                            i
count = 1
element = 2
since, nums[i] != element
       count--
       element = 2

Fifth Pass

       +-----+-----+-----+-----+-----+-----+-----+
nums = |  2  |  2  |  1  |  1  |  1  |  2  |  2  |
       +-----+-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5     6
                                  ^
                                  |
                                  i
count = 0
element = 2
since, nums[i] != element and count === 0, hence
       update element to nums[i] and count++
       count++
       element = nums[i] = 1

Sixth Pass

       +-----+-----+-----+-----+-----+-----+-----+
nums = |  2  |  2  |  1  |  1  |  1  |  2  |  2  |
       +-----+-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5     6
                                        ^
                                        |
                                        i
count = 1
element = 1
since, nums[i] != element
       count--
       element = 1

Seventh Pass

       +-----+-----+-----+-----+-----+-----+-----+
nums = |  2  |  2  |  1  |  1  |  1  |  2  |  2  |
       +-----+-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5     6
                                              ^
                                              |
                                              i
count = 0
element = 1
since, nums[i] != element and count === 0, hence
       update element to nums[i] and count++
       count++
       element = nums[i] = 2

Loop Termination

       +-----+-----+-----+-----+-----+-----+-----+
nums = |  2  |  2  |  1  |  1  |  1  |  2  |  2  |
       +-----+-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5     6
                                                     ^
                                                     |
                                                     i
count = 1
element = 2

since, i has crossed the array bounds, the loop will
terminate here.
Return the element.

Code:

#include <bits/stdc++.h>
using namespace std;

int majorityElement(vector<int> v) {

    //size of the given array:
    int n = v.size();
    int cnt = 0; // count
    int el; // Element

    // Step 1: Find a Candidate
    for (int i = 0; i < n; i++) {
        if (cnt == 0) {
            cnt = 1;
            el = v[i];
        }
        else if (el == v[i]) cnt++;
        else cnt--;
    }

    // Step 2: (Optional) Validation phase to verfiy the candidate.
    // checking if the stored element
    // is the majority element:
    int cnt1 = 0;
    for (int i = 0; i < n; i++) {
        if (v[i] == el) cnt1++;
    }

    if (cnt1 > (n / 2)) return el;
    return -1;
}

int main()
{
    vector<int> arr = {2, 2, 1, 1, 1, 2, 2};
    int ans = majorityElement(arr);
    cout << "The majority element is: " << ans << endl;
    return 0;
}

// Output
Majority Element: 4

Complexity Analysis:

Time Complexity:O(N) + O(N), where N = size of the given array.

• The first O(N) is to calculate the count an find the expected majority element. The second one is to check if the expected element is the majority one or not.

Note: If the question states that the array must contain a majority element, in that case, we do not need the second check. Then the time complexity will be O(N)

Space Complexity:O(1) as we are not using any extra space.