Be the first user to complete this post

  • 0
 Add to List
Medium

235. Majority Element- Boyer–Moore majority vote algorithm

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

Majority Element: If an element appears more than n/2 times in array where n is the size of the array.

Example:

int [] arrA = {1,3,5,5,5,5,4,1,5};
Output: Element appearing more than n/2 times: 5

int []arrA = {1,2,3,4};
Output: No element appearing more than n/2 time

Earlier we have seen Majority Element solutions using hash map and sorting. In this article, we will see O(n) solution with constant extra space.

Approach: Boyer–Moore majority vote algorithm

In its simplest form, the algorithm finds a majority element, if there is one: that is, an element that occurs repeatedly for more than half of the elements of the input. However, if there is no majority, the algorithm will not detect that fact, and will still output one of the elements. A version of the algorithm that makes a second pass through the data can be used to verify that the element found in the first pass really is a majority. Source - wiki

As per the above algorithm, we can divide our implementation into two parts

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

First iteration - Find the element which could be a majority element

  • Say Array has 10 elements and say element x appears 6 times. Rest of the elements count = 4. If we start to cancel out each occurrence of x with the rest of the elements, still at the end we will have some count of x remaining. In our example (6-4 =2, x count )
  • Iterate through the array and maintain the count of majority_element.(starts with the first element in the array.)
  • If the next element is the same then increment the count
  • If the next element is not the 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.

The second iteration – check the element (found in the first iteration) count is greater than n/2

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

Time Complexity: O(n), Space Complexity: O(1)

Example:

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.

Output:

 Element appearing more than n/2 times: 5

Reference: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm

Related Problems: