Program to find Maximum Repeating Element of Array in O(n) Time

• Write a program to find an element occurring maximum number of times in an array.
• How to find maximum repeating element of an array in O(n) time and without using any extra memory space.

Given an integer array of size N, containing elements from 0 to K where k < N. We have to find maximum repeating number in array in O(n) time complexity and O(1) space complexity.

Input Array : [2, 4, 1 ,5, 6, 2, 4, 5, 4, 4]
Maximum Repeating Element : 4
Count : 4

---

Let inputArray be an integer array of size N containing elements from 0 to k(0< k By counting frequency of every element

Algorithm to find maximum repeating element of array by counting occurrence of every element

• We will use two loops to count the frequency of every array element. Outer loop will fix an element and inner loop will traverse the array and count it's occurrence.
• Keep track of the maximum count element found till now and compare it with count of current element.

Time Complexity : O(n²)
Space Complexity : O(1)

C program to find maximum repeating number in O(n²)

#include<stdio.h>
#include<limits.h>

/* This function prints the maximum occuring element of array */
void getMaxCountElement(int *array, int size) {
    int i, j, maxCount, maxElement, count;
    maxCount = INT_MIN;
    /* Count the frequency of every elemenet of array, 
    and check if it is greater than maximum count element 
    we found till now and update it accordingly  */
    for(i = 0; i< size; i++){
    	count = 1;
    	for(j = i+1; j < size; j++){
            if(array[j] == array[i]){
                count++;
                /* If count of current element is more than 
                maxCount, uodate maxCount and maxElement */
                if(count > maxCount){
                    maxCount = count;
                    maxElement = array[j];
                }
            }
        }
    }
    printf("Maximum Repeating Element : %d\nCount : %d",
        maxElement, maxCount);
}
 
int main() {
    int array[10] = {2, 4, 1 ,5, 6, 2, 4, 5, 4, 4};

    getMaxCountElement(array, 10);
    
    return 0;
}

Output

Maximum Repeating Element : 4
Count : 4

---

By using inputArray to store count of elements.

The core logic behind this algorithm is as follows:

• The range of element in inputArray is always less than size of size of inputArray(k < N).
• The count of the element inputArray[i] is stored at index inputArray[i]. For example count of 8 is stored at index 8.
• Traverse inputArray and for every element inputArray[i], increment inputArray[inputArray[i]%K] by K.
• inputArray[i]/K gives the count of i in inputArray.
• Keep track of the maximum count element found till now and compare it with count of current element.

Time Complexity : O(n)
Space Complexity : O(1)

C program to find maximum occurring element in O(n) time and O(1) space

#include<stdio.h>
#include<limits.h>

/* This function prints the maximum occuring element of array */
int getMaxCountElement(int *array, int size, int K) {
    int i, max, maxElementIndex;
    /* For every element array[i], increment 
    array[array[i]%K] by K*/
    for(i = 0; i < size; i++) {
        array[array[i]%K] += K;	
    }
 
    /* Traverse array and find maximum count element */
    max = array[0]; maxElementIndex = 0;
    for (i = 1; i < size; i++) {
        if (array[i]/K > max) {
            max = array[i]/K;
            maxElementIndex = i;
        }
    }

   return maxElementIndex;
}
 
int main() {
    int array[10] = {2, 3, 3, 5, 3, 4, 1, 7};

    printf("Max Repeating Element is %d\n", getMaxCountElement(array, 8, 8));
    
    return 0;
}

Output

Max Repeating Element is 3