# 【LeetCode】 1351. Count Negative Numbers in a Sorted Matrix

## Description
> 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`.

> Constraints:
> * `m == grid.length`
> * `n == grid[i].length`
> * `1 <= m, n <= 100`
> * `-100 <= grid[i][j] <= 100`

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

> 給予一個 `m x n` 並且欄與列都以非遞增順序排序的矩陣 `grid`，回傳 `grid` 中非負數的數量。

> 限制：
> * `m == grid.length`
> * `n == grid[i].length`
> * `1 <= m, n <= 100`
> * `-100 <= grid[i][j] <= 100`

> 進階題：你可以找到一個 `O(n + m)` 的解法嗎？

## Example:

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

Example 2:

Input: grid = [[3,2],[1,0]]
Output: 0

## Solution

* 先用最直覺的想法做一次：每一列都從最後面去遍歷，檢查是否為負數
* 第一種範例 code
* 能過，但時間複雜度為 `O(m * n)`
* 最差的 case 就是全部都是負數，每一列都要跑滿
---

* 由於不只列有排序，欄其實也有排序，因此每次到下一列的時候可以不用重新從尾巴檢查，直接從上一次跑到的點檢查即可
* 簡單來說，`j` 其實不需要重置
* 從矩陣的最右上開始檢查，跑負數的地方，跑到最下面一列即可
* 圖解
* 
* 
* 即便是全負數的 case 也只需要跑 `n + m`，達到 `O(n + m)`

### Code

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int count = 0;
        for(int i = 0; i < grid.size(); i++)
            for(int j = grid[i].size() - 1; j >= 0; j--)
                count += grid[i][j] < 0;
        return count;
    }
};

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int count = 0;
        int j = 0;
        int n = grid[0].size();
        for(int i = 0; i < grid.size(); i++)
        {
            while(j != n && grid[i][n - j - 1] < 0)
            {
                j++;
            }
            count += j;
        }
                
        return count;
    }
};

###### tags: `LeetCode` `C++`