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.
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.
