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: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] Output: 8

Example: grid = [[3,2],[1,0]] Output: 0

Constraints:

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

Could you find an O(n + m) solution?

## Naive Solution

The brute force solution is to iterate through each element in the matrix and check if it's negative. If it is, increment a counter. This approach has a time complexity of O(m*n), where m is the number of rows and n is the number of columns.

```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

Since the grid 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. Once we find this index, we know that all elements to the right of this index are also negative. We can then add the number of negative elements in that row to a running total. This approach has a time complexity of O(m * log(n)). We can also optimize this to O(m+n) time complexity by starting from top right.

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


def count_negatives_optimal(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

Big(O) Run-time Analysis

• Brute Force: O(m*n), where m is the number of rows and n is the number of columns, 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, because we perform a binary search on each row.
• Optimal (O(m+n)): O(m + n), where m is the number of rows and n is the number of columns. In the worst case, we traverse one row and one column completely.

Big(O) Space Usage Analysis

• Brute Force: O(1) because we only use a constant amount of extra space to store the counter.
• Binary Search: O(1) because we only use a constant amount of extra space to store variables like left, right, and mid.
• Optimal (O(m+n)): O(1) because we only use a constant amount of extra space to store variables like row, col, and count.

Edge Cases

1. Empty Grid: If the input grid is empty (m=0), the function should return 0. The provided code handles this case correctly as the loops won't execute.
2. Grid with No Negative Numbers: If the grid contains no negative numbers, the function should return 0. The algorithm accounts for this as 'left' in binary search may end up at the end of the row, resulting in len(row) - left == 0.
3. Grid with All Negative Numbers: If the grid contains only negative numbers, the function should return m*n. This is handled correctly because each row will add len(row) to the count.
4. Large Grid: The code should be efficient enough to handle grids with sizes up to the constraint limits (m, n <= 100). The optimal (m+n) solution is preferred.
5. Grid with one row or one column: Code should correctly handle the boundary case where a grid has only one row or one column.