Majority element in integer array (Boyer Moore’s voting algorithm) in java

What is majority element in integer array?

• Given an integer elements, find the majority element in an array.
• We will find majority element using Boyer–Moore majority vote algorithm.
• The elements which exists more the half of elements in an array is a majority element in an array..

Examples: find majority element in integer array (java)

Example 1:

• Given an array { 21, 23, 21, 23, 21 } of length 5.
• Majority elements should exists more than half.
  • Occurrence of majority elements should be more 5/2 i.e. 2.
• In an array 21 appears 3 times, 23 & 24 appears only once.
• Clearly 21 exists more than half of elements in an array.
• Element 21 is a majority element.

Example 2:

• Given an array { 41, 42, 43, 41 } of length 4.
• Majority elements should exists more than half.
  • Occurrence of majority elements should be more 4/2 i.e. 2.
• In an array 41 appears 2 times & 42,43 appears only once.
• No element occurs more than 2.
• There is no majority element exists in an array.

Boyer – Moore majority vote algorithm:

• Boyer Moore voting algorithm is based upon cancelling technique.
• Declare the counter and candidate element.
• Iterate through the elements of array.
  • If counter is zero
    • Note down the candidate element & increment the counter
  • If counter is not equal to zero
    • If current element in iteration is same as candidate element
      • increment the counter
    • else decrements the counter
• end of iteration.
• If counter is zero, then there is no majority element in array.
• Now, check whether candidate element is a majority element.
  • Candidate element should occurs more than n/2 times.
  • If yes, we found the majority element.
• Time complexity of algorithm is O (n)

Program: Majority element in integer array  – Boyer Moore Algorithm (Java)

package org.learn.arrays;

import java.util.Arrays;

public class BoyerMooreMajorityElements {

	public static void main(String[] args) {

		int elements[] = { 41, 42, 43, 41 };
		int element = majorityElement(elements);
		String arrString = Arrays.toString(elements);
		if (element > -1) {
			System.out.printf("1. Majority element in an array %s is: %d", arrString, element);
		} else {
			System.out.printf("1. No majority element found in an array : %s", arrString);
		}

		elements = new int[] { 21, 23, 21, 23, 21 };
		element = majorityElement(elements);
		arrString = Arrays.toString(elements);
		if (element > -1) {
			System.out.printf("\n2. Majority element in an array %s is: %d", arrString, element);
		} else {
			System.out.printf("\n2. No majority element found in an array : %s", arrString);
		}
	}

	private static int majorityElement(int[] arr) {
		int element = -1;
		int counter = 0;
		int length = arr.length;
		int index = 0;
		while (index < length) {
			if (counter == 0) {
				element = arr[index];
				counter++;
			} else if (element == arr[index]) {
				counter++;
			} else {
				counter--;
			}
			index++;
		}

		if (counter == 0) {
			// No majority element found
			return -1;
		}

		index = -1;
		counter = 0;
		while (++index < length) {
			if (element == arr[index]) {
				counter++;
			}
		}

		if (counter > length / 2)
			return element;

		return -1;
	}
}

Output: majority element using Boyer–Moore vote algorithm in java

1. No majority element found in an array [41, 42, 43, 41]
2. Majority element in an array [21, 23, 21, 23, 21] is: 21