Problem

Given an array of integers, write a algorithm to find the element which appears maximum number of times in the array.

Examples

Example 1:

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

Similar Problem

Find the element which appears maximum number of times in the ranged array0, n)

Solution

Lets discuss the solution.

Method 1 - Use 2 loops

Check each element in the array with all other elements in the array and keep track of its count and also maintain the max counter which track the element repeats the maximum number of time.

Code

Java
public void MaxRepeatingElement(int[] arrA) {
	int maxCounter = 0;
	int element = 0;

	for (int i = 0; i < arrA.length; i++) {
		int counter = 1;

		for (int j = i + 1; j < arrA.length; j++) {
			if (arrA[i] == arrA[j]) {
				counter++;
			}
		}

		if (maxCounter < counter) {
			maxCounter = counter;
			element = arrA[i];
		}
	}

	System.out.println("Element repeating maximum no of times: " + element + ", maximum count: " + maxCounter);
}

Complexity

  • Time Complexity : O(n^2)
  • Space Complexity: O(1)

Method 2 - Sorting

Sort the array, this will bring all the duplicates together if present. Now navigate the array and keep track of its count and also maintain the max counter which track the element repeats the maximum number of time.

Code

Java
public void maxRepeatingElementUsingSorting(int[] arrA) {
	if (arrA.length < 1) {
		System.out.println("Inavlid Array");
		return;
	}

	Arrays.sort(arrA);
	int count = 1;
	int maxCount = 1;
	int currentElement = arrA[0];
	int maxCountElement = arrA[0];

	for (int i = 1; i < arrA.length; i++) {
		if (currentElement == arrA[i]) {
			count++;
		} else {
			if (count > maxCount) {
				maxCount = count;
				maxCountElement = currentElement;
			}

			currentElement = arrA[i];
			count = 1;
		}
	}

	System.out.println("Element repeating maximum no of times: " + maxCountElement + ", maximum count: " + maxCount);
}

Complexity

  • Time Complexity : O(nlogn)
  • Space Complexity: O(n) by using merge sort.

Method 3 - Use Hashmap

Store the count of each element of array in a hash table and later check in Hash map which element has the maximum count.

Code

Java
public void maxRepeatingElementUsingMap(int[] arrA) {
	//Will store each character and it's count
	HashMap<Integer, Integer> map = new HashMap<>();

	for (int i = 0; i < arrA.length; i++) {
		if (map.containsKey(arrA[i])) {
			map.put(arrA[i], map.get(arrA[i]) + 1);
		} else {
			map.put(arrA[i], 1);
		}
	}

	//traverse the map and track the element which has max count
	Iterator entries = map.entrySet().iterator();
	int maxCount = 0;
	int element = arrA[0];

	while (entries.hasNext()) {
		Map.Entry entry = (Map.Entry) entries.next();
		int count = (Integer) entry.getValue();

		if (maxCount < count) {
			maxCount = count;
			element = (Integer) entry.getKey();
		}
	}

	System.out.println("Element repeating maximum no of times: " + element + ", maximum count: " + maxCount);
}

Complexity

  • Time Complexity : O(n)
  • Space Complexity: O(n).

Method 4 - 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.

class TreeNode {
	int val;
	int count;
	TreeNode left;
	TreeNode right;
}
  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.

Complexity

  • Time complexity - O(n) + O(n) ≈ O(n). First for constructing the tree and second for inorder traversal.
  • Space complexity - O(2n)  ≈ O(n), since every node needs 2 extra pointers.