Problem

Given an array of integer write an algorithm to find the majority element in it (if exist).

Boyer Moore Majority Vote Algorithm

We have already seen the problem and some solutions - Majority Element 1 - with n by 2 definition

In this article we will see O(n) solution with constant extra space.

As per above algorithm we can divide out implementation into two parts

  1. First iteration – Find the element which could be a majority element.
  2. Second iteration – check the element(found in first iteration) count is greater than n/2

First Iteration – Find the Element Which Could Be a Majority Element

  • Iterate through array and maintain the count of majority_element.(starts with first element in the array.)
  • If next element is same then increment the count
  • If next element is not same then decrement the count.
  • If count becomes zero then majority_element = current element, count =1.
  • After the first iteration majority_element will be the candidate which might have the count > n/2.

Second Iteration – Check the Element (found in First iteration) Count is Greater Than n/2

  • Iterate through array and get the count of element found in first step. If count is >n/2 then print it.
  • If count is less than n/2 then ignore it, array does not have majority element.

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Code

Java

public int majorityElement(int[] arrA) {
	int size = arrA.length;
	if (size == 0)
		return;

	int majorityElement = arrA[0];
	int count = 1;
	for (int i = 1; i<size; i++) {
		if (majorityElement == arrA[i]) {
			count++;
		} else if (count == 0) {
			majorityElement = arrA[i];
			count = 1;
		} else {
			count--;
		}
	}
	//check if majorityElement is appearing more than n/2 times
	count = 0;
	for (int i = 0; i<size; i++) {
		if (arrA[i] == majorityElement) {
			count++;
		}
	}
	if (count > size / 2)
		return majorityElement;
	else
		return -1;
}

Dry Run

First Iteration:

int [] arrA = {5,3,3,5,5,1,5};
i = 0, majority_element = 5
count  = 1

int [] arrA = {5,3,3,5,5,1,5};
i = 1, current_element=3, majority_element = 5
count=0 (current element is not same, count = count -1)

int [] arrA = {5,3,3,5,5,1,5};
i = 2, current_element=3, majority_element = 3
count=1 (count was 0 so, majority_element = current_element)

int [] arrA = {5,3,3,5,5,1,5};
i = 3, current_element=5, majority_element= 3
count=0(current element is not same, count = count-1)

int [] arrA = {5,3,3,5,5,1,5};
i = 4 current_element=5, majority_element= 5
count = 1(count was 0 so, majority_element = current_element)

int [] arrA = {5,3,3,5,5,1,5};
i = 5, current_element=1, majority_element= 5,
count=0(current element is not same, count = count-1)

int [] arrA = {5,3,3,5,5,1,5};
i = 6, current_element=5, majority_element= 5
count = 1(count was 0 so, majority_element = current_element)

Now majority_element = 5,

Do the second iteration and check the count of 5.

What if majority element is guaranteed

In Leetcode problem, Majority element is guaranteed, so we don’t need second pass:

public int majorityElement(int[] nums) {
	int result = 0, count = 0;

	for (int i = 0; i<nums.length; i++) {
		if (count == 0) {
			result = nums[i];
			count = 1;
		} else if (result == nums[i]) {
			count++;
		} else {
			count--;
		}
	}

	return result;
}

Why We Need Second Pass?

I think the following intuition for the Boyer-Moore algorithm might shed some light on why two passes are necessary.

The algorithm is based on the following idea. Imagine each element of your array is a person in a room holding a card with a number on it. Each person in the room wanders around until they meet someone else. If the two people are holding different numbers, they each sit down. Otherwise, they keep moving around until they encounter someone else. Eventually, some number of people will be left standing.

If there is a true majority element, the group of the last people standing will definitely have the majority element because no matter how people pair off there’s too many people in the majority for all of them to have been eliminated. But if there isn’t a majority, there could still be someone left standing at the end holding a non-majority element. For example, maybe they just happened to have not encountered anyone with a different value while everyone else sat down.

The reason for the second pass is to differentiate between these two cases. If there is a majority at all, it has to end up as the final candidate. If there isn’t, something might still end up as the final candidate and you need to rule that case out.