serhatgiydiren's blog

How O(n) is possible for this Google Kickstart 2019 Round C problem Wiggle Walk?
By serhatgiydiren, history, 5 years ago, In English

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

  • Vote: I like it
  • +16
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply