# Count Negative Numbers in a Sorted Matrix

Given a `m x n` matrix `grid` which is sorted in non-increasing order both row-wise and column-wise, return *the number of **negative** numbers in* `grid`.

**Example 1:**

<pre><code><strong>Input: grid = [
</strong><strong>[4,3,2,-1],
</strong><strong>[3,2,1,-1],
</strong><strong>[1,1,-1,-2],
</strong><strong>[-1,-1,-2,-3]
</strong><strong>]
</strong><strong>Output: 8
</strong><strong>Explanation: There are 8 negatives number in the matrix.
</strong></code></pre>

**Follow up:** Could you find an `O(n + m)` solution?

***My Solutions:***

根据题意，每一行的数字递减，每一列的数字也是递减的。所以可以从grid的左下角开始，往右或者往上移动。也可以从右上角开始，往左或者往下移动

```
class Solution {
    public int countNegatives(int[][] grid) {
        int m = grid.length, n = grid[0].length, count = 0;

        // 从grid的左下角开始
        int r = m - 1, c = 0;
        while (r >= 0 && c < n) { 
            if (grid[r][c] < 0) {  // 现在格子的这一行肯定都是negative number
                r--; // 把行数往上移动一位
                count += n - c; // 列数-c所在的位置
            } else { // 向右移动
                c++;
            }
        }

        // // 或者从grid的右上角开始
        // int r = 0, c = n - 1;
        // while (r < m && c >= 0) { 
        //     if (grid[r][c] < 0) {  // 现在格子的下面一列肯定都是negative number
        //         c--; // 把列数往左移动一位
        //         count += m - r;
        //     } else {
        //         r++;
        //     }
        // }

        return count;
    }
}
```

这个题目也可以变形成每一行的数字递增，每一列递增。

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

**Example 1:**

```
Input:[    
[-5,-3,-1,0,1],    
[-2,-1,0,0,1],    
[0,11,12,12,14]
]
Output: 5
Explanation: There are only 5 negative number.
```

**Example 2:**

```
Input:[    
[-50,-30,-10,-5],    
[-30,-20,-5,-1],    
[-10,-5,-1,0]
]
Output: 11
Explanation: There are only 11 negative number.
```

***My Solutions:***

类似的从右上角开始，往左和往下移动

```
public int countNumber(int[][] nums) {
    // Write your code here
    int count = 0, m = nums.length, n = nums[0].length;
    int r = 0, c = n - 1;
    while (r < m && c >= 0) {
        if (nums[r][c] < 0) { // 现在格子的一行都是负数
            count += c + 1;
            r++; // 移动到下一行
        } else {
            c--; // 现在的格子是正数，移动到左边的一列
        }
    }
    return count;
}
```