3

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 ?

Garrick
  • 677
  • 4
  • 15
  • 34
  • Does "maximum repeating number" mean the number that occurs the most, or the biggest that is repeated? – Scott Hunter Aug 31 '16 at 14:01
  • The number that occurs the most – Garrick Aug 31 '16 at 14:02
  • I don't think that this is possible. The best I can think of is a sort (`O(n*log(n))`) + one sweep over the sorted array (`O(n)`). – example Aug 31 '16 at 14:14
  • Are they integers? Is there any limit on the largest or smallest numbers that may occur? – Nir Friedman Aug 31 '16 at 14:15
  • yes , all are integers and there is no bound or range. – Garrick Aug 31 '16 at 14:17
  • I can use count array , but it takes O(N) extra space . I want O(1) . – Garrick Aug 31 '16 at 14:18
  • Cannot be done. https://www.quora.com/Given-an-array-of-integers-of-size-N-how-can-we-find-the-most-frequently-occurring-element-in-linear-time . You need O(n) time and O(k) space in most favorable interpretation, with k being number of distinct numbers. As expectation of k is to grow with n, it is not really O(1) in space. – Artur Biesiadowski Aug 31 '16 at 14:29
  • 1
    Also http://www.geeksforgeeks.org/find-the-maximum-repeating-number-in-ok-time/. Another problem with this approach is that the original array is modified and requires another `O(n)` operation to get the original values back. – beaker Aug 31 '16 at 14:37
  • if we don't want to modify the array , then it cannot be done . But what if we are allowed to do that ? – Garrick Aug 31 '16 at 15:37

1 Answers1

2

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.
example
  • 3,349
  • 1
  • 20
  • 29
  • what about maintaining count array in O(n) and O(k) extra space . – Garrick Aug 31 '16 at 15:34
  • @stackuser you are right. I was thinking of a map (which has `O(log(k))` complexity for lookup) but a unordered map or array (for sequential numbers like `0` through `k`) have constant lookup complexity. – example Sep 07 '16 at 12:10