I might be wrong here but, why can't you just sort the block A[i..j] it will take O((j-i)log(j-i)) (there are many O(n logn) sorting algorthms) steps and then just look if they are in sequence trivially another j-i steps.
On Dec 3, 1:33 am, Vinoth Kumar <vinoth.ratna.ku...@gmail.com> wrote: > I kinda need the worst case also to be in nlogn. > Any ideas guys ? > > -- Vinod > > On Dec 2, 11:02 pm, Geoffrey Summerhayes <sumr...@gmail.com> wrote: > > > > > On Dec 2, 10:42 am, Geoffrey Summerhayes <sumr...@gmail.com> wrote: > > > > It's a binary tree, [ 7 3 4 1 2 6 5 8] has children > > > [ 7 3 4 1 2 6 5] and [ 3 4 1 2 6 5 8], all the way > > > down to [ 7 3] [3 4] [4 1] ... > > > > If you start at the bottom keeping track of min and max > > > for each node, if max-min == node length - 1 the node > > > if conseq. then it's just a matter of combining node > > > together and working up the tree > > > Darn! > > > Total steps= n*n/2 - n/2 > > > Anybody have a math trick? > > > -- > > Geoff -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
