Majority Element in an Array

Understanding the problem

Given an array A[n] having size n. Find an element whose occurence is more than n/2 times.

Example:

Input: [2,2,2,4,5,4,6,2,4,2]

Output: 2

Brute Force Approach

The Brute Force Approach for identifying the majority element in an array involves exhaustively checking the occurrence of each element in the array and determining if it appears more than n/2 times, where n is the size of the array. This approach iterates through the entire array, keeping track of the count of each element.

Algorithm:

• Start traversing the array in a loop.
• Store the first element in a temp variable
• Check if every other element equals temp.
• If true then increase count of temp
• Finally check if temp is greater than size/2

int majorityElement(int arr[], int n)
{
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (arr[i] == arr[j])
                count++;
        }

        if (count > n/2) {
            return arr[i];
        }
    }
    return -1;
}

Using Hashmap (Better Solution)

In this approach we can use a hashmap to easily get the frequency of each element in the array. The hashmap allows to optimize the calculation of frequency. On iterating the values in hashmap check if the value is greater than n/2.

Algorithm:

• Declare an empty hashmap
• Iterate the array and add each element to hashmap as key.
• If the element is already present then increase the value by 1.
• After all elements are covered then iterate the hashmap
• Access the value in hashmap to check if the value is greater than n/2

int majorityElement(int arr[], int n)
{

    HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

    for(int i = 1; i < n; i++)
    {
        if(hm.containsKey(arr[i]))
        {
            int val = hm.get(arr[i]) + 1;
            hm.put(arr[i], val);
        }
        else
        {
            hm.put(arr[i], 1);
        }
    }

    //iterating hashmap to check if any value is greater than n/2
    for(int i = 1; i < n; i++)
    {
        int count = hm.get(arr[i]) + 1;
        if (count > n / 2)
        {

            return arr[i];
        }
    }

    //if no value found
    return -1;
}

Time Complexity

The algorithm's time complexity is O(NlogN) due to the insertion of N elements in the map, where each insertion takes logN time. Additionally, the count verification step takes O(N) time while traversing the array. The dominant term is O(NlogN), making it an efficient approach for finding the majority element in an array.

Space Complexity

O(N) since we are using a map data structure

Moore's Voting Algorithm (Optimal Solution)

The Majority Element Finding Algorithm aims to identify a majority element in an array, which is defined as an element that appears more than half the size of the array (n/2 times). To accomplish this, the algorithm follows the steps outlined below:

Algorithm:

1. Initialization

   • Initialize a count variable to keep track of the occurrences of the majority element and a variable to store the index of the potential majority element.
   • Start traversing the array from the first element.

2. Increment and Decrement

   • Increment the count if the current element is the same as the element at the index stored as the potential majority element.
   • Decrement the count if the current element is different from the potential majority element.

3. Identification

   • Whenever the count becomes 0 during traversal, update the potential majority element index to the current element's index and set the count to 1 again.

4. Final Determination

   • After the first traversal, traverse the array once again to find the actual count of the potential majority element based on the index obtained in Step 3.
   • If the count of the potential majority element is greater than n/2 (half the size of the array), it qualifies as the majority element, and the algorithm returns this element.
   • If the count is not greater than n/2, there is no majority element in the array.

public int majorityElement(int[] nums) {

    int count = 0;
    int candidate = 0;

    for(int num: nums)
    {
        if(count == 0)
            candidate=num;
        if(num == candidate)
            count++;
        else
            count--;
    }

    return candidate;
}

Time Complexity

The time complexity is O(n) since we are traversing the array once.

Space Complexity

There is no extra space being used so we can say O(1).