Count Negative Numbers in a Sorted Matrix

Brute Force Solution

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

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: O(m * n), where m is the number of rows and n is the number of columns.

Space Complexity: O(1), as it uses only a constant amount of extra space.

Optimal Solution: Binary Search

Since the matrix is sorted in non-increasing order both row-wise and column-wise, we can use binary search on each row to find the index of the first negative number. The number of negative numbers in that row is then the length of the row minus that index. This exploits the sorted property of the array.

def count_negatives_binary_search(grid):
    count = 0
    for row in grid:
        left, right = 0, len(row) - 1
        first_negative_index = len(row)  # Initialize to length of row

        while left <= right:
            mid = (left + right) // 2
            if row[mid] < 0:
                first_negative_index = mid
                right = mid - 1  # Search left for the first negative number
            else:
                left = mid + 1  # Search right

        count += len(row) - first_negative_index
    return count

Time Complexity: O(m * log n), where m is the number of rows and n is the number of columns. This is because we perform a binary search (log n) on each of the m rows.

Further Optimized Solution: O(m + n)

We can take advantage of the fact that the matrix is sorted both row-wise and column-wise to achieve O(m+n) complexity. Starting from the bottom-left element, we can move either up or right based on the value of the current element.

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

    while row >= 0 and col < n:
        if grid[row][col] < 0:
            count += n - col  # Add the remaining elements in the row
            row -= 1  # Move to the previous row
        else:
            col += 1  # Move to the next column

    return count

Time Complexity: O(m + n), as in the worst case, we traverse each row and each column once.

Space Complexity: O(1), as it uses only a constant amount of extra space.

Edge Cases:

• Empty Grid: If the grid is empty (m = 0), return 0.
• Empty Rows: If any row is empty (n = 0), the binary search approach will still work correctly as len(row) will be 0.
• All Positive/Negative Numbers: The algorithms should correctly handle cases where all numbers are positive or all numbers are negative.