@senthilnathan: Indeed a nice logic. 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.
