Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Majority Element– Boyer–Moore majority vote algorithm

Objec­tive:  Given an array of inte­ger write an algo­rithm to find the major­ity ele­ment in it (if exist).

Major­ity Ele­ment: If an ele­ment appears more than n/2 times in array where n is the size of the array.

Exam­ple:

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

Ear­lier we have seen Major­ity Ele­ment solu­tions using hash map and sort­ing. In this arti­cle we will see O(n) solu­tion with con­stant extra space.

Approach: Boyer–Moore major­ity vote algorithm

In its sim­plest form, the algo­rithm finds a major­ity ele­ment, if there is one: that is, an ele­ment that occurs repeat­edly for more than half of the ele­ments of the input. How­ever, if there is no major­ity, the algo­rithm will not detect that fact, and will still out­put one of the ele­ments. A ver­sion of the algo­rithm that makes a sec­ond pass through the data can be used to ver­ify that the ele­ment found in the first pass really is a major­ity. Sourcewiki

As per above algo­rithm we can divide out imple­men­ta­tion into two parts

  1. First iter­a­tion — Find the ele­ment which could be a major­ity element.
  2. Sec­ond iter­a­tion – check the element(found in first iter­a­tion) count is greater than n/2

First iter­a­tion — Find the ele­ment which could be a major­ity element

  • Say Array has 10 ele­ments and say ele­ment x appears 6 times. Rest of the ele­ments count = 4. If we start can­cel out each occur­rence of x with rest of the ele­ments, still at the end we will have some count of x remain­ing. In our exam­ple (6–4 =2, x count )
  • Iter­ate through array and main­tain the count of majority_element.(starts with first ele­ment in the array.)
  • If next ele­ment is same then incre­ment the count
  • If next ele­ment is not same then decre­ment the count.
  • If count becomes zero then majority_element = cur­rent ele­ment, count =1.
  • After the first iter­a­tion majority_element will be the can­di­date which might have the count > n/2.

Sec­ond iter­a­tion – check the ele­ment (found in first iter­a­tion) count is greater than n/2

  • Iter­ate through array and get the count of ele­ment 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 major­ity element.

Time Com­plex­ity: O(n), Space Com­plex­ity: O(1)

Exam­ple:

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.

Code:

Out­put:

 Element appearing more than n/2 times: 5

Ref­er­ence: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm

You may also like...