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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.