Question

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: Start Traversing from the Bottom Left or Top Right

According to the characteristic that both rows and columns are arranged in non-increasing order, we can start traversing from the bottom left corner towards the top right direction.

When encountering a negative number, it indicates that all elements to the right of the current position in this row are negative. We add the number of remaining elements in this row to the answer, that is, $n - j$, and move up a row, that is, $i \leftarrow i - 1$. Otherwise, move to the right column, that is, $j \leftarrow j + 1$.

After the traversal is over, return 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)$.

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:
        ans += n - j
        i -= 1
      else:
        j += 1
    return ans

class Solution {
  public int countNegatives(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int ans = 0;
    for (int i = m - 1, j = 0; i >= 0 && j < n;) {
      if (grid[i][j] < 0) {
        ans += n - j;
        --i;
      } else {
        ++j;
      }
    }
    return ans;
  }
}

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

func countNegatives(grid [][]int) int {
  m, n := len(grid), len(grid[0])
  ans := 0
  for i, j := m-1, 0; i >= 0 && j < n; {
    if grid[i][j] < 0 {
      ans += n - j
      i--
    } else {
      j++
    }
  }
  return ans
}

function countNegatives(grid: number[][]): number {
  const m = grid.length,
    n = grid[0].length;
  let ans = 0;
  for (let i = m - 1, j = 0; i >= 0 && j < n; ) {
    if (grid[i][j] < 0) {
      ans += n - j;
      --i;
    } else {
      ++j;
    }
  }
  return ans;
}

impl Solution {
  pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
    let n = grid[0].len();
    grid.into_iter()
      .map(|nums| {
        let mut left = 0;
        let mut right = n;
        while left < right {
          let mid = left + (right - left) / 2;
          if nums[mid] >= 0 {
            left = mid + 1;
          } else {
            right = mid;
          }
        }
        (n - left) as i32
      })
      .sum()
  }
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var countNegatives = function (grid) {
  const m = grid.length,
    n = grid[0].length;
  let ans = 0;
  for (let i = m - 1, j = 0; i >= 0 && j < n; ) {
    if (grid[i][j] < 0) {
      ans += n - j;
      --i;
    } else {
      ++j;
    }
  }
  return ans;
};

Solution 2: Binary Search

Traverse each row, use binary search to find the first position less than $0$ in each row. All elements to the right of this position are negative, and add the number of negative numbers to the answer.

After the traversal is over, return the answer.

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

class Solution:
  def countNegatives(self, grid: List[List[int]]) -> int:
    return sum(bisect_left(row[::-1], 0) for row in grid)

class Solution {
  public int countNegatives(int[][] grid) {
    int ans = 0;
    int n = grid[0].length;
    for (int[] row : grid) {
      int left = 0, right = n;
      while (left < right) {
        int mid = (left + right) >> 1;
        if (row[mid] < 0) {
          right = mid;
        } else {
          left = mid + 1;
        }
      }
      ans += n - left;
    }
    return ans;
  }
}

class Solution {
public:
  int countNegatives(vector<vector<int>>& grid) {
    int ans = 0;
    for (auto& row : grid) {
      ans += lower_bound(row.rbegin(), row.rend(), 0) - row.rbegin();
    }
    return ans;
  }
};

func countNegatives(grid [][]int) int {
  ans, n := 0, len(grid[0])
  for _, row := range grid {
    left, right := 0, n
    for left < right {
      mid := (left + right) >> 1
      if row[mid] < 0 {
        right = mid
      } else {
        left = mid + 1
      }
    }
    ans += n - left
  }
  return ans
}

function countNegatives(grid: number[][]): number {
  const n = grid[0].length;
  let ans = 0;
  for (let row of grid) {
    let left = 0,
      right = n;
    while (left < right) {
      const mid = (left + right) >> 1;
      if (row[mid] < 0) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    ans += n - left;
  }
  return ans;
}

impl Solution {
  pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let mut i = m;
    let mut j = 0;
    let mut res = 0;
    while i > 0 && j < n {
      if grid[i - 1][j] >= 0 {
        j += 1;
      } else {
        res += n - j;
        i -= 1;
      }
    }
    res as i32
  }
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var countNegatives = function (grid) {
  const n = grid[0].length;
  let ans = 0;
  for (let row of grid) {
    let left = 0,
      right = n;
    while (left < right) {
      const mid = (left + right) >> 1;
      if (row[mid] < 0) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    ans += n - left;
  }
  return ans;
};