1. check arr[0][0]. If this is non negative, there are 0 negative
numbers. (assuming sorting is ascending)
2. for arr[i][j], increment j until you hit a non-negative number.
this index will be limitRow
3. increment i, until you hit a non-negative number, this index will
be limitColumn,
for i<limitRow
for j<limitColumn
if(arr[i][j] <0)
negativeCount++;
limitColumn=j;
if(limitColumn == 1) break;
This is <O(n) since every element will be checked a max. of 1 time
On Jun 5, 12:08 pm, divya <[email protected]> wrote:
> Given an n X n array with rows sorted and cols sorted, find the number
> of negative elements in most efficient way
--
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.
