Majority Frequency Element

We have an array of intergers a[]. Our task is to find the majority element in the array.

A majority element in an array a[] of size n is an element that appears more than n/2 times. So there will be at most one such element.

Example 1

Input : a[]={3, 3, 6, 2, 6, 6, 2, 6, 6}

Output : 6

Explanation: The frequency of 6 is 5 which is greater than the half of the size of the array size.

Example 2

Input : a[] = {3, 3, 6, 2, 6, 6, 2, 6}

Output : No Majority Element

Explanation: There is no element whose frequency is greater than the half of the size of the array size.

Approach

Approach to finding the majority element in an array is to use the Boyer-Moore Majority Vote Algorithm, which is an efficient and clever algorithm that doesn't require sorting or additional data structures

1. Initialize two variables: candidate and count. The candidate represents the current element under consideration as a potential majority element, and count is used to keep track of how many times the candidate has been seen so far. Initially, both are set to null or 0.
2. Iterate through the array one element at a time.
3. For each element in the array:
   1. f count is 0, set the current element as the new candidate and increment count to 1.
   2. If the current element is the same as the candidate, increment count by 1.
   3. If the current element is different from the candidate, decrement count by 1.

4. After iterating through the entire array, the candidate variable will hold the element that is most likely the majority element.
5. To confirm if the candidate is indeed the majority element, iterate through the array again and count the occurrences of the candidate.
6. If the count of the candidate is greater than n/2 (where n is the size of the array), it is considered the majority element. Otherwise, there is no majority element in the array.

Complexity

• Time Complexity: O(N), where N is the number of elements in the array.
• Space Complexity: O(1), because the code uses a fixed number of variables

Code

#Java Code

public class MajorityElementFinder {

    public int findMajorityElement(int[] nums) {

        int candidate = 0;
        int count = 0;

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


    public boolean isMajorityElement(int[] nums, int candidate) {

        int count = 0;
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }
        return count > nums.length / 2;
    }


    public static void main(String[] args) {
        MajorityElementFinder finder = new MajorityElementFinder();
        int[] arr = {3, 3, 6, 2, 6, 6, 2, 6, 6};
        int majorityCandidate = finder.findMajorityElement(arr);


        if (finder.isMajorityElement(arr, majorityCandidate)) {
            System.out.println("The majority element is " + majorityCandidate);
        } else {
            System.out.println("There is no majority element in the array.");
        }
    }
}

Output

The majority element is 6