@senthilnathan: Indeed a nice logic. Complexity is O(logn) worst case(if > all elements are negative). > > http://codepad.org/hRbYV287 >
> On Tue, Jun 8, 2010 at 8:18 AM, Minotauraus <anike...@gmail.com> wrote: > >> Actually, this might not always be the best approach. Example: >> >> -1 1 2 3 4 >> 1 2 3 4 5 >> 1 2 3 4 5 >> 1 2 3 4 5 >> 1 2 3 4 5 >> >> 2*N = 10 steps. >> >> With my algo, you'll go: >> >> Step 1: top-left: negative, count++, >> Step2: [0][1] non negative, set limitRow=0 (or 1 depending on how you >> code) >> Step3: for([i][j] < limitRow) >> check [1] [0]: non negative, set limitColumn = 0; >> since i=limitRow, j=limitCol, stop; count =1. >> >> >> >> > We can do it in O(n * log n) by individually binary-searching for zero >> on >> > each of the rows. Once we get the index of the first position where >> zero >> > appears, counting the number of negative number is straight-forward. >> >> >> What if there are no zero elements at all? >> >> -Minotauraus. >> >> >> > Here is an even better O(N) algorithm which is very elegant: >> > Consider the bottom-left element of the given 2-D array. >> > If it is negative, the whole of first-column is negative. So we can add >> > that count and ignore that column from then onwards. >> > If it is non-negative, the whole of last-row is non-negative. So we can >> > ignore that row without changing the count. >> > Therefore, by just doing one comparison we are able to "eliminate" one >> row >> > or one column. >> > We can iteratively follow this approach and it will terminate in exactly >> 2*N >> > steps. >> >> -- >> 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<algogeeks%2bunsubscr...@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.
