Skip to content

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.

 

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?

Solutions

Solution 1: Traverse from the Bottom-Left Corner

Since the matrix is sorted in non-strictly decreasing order both row-wise and column-wise, we can start traversing from the bottom-left corner of the matrix. Let the current position be \((i, j)\).

If the element at the current position is greater than or equal to \(0\), it means all preceding elements in that row are also greater than or equal to \(0\). Therefore, we move the column index \(j\) one position to the right, i.e., \(j = j + 1\).

If the element at the current position is less than \(0\), it means the current element and all elements to its right in that row are negative. Therefore, we can add \(n - j\) to the count of negative numbers (where \(n\) is the number of columns in the matrix), and then move the row index \(i\) one position upward, i.e., \(i = i - 1\).

We repeat the above process until the row index \(i\) is less than \(0\) or the column index \(j\) is greater than or equal to \(n\). Finally, the count of negative numbers is the answer.

The time complexity is \(O(m + n)\), where \(m\) and \(n\) are the number of rows and columns of the matrix, respectively. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        i, j = m - 1, 0
        ans = 0
        while i >= 0 and j < n:
            if grid[i][j] >= 0:
                j += 1
            else:
                ans += n - j
                i -= 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int countNegatives(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int i = m - 1;
        int j = 0;
        int ans = 0;
        while (i >= 0 && j < n) {
            if (grid[i][j] >= 0) {
                j++;
            } else {
                ans += n - j;
                i--;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int i = m - 1;
        int j = 0;
        int ans = 0;
        while (i >= 0 && j < n) {
            if (grid[i][j] >= 0) {
                j++;
            } else {
                ans += n - j;
                i--;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func countNegatives(grid [][]int) (ans int) {
    m := len(grid)
    n := len(grid[0])
    i := m - 1
    j := 0
    for i >= 0 && j < n {
        if grid[i][j] >= 0 {
            j++
        } else {
            ans += n - j
            i--
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function countNegatives(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    let i = m - 1;
    let j = 0;
    let ans = 0;
    while (i >= 0 && j < n) {
        if (grid[i][j] >= 0) {
            j++;
        } else {
            ans += n - j;
            i--;
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
impl Solution {
    pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut i: i32 = m as i32 - 1;
        let mut j: usize = 0;
        let mut ans: i32 = 0;
        while i >= 0 && j < n {
            if grid[i as usize][j] >= 0 {
                j += 1;
            } else {
                ans += (n - j) as i32;
                i -= 1;
            }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[][]} grid
 * @return {number}
 */
var countNegatives = function (grid) {
    const m = grid.length;
    const n = grid[0].length;
    let i = m - 1;
    let j = 0;
    let ans = 0;
    while (i >= 0 && j < n) {
        if (grid[i][j] >= 0) {
            j++;
        } else {
            ans += n - j;
            i--;
        }
    }
    return ans;
};

Comments