Блог пользователя serhatgiydiren

How O(n) is possible for this Google Kickstart 2019 Round C problem Wiggle Walk?
Автор serhatgiydiren, история, 5 лет назад, По-английски

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
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +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

→ Ответить