Hi community. Is there anyone who can comment about the O(n) time complexity approach for the following problem? In the problem analysis part, author talks about it (There is also a O(N) solution to this problem using hash tables. It is left as an exercise to the reader.) but does not give thee details. I appreciate if you help about the matter. Thank you.

I think I have asked something bad. :) Interesting to see "not like"s.

I solved this question with just an interval set, but I think $$$O(n)$$$ with hash table would be maintaining 2 table $$$nxt$$$ and $$$prv$$$ that point to the next and prev element not used for some query $$$x$$$. When we insert a new point we then update neighboring points with path compression style similar to how union find works. This would allow $$$O(1)$$$ per query which will result in $$$O(n)$$$ overall

Thank you. I am going to try.