You have an array of N numbers. Find all the numbers that occur more N/5 times in the array.

This can be obviously done in O(n log n) time and O(1) space, or O(n) time and O(n) space, but the catch is that it can be done in O(n) time and O(1) space.

After hours of thinking I found the solution, which is absolutely the same as described here (and it is not hard to extend it for M times).

My question is: does this problem belongs to some general class of algorithms? and what kind of similar problems are there? Like dynamic programming, greedy or recursion (these are clearly wrong classes)?

I was looking at the streaming algorithms, but it does not look this is the case.

  • $\begingroup$ I don't know the answer. However, why do you want to know the general class it falls into? In addition, "similar problems" is a broad term. Anyway, you can find a formal study of this problem in this paper: Finding Repeated Elements@1982 (including a lower bound proof). $\endgroup$ – hengxin Feb 29 '16 at 7:20
  • $\begingroup$ @hengxin this problem looks different in comparison to problems I solved previously. It was pretty hard to me and I assume this is the basic problem of this particular type. I would like to learn more about these types of problems $\endgroup$ – Salvador Dali Feb 29 '16 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.