1351.Count Negative Numbers in a Sorted Matrix
===

###### tags: `Easy`,`Array`,`Binary Search`,`Matrix`

[1351. Count Negative Numbers in a Sorted Matrix](https://leetcode.com/problems/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:**

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

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

### 解答

#### C++
Linear search

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        ios_base::sync_with_stdio(0), cin.tie(0);
        int m = grid.size();
        int n = grid[0].size();
        int ans = 0;
        for (int r = 0; r < m; r ++) {
            for (int c = 0; c < n; c ++) {
                if (grid[r][c] < 0) {
                    ans ++;
                }
            }
        }
        return ans;
    }
};

> [name=Jerry Wu][time=8 June, 2023]

Binary search

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        ios_base::sync_with_stdio(0), cin.tie(0);
        int m = grid.size();
        int n = grid[0].size();
        int ans = 0;
        for (const auto row : grid) {
            ans += upper_bound(row.rbegin(), row.rend(), -1) - row.rbegin();
        }
        return ans;
    }
};

> [name=Jerry Wu][time=8 June, 2023]

#### C#

public class Solution {
    public int CountNegatives(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        
        int count = 0;
        int rowCount = 0;
        for (int row = 0; row < m; row++) {
            for (int col = n - 1 - rowCount; col >= 0; col--) {
                if (grid[row][col] >= 0) break;
                rowCount++;
            }
            count += rowCount;
        } 

        return count;
    }
}

>[name=Jim][time=Jun 8, 2023]

#### Python

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        return len([elem for arr in grid for elem in arr if elem < 0])

> [name=Ron Chen][time=Tue, Jun 8, 2023]

#### Java
我寫的版本

class Solution {
    public int countNegatives(int[][] grid) {
        List<List<Integer>> list = Arrays.stream(grid)
                .map(row -> Arrays.stream(row).boxed().collect(Collectors.toList()))
                .collect(Collectors.toList());

        int res = 0;
        for (List<Integer> sublist : list) {
            for (int num : sublist) {
                if(num < 0) res++;
            }
        }

        return res;
    }
}

ChatGPT 寫的版本

class Solution {
    public int countNegatives(int[][] grid) {
        return (int) Arrays.stream(grid)
                .flatMapToInt(Arrays::stream)
                .filter(num -> num < 0)
                .count();
    }
}

> [name=Ron Chen][time=Tue, Jun 8, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)