## DEV Community is a community of 733,030 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Gangbaolede Li

Posted on

# Leetcode 1351: Count Negative Numbers in a Sorted Matrix

Problem statement:
https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/

• Let's say we are at i-th row and j-th column. If grid[i][j] < 0, we can say that numbers below grid[i][j] are all negative and count them up. With this, we just start from top right corner to bottom left corner and count the negative numbers column by column.

Runtime: O(M+N)

Python

``````class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid)
i = 0
j = n - 1
count = 0
while i < m and j >= 0:
if grid[i][j] < 0:
count += m - i
j = j - 1
else:
i = i + 1
return count
``````

C++

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