Majority Element[Leetcode] Asked in Microsoft/Yahoo/Google/Amazon

Majority element is one of the most asked questions in Coding Interview and today we are going to see brute force to optimal way for solving this particular problem.

Link of the problem :- Problem

Task: Our aim is to find the element having the frequency count of a particular element is greater than the size of input array if there is any majority element then print the element else print 0.

Brute Force: In brute force, we try to run a loop through elements and for each element we are checking its count using count function and check whether it is greater than n/2 where n is the length of the array.

The output should be :

Time complexity: O(n²)

As we are iterating through n element and using count function also take n time.

Space Complexity: O(1), as no extra space used

But if you are trying this on leetcode its lets to time limit exceed error and now you have to find a more optimal approach to crack it.

More Optimal: We may use Hashmap/Hash table/ dictionary whichever you use so that we can get in linear time and we only iterate once but we have to use extra space for the dictionary to store values too so linear time too.

Let’s see the approach: We run through loop and count the frequency of element and store in the dictionary and check-in dictionary of key-value greater than the length of array divided by 2.

The Output :

Time complexity: O(n)

Space complexity: O(n)

But if you are in an interview and the interviewer is not happy and want the way in which constant space is used that space complexity is O(1) then you have to think most optimal way and for this, we have a very famous algorithm called Boyer–Moore majority vote algorithm and if you want to find moore 😊about this check this.

Most optimal: Basically this algorithm says if we find the count of the most occurred element it's always greater then than the length of all elements combined.

eg. [A,B,C,A,A] let’s suppose A, B, C are different countries fighting and to crush A, B and C unties and fight against A.

So right now we Have A = 3, B = 1 and C = 1 as the number of people to fight and if 2 people fight and die is the fight result. Then with 3 people from ‘A’ fights with 2 peoples of ‘B’ and ‘C’ combined leaves, 1 person, from A unharmed and A wins this is the whole intuition of this algorithm.

So this algo. states that if there possible that an element is most occurred in any list its count always greater than the count of all other together.

Now

The output is :

Time Complexity: O(n)

Space Complexity: O(1)

So this ends the today coding question , Follow me to find more.