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.

For example:

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.

Another example:

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?

## Brute Force Solution

This approach iterates through each element of the matrix and checks if it's negative. If it is, a counter is incremented. This is a straightforward but potentially inefficient method.

```python
def count_negatives_brute_force(grid):
    count = 0
    for row in grid:
        for num in row:
            if num < 0:
                count += 1
    return count

Optimal Solution: Binary Search

Since the matrix is sorted in non-increasing order both row-wise and column-wise, we can use binary search to find the index of the first negative number in each row. This allows us to count the number of negative numbers in each row more efficiently.

def count_negatives_binary_search(grid):
    count = 0
    for row in grid:
        left, right = 0, len(row) - 1
        while left <= right:
            mid = (left + right) // 2
            if row[mid] < 0:
                right = mid - 1
            else:
                left = mid + 1
        count += len(row) - left
    return count

Optimized Solution: Starting from Top-Right

We can start from the top-right element of the matrix. If the element is positive, we move one step to the left. If the element is negative, it means all elements below it in the current column are also negative. So, we increment the count by the number of rows below the current element (including the current row) and move one step up.

def count_negatives_optimized(grid):
    m, n = len(grid), len(grid[0])
    row, col = 0, n - 1
    count = 0

    while row < m and col >= 0:
        if grid[row][col] < 0:
            count += m - row
            col -= 1
        else:
            row += 1

    return count

Run-time Analysis

• Brute Force: O(m * n), where m is the number of rows and n is the number of columns. This is because we iterate through each element of the matrix.
• Binary Search: O(m * log(n)), where m is the number of rows and n is the number of columns. We perform binary search on each row, so the time complexity is proportional to the number of rows times the logarithm of the number of columns.
• Optimized Solution: O(m + n), where m is the number of rows and n is the number of columns. In the worst case, we traverse through all the rows and columns once.

Space Usage Analysis

• Brute Force: O(1), as we only use a constant amount of extra space for the counter.
• Binary Search: O(1), as we only use a constant amount of extra space for the left, right, and mid variables.
• Optimized Solution: O(1), as we only use a constant amount of extra space for the row, col, and count variables.

Edge Cases

• Empty Matrix: If the input matrix is empty, the code should return 0.
• Matrix with No Negative Numbers: If the matrix contains no negative numbers, the code should return 0.
• Matrix with All Negative Numbers: If the matrix contains all negative numbers, the code should return the total number of elements in the matrix (m * n).
• Invalid Input: The matrix must be sorted in non-increasing order both row-wise and column-wise. If this condition is not met, the binary search and optimized solutions may not work correctly.