Count Negative Numbers In A Sorted Matrix - Leetcode Solution

Problem:

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,-2,-3],[-2,-3,-3,-4]] 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:

We can find the number of negative numbers in the given matrix using binary search.

Algorithm:

1. Initialize a variable count to 0 to keep track of the number of negative numbers.
2. Loop over each row in the matrix: a. Perform binary search on the row, to find the first negative number in that row. (Here we use binary search since the matrix is sorted row-wise and column-wise.) b. Increment count by the length of the row minus the index of the first negative number in that row.
3. Return count.

Code:

The code to implement the above algorithm is shown below:

class Solution: def countNegatives(self, grid: List[List[int]]) -> int: count = 0 for row in grid: left, right = 0, len(row)-1 while left <= right: mid = (left+right)//2 if row[mid] >= 0: left = mid+1 else: right = mid-1 count += len(row)-left return count

Time complexity: O(m*logn), where m and n are the dimensions of the input matrix.

Space complexity: O(1).

1