Count Negative Numbers in a Sorted Matrix

Description

Given a m * 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

Example 3:

Input: grid = [[1,-1],[-1,-1]]
Output: 3

Example 4:

Input: grid = [[-1]]
Output: 1

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100

Solution(javascript)

/**
 * @param {number[][]} grid
 * @return {number}
 */
const countNegatives = function (grid) {
  const search = (row) => {
    let left = 0
    let right = grid[row].length - 1
    let result = -1
    while (left <= right) {
      const middle = Math.floor((left + right) / 2)
      if (grid[row][middle] <= -1) {
        result = middle
        right = middle - 1
      } else {
        left = middle + 1
      }
    }
    return result
  }
  let count = 0
  for (let row = 0; row < grid.length; row++) {
    const index = search(row)
    if (index > -1) {
      count += grid[row].length - index
    }
  }
  return count
}