Problem

Given an array of integers occurring between range[0, n) where n is length of the array, write a algorithm to find the element which appears maximum number of times in the array.

Examples

Example 1:

1
2
3

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

Solution

We have discussed the solutions like nested loops, sorting and hashmap here - Find most frequent element in the array.

As this is special case, we can use array as hashmap, and use array index to track the elements.

[!NOTE] This solution works only if array has positive integers and all the elements in the array are in range from 0 to n-1 where n is the size of the array.

Method 1 - Using Index to track count

Algorithm

Here is the algorithm:

  • Nav­i­gate the array.
  • Update the array as for i’th index :- nums[nums[i]% n] = nums[nums[i]% n] + n;
  • Now navigate the updated array and check which index has the maximum value, that index number is the element which has the maximum occurrence in the array.
  • See the picture below for more explanation.

This solution is similar to Check if Array is Consecutive Integers.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public int maxRepeatingElement(int[] nums) {
	int n = nums.length;
	int maxCnt = 0;
	int maxIdx = 0;

	for (int i = 0; i < n; i++) {
		//get the index to be updated
		int idx = nums[i] % n;
		nums[idx] = nums[idx] + n;
	}

	for (int i = 0; i < n; i++) {
		if (nums[i] / n > maxCnt) {
			maxCnt = nums[i] / n;
			maxIdx = i;
		}
	}

	return maxIdx;
}

Complexity

  • O(n) - For looping on array twice
  • O(1) - As we don’t use any extra space, and reuse array instead