Find the Maximum Repeating Number in O(N) Time and O(1) Extra Space

Introduction

In this blog, we will take up a coding challenge which is seemingly very easy to complete. However, it becomes increasingly difficult to solve the problem when the constraints are put forward. We will find the maximum repeating element in the array and try to come up with a solution within the given constraints. Apart from this, we will also discuss the easy-approaches to solve the problem but outside of the constraints.

Problem Statement

Ninja has given you an array of size N and a number K. It is assumed that all elements in the array are in the range [0, K - 1] and K <= N. Your task is to find the maximum repeating element in the array in O(N) time and O(1) space. So without wasting time, let’s get started.

Sample Examples

Input

Enter the size of the array: 5

Enter the elements of the array (space-separated): 2 2 1 3 4

Enter the value of K: 5

Output: 2

Explanation: As it is visible, 2 is the maximum repeating element, occurring twice.

Input 2

Enter the size of the array: 7

Enter the elements of the array (space-separated): 3 2 1 3 4 1 3

Enter the value of K: 6

Output: 3

Explanation: As it is visible, 3 is the maximum repeating element, occurring thrice.

Also see, Euclid GCD Algorithm

Approach

Naive Approach: If we forget the constraints for a moment, we could find the maximum repeating element in a variety of ways. We could run two for loops (nested) over the array elements and count the occurrences of each array element in each iteration of the inner for loop. Then we can find the element with the highest number of occurrences. The time complexity of this approach is, however, O(N ^ 2) and space complexity is O(1), where N is the size of the input array.

Efficient Approach: To improve the time complexity of finding the maximum repeating element, we can create an array FREQ of size K. Now, we can loop over the array elements and increment FREQ[ARR[IND]] by one, where ARR is the input array and IND is the iterator. We can do this because it is given that all elements of the array are less than K. Now, we can simply pick the index with maximum value and output it as the maximum repeating element. But again, the time complexity of this approach is O(N) (great improvement!) and the space complexity is O(K) due to the FREQ array so created.We missed it by a little margin!

So let us now discuss the final solution to find the maximum repeating element. We can iterate over the input array ARR and increment ARR[ARR[IND] % K] by K, where IND is the iterator. Now, we can output the index with the maximum value as the answer. Time and Space complexity are within the constraints, i.e., O(N) and O(1) respectively.

Why does it work?

Few points to keep in mind:

1. By incrementing the array elements by K, we are not changing the value of this expression: ARR[IND] % K.
2. The element with most occurrences will have its index incremented the most number of times.
3. Since all the elements are below K, we can identify the maximum repeating element by the index which holds the maximum value. As maximum value is analogous to maximum number of increments.

Algorithm

1. Take the input array and the value of K.
2. Iterate over the array with IND as the iterating variable.
   1. Increment ARR[ARR[IND] % K] by K.
3. Find the index with maximum value and output the index as the answer.

Implementation in C++

// C++ Program to find the maximum repeating element in O(N) time and O(1) space.
#include <bits/stdc++.h>
using namespace std;


// Function to solve the problem.
int solve(vector<int> &arr, int n, int k)
{
    // Current ans = 0;
    int ans = 0;


    // Current maximum element.
    int currMax = -1;
    for (int i = 0; i < n; i++)
    {
        // As discussed in the approach.
        arr[arr[i] % k] += k;


        // Update the ans and currMax variables if satisfied.
        if (arr[arr[i] % k] > currMax)
        {
            currMax = arr[arr[i] % k];
            ans = arr[i] % k;
        }
    }


    // Return the ans.
    return ans;
}


int main()
{
    // Input the array and K.
    int n;
    cout << "Enter the size of the array: ";
    cin >> n;
    cout << "Enter the elements of the array (space-separated): ";
    vector<int> arr;
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        arr.push_back(a);
    }
    int k;
    cout << "Enter the value of K: ";
    cin >> k;
    cout << solve(arr, n, k);
}

Implementation in Python

// Python Program to find the maximum repeating element in O(N) time and O(1) space.
# Take the input.
print("Enter the size of the array: ", end="")
n = int(input())


print("Enter the elements of the array (space-separated): ", end="")
arr = [int(i) for i in input().split()]


print("Enter the value of K: ", end="")
k = int(input())


# Current max element and the answer.
maxElem = -1
ans = 0


# Iterate through the array.
for i in range(n):
    # As discussed in the approach.
    arr[arr[i] % k] = k


    # If required, update the maxElem and ans variables.
    if arr[arr[i] % k] > maxElem:
        maxElem = arr[arr[i] % k]
        ans = arr[i] % k


# Print ans.
print(ans)

Input

Enter the size of the array: 5

Enter the elements of the array (space-separated): 2 2 1 3 4

Enter the value of K: 5

Output

2

Time Complexity

The Time Complexity of the above approach is O(N), where N is the size of the array.

It is because we are iterating the array in a single for loop and doing the O(1) operations. Also, the time complexity of finding the index holding the maximum element is O(N).

Space Complexity

The Space Complexity of the above approach is O(1), as we are not using any extra space.