Saturday, January 18, 2014

Finding the max repeated element in an array

Problem : Find the element which occurs maximum number of times.

METHOD 1 : Sorting the array and scanning the array
The simple solution is to
1) Sort the array
2) Scan the array such that keep the track of the elements which occurred max number of times

METHOD 2 : Using Binary Search Tree

We can have a binary search tree with an extra field count, which indicates the number of times an element appeared in the input. 
Node of the Binary Search Tree (used in this approach) will be as follows.

struct tree
  int element;
  int count;

1) Insert elements in BST one by one and if an element is already present then increment the count of the node.
2) Now do the inorder traversal on the tree, keeping track of the count and value of max element in the tree.

Time complexity - O(n) + O(n) ≈ O(n). First for contructing the tree and second for inorder traversal.

Space complexity - O(2n)  ≈ O(n), since every node needs 2 extra pointers.

METHOD 3 : Using Hashtable
Use a counter for each elements, as value and key as the element in the hashtable. At the end just retun the element having max counter.

Time complexity - O(n) and space complexity O(n) needed for storing in hashtable.



Post a Comment