# LintCode: Count Negative Number

Count Negative Number Similar Problems:

Give a horizontally sorted and vertically sorted n * m matrix, find the number of negative number.

Notice

• The size of given matrix is n x m, n <= 500, m <= 500.
• In order to restrain the time complexity of the program, your program will run 10 ^ 5 times.

Example

```Given mat =

[
[-5,-3,-1,0,1],
[-2,-1,0,0,1],
[0,11,12,12,14]
],
return 5.
```
```Explanation:
There are only 5 negative number.
Given mat =

[
[-50,-30,-10,-5],
[-30,-20,-5,-1],
[-10,-5,-1,0]
]
return 11.

Explanation:
There are only 11 negative number.
```

Github: code.dennyzhang.com

Credits To: LintCode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/count-negative-number
class Solution:
"""
@param nums: the sorted matrix
@return: the number of Negative Number
"""
def countNumber(self, nums):
## Basic Ideas:
## Complexity: Time O(n*log(m)), Space O(1)
row_count = len(nums)
if row_count == 0: return 0
col_count = len(nums)

res = 0

left = max(self.findFirstNegative(nums[-1], 0, col_count-1), 0)
i, j = 0, col_count-1
while i>=0 and i<=row_count-1 and \
j>=0 and j<=col_count-1:
if nums[i][j] >= 0:
j = self.findFirstNegative(nums[i], left, j)
res += j+1
i += 1
return res

def findFirstNegative(self, myList, left, right):
l, r = left, right
while l<r:
mid = l + int((r-l)/2)
# find first non-negative
if myList[mid] >= 0:
r = mid
else:
l = mid + 1
return l if myList[l]<0 else l-1
```

Share It, If You Like It.