On Dec 2, 6:45 am, Vinoth Kumar <[email protected]> wrote: > These are the steps for the O(n^2) solution > > n=length of A > for each subarray A[i,j] where j>i > min=min(A[i,j]) > max=max(A[i,j]) > if(max - min==size (A[i,j]) print A[i,j] > > min[A[i,j]]=min( A[j], min(A[i,j-1]) > similar one for max > > Note: > A[i,j] = A[i],A[i+1]....A[j] > > I was wondering how to do the same problem in O(nlogn) >
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 -- Geoff -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
