Leetcode problem 117 - Count Negative Numbers in a Sorted Matrix

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

/**
 * @param {number[][]} grid
 * @return {number}
 */
var countNegatives = function (grid) {
  // Initialize the count variable to store the total count of negative numbers
  let count = 0;

  // Iterate over each row in the grid
  for (let row of grid) {
    // Initialize the left pointer to the start of the row
    let left = 0;
    // Initialize the right pointer to the end of the row
    let right = row.length - 1;

    // Perform binary search within the row
    while (left <= right) {
      // Calculate the mid index of the current row
      let mid = Math.floor((left + right) / 2);

      // If the value at the mid index is negative
      if (row[mid] < 0) {
        // Move the right pointer to mid - 1 to search in the left half
        right = mid - 1;
      } else {
        // Move the left pointer to mid + 1 to search in the right half
        left = mid + 1;
      }
    }

    // Add the count of negative numbers in the current row to the total count
    count += row.length - left;
  }

  // Return the total count of negative numbers in the grid
  return count;
};

The time complexity of this code is O(n _ log(m)), where n is the number of rows in the grid and m is the average length of each row. This is because for each row, we perform a binary search to find the first positive number, which takes O(log(m)) time. Since we perform this operation for each row, the overall time complexity is O(n _ log(m)).

The space complexity of this code is O(1) because we only use a constant amount of extra space for the variables count, left, right, and mid. The space used does not depend on the size of the input grid.