How O(n) is possible for this Google Kickstart 2019 Round C problem Wiggle Walk?

Revision en3, by serhatgiydiren, 2020-03-26 20:14:41

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

Tags #googlekickstart, 2019 round c, wiggle walk

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English serhatgiydiren 2020-03-26 20:14:41 5 Tiny change: 'e who can make comment a' -> 'e who can comment a'
en2 English serhatgiydiren 2020-03-26 14:30:38 4 Tiny change: 're anyone can make ' -> 're anyone who can make '
en1 English serhatgiydiren 2020-03-26 14:30:05 553 Initial revision (published)