Algorithm to Compute High Water Mark

I saw this algorithm question which is as below.
There is a server that receives request Ids that are positive integers.
The High Water Mark (HWM) for the server at any instant of time is defined as the highest integer request Id n such that every positive integer request Id less than n has already been received.

For example, if the server gets 5 request Ids as below,

  1, 6, 2, 3, 9

Then at the end of the 5th request, the getHWM() method should return 3 as 1, 2, 3 are already received but 4 is not yet received.

Similarly, for the above test case, the HWM at the end of the 3rd request, the HWM would have been 2.

My approach to this problem had been as below.

Maintain a variable hw that keeps up with the live HWM at any instant of time. Further, maintain a HashMap that stores all the requests which have been received.

Whenever a new request x is received, add hw to the HashMap. Start iterating over every positive integer in increasing order from hw and check if it is in the HashMap.

If it is in the HashMap, add increase hw by 1. Else break the loop.

A disadvantage of this approach is that it might iterate over a large list of integers.

An example can be the test case below.

  1, 2, 3, ..., 4445, 4447, ..., 8888, 4446.

(it would need to iterate from 4446 to 8888 to compute hw
after the last request.)

Another approach would be to group the requestIds received in a sorted list.

  (1-3) -> (7, 13) -> (16, 183),

search if the new requestId belongs to a particular group. Else add/merge merge nodes of the list.

Can someone suggest a more efficient approach to this problem?

You can use a disjoint sets data structure to quickly solve your problem (exercise). This can be further improved by exploiting the particular nature of your problem.

We maintain a list of intervals $[a_1,b_1],[a_2,b_2],\ldots$ which succinctly represent the integers seen so far. In addition, we store $a_i,b_i$ in a hash table.

Given a new integer $c$, we can update the data structure by looking up $c-1$ and $c+1$ in the hash table (details left to you).

To find the high water mark, simply look up $1$, and output the endpoint of the interval (if any).

Altogether, we have managed to implement all operations in $O(1)$.

StackExchange Computer Science Q#140884, answer score: 3