###### tags: `Leetcode` `easy` `array` `python` `c++`

# 1351. Count Negative Numbers in a Sorted Matrix

## [題目連結:] https://leetcode.com/problems/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```.

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

**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

## 解題想法:
* 此題為求出matrix中所有小於0的元素各數
* 此matrix每列、行皆為由大到小排好
* time: O(m+n)

* 此題說歸類在binary search@@? 但是感覺不相關

* 作法:
* 從**左下角**開始遍歷判斷
* curRow=m-1
* curCol=0
* 對於每個位置，判斷當前是否<0
* 若<0，則該行(n-curCol)數量皆可加入到res
* 並往上一列移動
* curRow-=1
* 若>0，則往該行後面移動
* curCol+=1

## Python:

class Solution(object):
    def countNegatives(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        #從左下開始遍歷判斷
        #對於每列由左至右判斷是否小於0
        m=len(grid)
        n=len(grid[0])
        res=0
        curRow=m-1
        curCol=0
        while curRow>=0 and curCol<n:
            if grid[curRow][curCol]<0:
                res+= n-curCol
                curRow-=1
            else:
                curCol+=1
        return res

## C++:

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int m=grid.size(), n=grid[0].size();
        int curRow=m-1, curCol=0;
        int res=0;
        while (curRow>=0 && curCol<n){
            if (grid[curRow][curCol]<0){
                res+= n-curCol;
                curRow-=1;
            }
            else
                curCol+=1;
        }
        return res;
    }
};