# 1351. Count Negative Numbers in a Sorted Matrix
[1351. Count Negative Numbers in a Sorted Matrix](https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/) (<font color="#00AF9B"> Easy</font> 通過率: 77.7%)

## 限制條件
<ul>
<li>m == grid.length</li>
<li>n == grid[i].length</li>
<li>1 <= m, n <= 100</li>
<li>-100 <= grid[i][j] <= 100</li>
</ul>

### 解法 1
第一種寫法，很簡單的暴力解。
會過，但這種寫法很丑。

- 時間複雜度: O(n*m)
- 空間複雜度: O(1)

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

### 解法 2
第二種類就是類似游標的感覺。
先從第最後一列的第一個元素開始找
1. 如果找到負數，那就不用看後面直接＋當列的負數個數，然後往上一列繼續找。
2. 如果找到的是正數，那繼續往右找到負數為止。

- 時間複雜度: O(m+n)
- 空間複雜度: O(1)

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int result = 0;

        int m = grid.size();
        int n = grid[0].size();

        int xIndex = m - 1;
        int yIndex = 0;

        while (xIndex >= 0 && xIndex < m && yIndex >= 0 && yIndex < n) {
            if (grid[xIndex][yIndex] < 0) {
                result += (n - yIndex);
                xIndex -= 1;
            } else {
                yIndex += 1;
            }
        }

        return result;
    }
};