I have N elements and need to find the maximum of these elements. At each time tick, exactly one of the N elements is updated and I need to determine the new max element (more specifically, the index of the max element). How can I do this by accessing as little "state" as possible?
The naive approach is to store all N elements and in each tick read the N elements and determine the max element. Here the amount of "state" accessed corresponds to N elements.
Is it possible to determine the max element by maintaining lesser state -- specifically state that grows sub-linearly as N increases? Essentially I do not want to make a pass on the entire set of N elements. Assume N is a fixed number.
It seems like this problem has the flavor of data streaming algorithms like the count(-min) sketch. We have N buckets -- items being streamed in update the count of one of these N buckets -- and wish to perform some query on these N buckets with sub-linear space usage.
I understand how sketches can be used to query the value of the Nth bucket, but do not understand if it can be extended to obtain an estimate for the max value (and specifically, the index of the max element). The heavy hitters problem outputs items above a certain frequency, but I am interested only in the item with the maximum frequency.
Am I over-thinking this problem? Is there a far simpler solution?