How to get maximum value among N counters in constant time?

Question

We have N integer counters, initially showing 0. Operations:

int getMax() - returns the highest value shown by counters.
void increment(int i) - increments value of counter i.
void zero() - set zero value for all the counters. Alternative name was flood(), maybe this name will be helpful to you.

Present implementation of these operations and underlying data structure, knowing that we want these operations to be as fast as possible.

---

It was my interview question. There is a small chance that I stated something a little wrong, because of my lack of memory, but I tried my best. Maybe it is similar to some well-known problem? (I hope.)

As far as I remember, all of the operations could be done in O(1)... And one of the operations was "lazy" (maybe increment)... i.e. in a moment of call it was doing nothing, but later when the user asked for value with getMax() - it worked.

Answer 1

This can be done with simply an array of size N, where each element consists of 2 numbers - the current value, and a version (say a timestamp, for example). And you also need a global last reset (zero'd) version and a global max value.

To increment:

• If that element's version is less than the global, simply set it's value to 1. Otherwise increment it.
• If it's greater than the global max, set the global max to its value.
• Set its version appropriately (to the current time).

To get the maximum:

• Simply return the global max.

To reset:

• Simply set the global last reset version (to the current time) and also set the global max value to 0.

All operations: O(1).