You guy check this solution. It is expected to be run in O(n lg n) for random permutation in average time. For worst case, I think we can improve it for that.
Let's do an example firstly. 7 3 4 1 2 6 5 8 For *1*, it self is a block. Let's count the blocks containing *1* firstly. If a block with size more than 1 contains *1*, it will contains *2*. Now check *2*, it is not beside *1*, so no block with size=2 contains *1*. Let's check *3*', the minimum position for (1,2,3) is 1 (with 0 based index), and maximum position for (1,2,3) is 4. Because 4-1+1 = 4>3, no block with sizeo=3 contains *1*. Let's check *4*, the minimum position for (1,2,3,4) is 1, and maximum position is 4. The window size is 4-1+1 = 4. We find a block with size=4 and it contains *1*. By continuing this process, we will get the number of blocks containing number *1* and more important is the time we need is linear time: O(n). Now, we have checked all blocks including number *1*. So from now on, we do not need number *1* anymore. It means we can split the list into two [7 3 4] and [2 6 5 8] and repeat the above process again & again. If the permutation is really random, the above process is very similar as the QuickSort process and then we know the whole process cost O(n lg n) time. However, for worst case like [1 2 3 4 ... n], it performs very bad. The time complexity is linear with the number of blocks and so it is not good in worst case. I.e. the above algorithm need O(n^2) time for such worst case. Hope other guys can solve the worst case in O(n lg n) time. Thanks On Tue, Dec 1, 2009 at 2:33 PM, Vinoth Kumar <[email protected]> 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 [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. > > > -- 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.
