### serhatgiydiren's blog

By serhatgiydiren, history, 2 months ago, ,

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.

Wiggle Walk

• +16

 » 2 months ago, # | ← Rev. 2 →   0 I think I have asked something bad. :) Interesting to see "not like"s.
 » 2 months ago, # |   +1 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
•  » » 2 months ago, # ^ |   0 Thank you. I am going to try.