Follow the minimum value in a collection of values which can only increase

Question

I have a large collection of integers, the value of which can only grow (I'm counting stuff).

For efficiency reasons, I separately keep a max value, which is updated whenever needed:

// when increasing the i'th count
coll[i] += 1;
// check whether also to update the max:
if(coll[i] > max){
  max = coll[i];
}

What's an efficient algorithm to also "follow" the minimum value of the collection?

By efficient I mean, iterate over the whole collection the least often possible and keep memory footprint small. (the latter is really less important than the former)

I'm using Java: so if said algorithm is already in the JRE, I'd welcome a reference.

Answer 1

Keep a hash table of counts for each value, then update it and also the min if there are no more values equal to min in your hash table.

// when increasing the i'th count
coll[i] += 1;
--hashTable[coll[i] - 1];
++hashTable[coll[i]];
// check whether also to update the max:
if(coll[i] > max){
  max = coll[i];
}
// check whether to update the min:
if(min == coll[i] - 1 && hashTable[coll[i] - 1] == 0){
  min = coll[i];
}

The hash table can be a simple array if you can afford the memory (if your values are small enough) or an actual Hashtable.

This would only require an initial iteration over your collection to build the hash table. Then no more iterations will be performed.