Find the maximum repeating number in O(n) time and O(1) extra space

Question

Find the maximum repeating number (The number that occurs the most) in O(n) time and O(1) extra space .

I think i can use counting sort phase that maintains a count array , then it can be done in O(N) . Am i right ?

But how to handle extra space . Is there any other efficient algorithm ?

Answer 1

I don't think that this is possible without any further knowledge about the possible numbers in the array. For the intuition consider the following: for any constant amount of memory you are prepared to use (c = O(1)) there is a sequence such that at point n-1 there are c+1 possibilites for the correct answer and only the last number breaks the tie. In this case the algorithm with constant memory c cannot find the answer in one pass. This works similarly for several (constant amount of) passes.

Lets see what we can do instead.

• If we know that there are at most k unique numbers, we can find the answer in O(n) with O(k) extra space by keeping a count-array (or unordered map with constant lookup cost if the k numbers need not be sequential). But if we cannot bound k other than k<n this becomes O(n) extra space in the worst case.
• If we sort the array in O(n log(n)), we can then find the answer in O(n). So the total complexity is O(n log(n)) with O(1) extra space.