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 – Part 1

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 times

Click here to read O(n) approach-Boyer–Moore major­ity vote algorithm

Approach 1: Brute Force

Use nested for loops and count each ele­ment and if count>n/2 for each element.

Time Com­plex­ity: O(n^2)

Code:

Approach 2: Hash Map

  • Store the count of each ele­ment in Hash map.
  • Iter­ate through hash map and check if any ele­ment has count >n/2

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

Code:

Approach 3: Sorting

  • Sort array, this will bring all the same ele­ments together.
  • Iter­ate through array and check if any ele­ment has count >n/2

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

Code:

Out­put:

Element appearing more than n/2 times: 5

You may also like...

  • lipsa patel

    In Nested Loop approach, break the loop after found=true;