Brute Force Solution

The most straightforward approach is to iterate through each element of the grid and check if it's negative. If it is, increment a counter.

Code (Python)

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

Time Complexity

The brute-force solution iterates through each element of the m x n grid once. Therefore, the time complexity is O(m * n).

Space Complexity

The space complexity is O(1) because it only uses a constant amount of extra space for the counter.

Optimal Solution (O(n + m))

Since the grid is sorted in non-increasing order both row-wise and column-wise, we can use this property to optimize our search. We can start from the bottom-left element and move either up (if the current element is non-negative) or right (if the current element is negative).

Algorithm

1. Initialize row to m - 1 and col to 0.
2. Initialize count to 0.
3. While row >= 0 and col < n:
   • If grid[row][col] < 0:
     • Increment count by n - col (all elements to the right in the current row are negative).
     • Decrement row to move up to the next row.
   • Else:
     • Increment col to move right to the next column.
4. Return count.

Code (Python)

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

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

    return count

Time Complexity

The optimal solution traverses the grid in a way that either row decreases or col increases in each step. In the worst case, it can traverse all rows and columns, resulting in a time complexity of O(m + n).

Space Complexity

The space complexity is O(1) because we only use a constant amount of extra space for variables.

Edge Cases

• Empty Grid: If the grid is empty (m = 0 or n = 0), the function should return 0.
• All Positive Numbers: If all numbers in the grid are positive or zero, the function should return 0.
• All Negative Numbers: If all numbers in the grid are negative, the function should return m * n.

Both the brute force and optimal solutions can handle these edge cases correctly.