You have an array of
Nnumbers. Find all the numbers that occur more
N/5times 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
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
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.