[algogeeks] Re: Can you guys help me how to approach this problem !!!
I kinda need the worst case also to be in nlogn. Any ideas guys ? -- Vinod On Dec 2, 11:02 pm, Geoffrey Summerhayes wrote: > On Dec 2, 10:42 am, Geoffrey Summerhayes 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.
Re: [algogeeks] Re: Can you guys help me how to approach this problem !!!
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) -- Vinod On Wed, Dec 2, 2009 at 11:48 AM, ranjmis wrote: > Vinod. Can you please mention steps for the O(n^2) solution that you > have thought of. > > On Dec 2, 9:50 am, Vinoth Kumar wrote: > > No need for the code guys. > > Can u give me a algo or pseudo code for this problem. > > I can think of a soln of O(n^2) but i need a algo for O(nlogn) > > > > > > > > On Wed, Dec 2, 2009 at 2:06 AM, NickLarsen wrote: > > > That doesn't quite get it, try the input [ 7 3 4 2 1 6 5 8] and your > > > idea would miss [3 4 2] > > > > > On Dec 1, 10:10 am, sharad kumar wrote: > > > > find out the subseq which are consecttive > > > > concatenate them at each level to get the entire set. > > > > > > On Tue, Dec 1, 2009 at 12:03 PM, Vinoth Kumar > > > > wrote: > > > > > > > Given an array A which holds a permutation of 1,2,...,n. A > sub-block A > > > > > [i..j] of an array A > > > > > is called a valid block if all the numbers appearing in A[i..j] are > > > > > consecutive numbers (may not be in order. > > > > > > > Given an array A= [ 7 3 4 1 2 6 5 8] > > > > > the valid blocks are [3 4], [1,2], [6,5], [3 4 1 2], [3 4 1 2 6 5], > [7 > > > > > 3 4 1 2 6 5], [7 3 4 1 2 6 5 8] > > > > > > > Give an O( n log n) algorithm to count the number of valid blocks. > > > > > > > -- Vinod > > > > > > > -- > > > > > > > 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. > > > > > -- > > > > > 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. > > > > -- > > Cheers, > > Vinod > > -- > > 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. > > > -- 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.
Re: [algogeeks] Re: Can you guys help me how to approach this problem !!!
No need for the code guys. Can u give me a algo or pseudo code for this problem. I can think of a soln of O(n^2) but i need a algo for O(nlogn) On Wed, Dec 2, 2009 at 2:06 AM, NickLarsen wrote: > That doesn't quite get it, try the input [ 7 3 4 2 1 6 5 8] and your > idea would miss [3 4 2] > > On Dec 1, 10:10 am, sharad kumar wrote: > > find out the subseq which are consecttive > > concatenate them at each level to get the entire set. > > > > On Tue, Dec 1, 2009 at 12:03 PM, Vinoth Kumar > > wrote: > > > > > > > > > Given an array A which holds a permutation of 1,2,...,n. A sub-block A > > > [i..j] of an array A > > > is called a valid block if all the numbers appearing in A[i..j] are > > > consecutive numbers (may not be in order. > > > > > Given an array A= [ 7 3 4 1 2 6 5 8] > > > the valid blocks are [3 4], [1,2], [6,5], [3 4 1 2], [3 4 1 2 6 5], [7 > > > 3 4 1 2 6 5], [7 3 4 1 2 6 5 8] > > > > > Give an O( n log n) algorithm to count the number of valid blocks. > > > > > -- Vinod > > > > > -- > > > > > 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. > > -- > > 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. > > > -- Cheers, Vinod -- 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.
[algogeeks] Can you guys help me how to approach this problem !!!
Given an array A which holds a permutation of 1,2,...,n. A sub-block A [i..j] of an array A is called a valid block if all the numbers appearing in A[i..j] are consecutive numbers (may not be in order. Given an array A= [ 7 3 4 1 2 6 5 8] the valid blocks are [3 4], [1,2], [6,5], [3 4 1 2], [3 4 1 2 6 5], [7 3 4 1 2 6 5], [7 3 4 1 2 6 5 8] Give an O( n log n) algorithm to count the number of valid blocks. -- Vinod -- 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.
