Suppose I have an unsorted list such as the one below:

[1, 2, 3, 1, 1, 5, 2, 1]

and I want to return the number of minimum elements (in this case, min = 1), which is 4.

A quick solution is to just find the minimum using some built in min() function, and then iterate over the list again and compare values, then count them up. O(2n) time.

But I'm wondering if it's possible to do it in strictly O(n) time - only make one pass through the list. Is there a way to do so?

CodePudding user response：

Remember that big-O notation talks about the way in which a runtime scales, not the absolute runtime. In that sense, an algorithm that makes two passes over an array that each take time O(n) also has runtime O(n) - the runtime will scale linearly as the input size increases. So your two-pass algorithm will work just fine.

A stronger requirement is that you have a one-pass algorithm, in which you get to see all the elements once. In that case, you can do this by tracking the smallest number you've seen so far and all the positions where you've seen it. Whenever you see a value,

• if that value is bigger than the smallest you've seen, ignore it;
• if that value equals the smallest you've seen, add it to the list of positions; and
• if that value is smaller than the smallest you've seen, discard your list of all the smallest elements (they weren't actually the smallest) and reset it to a list of just the current position.

This also takes time O(n), but does so in a single pass.