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

Find the element which appears maximum number of times in the array.

Objec­tive: Given an array of inte­gers, write a algo­rithm to find the ele­ment which appears max­i­mum num­ber of times in the array.

Exam­ple:

int [] arrA = {4, 1, 5, 2, 1, 5, 9, 8, 6, 5, 3, 2, 4, 7};
Output: Element repeating maximum no of times: 5, maximum count: 3

Approach:

Naive approach: Use 2 loops. Check each ele­ment in the array with all other ele­ments in the array and keep track of its count and also main­tain the max counter which track the ele­ment repeats the max­i­mum num­ber of time.

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

Code:

 

Sort­ing approach: Sort the array, this will bring all the dupli­cates together if present. Now nav­i­gate the array and keep track of its count and also main­tain the max counter which track the ele­ment repeats the max­i­mum num­ber of time.

Time Com­plex­ity : O(nlogn) Space Com­plex­ity: O(n) by using merge sort.

Code:

 

Bet­ter Solu­tion : Use Hashmap. Store the count of each ele­ment of array in a hash table and later check in Hash map which ele­ment has the max­i­mum count — Find dupli­cates in an given array

Time Com­plex­ity : O(n) and Space Com­plex­ity: O(n).

Code:

 

Bet­ter Solu­tion (Con­di­tional) : O(n) time and O(1) extra space.

  • This solu­tion works only if array has pos­i­tive inte­gers and all the ele­ments in the array are in range from 0 to n-1 where n is the size of the array.
  • Nav­i­gate the array.
  • Update the array as for ith index :- arrA[arrA[i]% n] = arrA[arrA[i]% n] + n;
  • Now nav­i­gate the updated array and check which index has the max­i­mum value, that index num­ber is the ele­ment which has the max­i­mum occur­rence in the array.
  • See the pic­ture below for more explanation.

 

Sim­i­lar approach used in prob­lem : if array has all con­sec­u­tive numbers.

Code:

Out­put:

Element repeating maximum no of times: 5, maximum count: 3

You may also like...