On Jun 7, 8:49 am, Senthilnathan Maadasamy
<[email protected]> wrote:
> 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.
I must say that your algorithm is very clever since I never thought of
it. :-)
I thought of a different approach that can be combined with yours
to, oddly enough, get an even better solution.
Consider the bottom-left element of the given 2-D array.
If it is negative:
Search the bottom row for the first non-negative value.
If this element is the kth then it can be found in
O(log k) time using a variation of binary search.
Now the first k - 1 columns are all negative so we count
those.
If it is non-negative:
Search the first column bottom to top for the first negative
value.
If this element is the jth from the bottom then it can be found
in O(log j) time.
Now the last j-1 rows are all non-negative so they need not be
counted.
Now follow this approach and it will terminate in O(N) steps.
This is no better than your approach in the worst case (in fact
slightly worse)
but can be much better for cases where either most of the elements are
positive
or most of the elements are negative. For example if all elements are
negative
the algorithm runs in O(log N) time (actually 2 log N + O(1)).
Open problem:
I am guessing that my algorithm is optimal in some (reasonable) sense
in which your algorithm is not.
Define optimal (reasonably) than then prove that my algorithm is
indeed
optimal or show that some other algorithm is better by your
definition.
Regards,
Ralph Boland
--
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.
