Max & Min in stream of integers

Question

Given a stream of integers (I can only go through them once), what is the best solution to find maximum and minimum? I suppose that in case I have enough time to proccess each number the easiest solution is to simply keep min and max values in a separate variables, but what is the best approach if I'm unable to proccess every single one of them? Is there some better solution than simply keep max and min variables and skip for example every second number?

Answer 1

If you want the true maximum and minimum, just track them with variables.

Depending on your input data, a probabilistic min/max may be "accurate enough". So if you only look at every number with 50% chance, then you probably have only a 50% of having the exact min or max. But maybe already a 75% chance of having at least the second largest/smallest etc. However, computing the random number to do an unbiased sampling is already more expensive than looking at all numbers for min/max. Skipping every second is dangerous: there might be an even/odd pattern in the data that screws you badly.