We are given an array and we want to find its majority element, if it has one, using a divide-and-conquer algorithm in O(n*log.n).

A majority element of an n-sized array is defined as an element that appears more than n/2 times.

Solution

We will keep dividing the array into half until we reach an array of size two and we will compare the two elements of each array. If they are the same, they are the majority element of that array and we will return their value. If they are not the same, we will return a special character to signify that there is no majority element.

Moving recursively up the arrays, we will check the values we get from the two child-arrays/halves. As with the base case above, if the elements are the same, we return them, otherwise we return the special character.

Essentially we are checking two elements each time and if they are the same we keep them, while otherwise we discard them.

This is a simple example of a “Divide and Conquer” algorithm which showcases how to use the particular technique to our advantage. We have a big problem which will be easier to solve if we break it up into smaller problems. We keep breaking the problem up until we get to a base case (here the 2-element array) which we can trivially solve and then recursively propagate the solution up until we solve the original problem.

You can find the code here.

NOTE: This particular problem also has an O(n) solution without the use of divide-and-conquer. Can you find it?

Advertisements

4 thoughts on “Divide and Conquer – Find Majority Element

  1. I’ve tried to implement your solution but it doesn’t work for me if the sequence I’m analysing is something like: “2 3 2 9 2”. Should your algorithm work for this case too?

    Like

    1. Hi Raul.

      The algorithm I noted actually only works for input with length a power of two. I made it that way since that is how most textbooks have it.

      It is easy to fix by simply checking if the length of the input is 1 instead of 2 (that means an ‘odd’ element was found).

      Since I feel your confusion is justified, I have amended my code: https://github.com/MrDupin/Algorithms/blob/master/Divide%20and%20Conquer/FindMajorityElement.py

      Thanks for letting me know!

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s