Count negative numbers in a sorted matrix

Array Binary Search Matrix

79.5% acceptance

Feb 25, 2026

5477

146

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.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let mut count = 0;
    let mut col = n as i32 - 1;
    for row in 0..m {
      while col >= 0 && grid[row][col as usize] < 0 {
        col -= 1;
      }
      count += (n as i32 - 1 - col) as i32;
    }
    count
  }
}