Count Negative Numbers in a Sorted Matrix

Difficulty: Easy | Acceptance: 79.60% | Paid: No Topics: Array, Binary Search, 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.

• Examples
• Constraints
• Brute Force
• Binary Search
• Optimal Traversal

Examples

Example 1:

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.

Example 2:

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

Brute Force

Intuition Since the matrix size is relatively small (up to 100x100), we can simply iterate through every element in the matrix and count how many are negative.

Steps

• Initialize a counter to 0.
• Iterate through each row of the matrix.
• Iterate through each element in the row.
• If the element is less than 0, increment the counter.
• Return the counter.

class Solution:
    def countNegatives(self, grid: list[list[int]]) -> int:
        count = 0
        for row in grid:
            for num in row:
                if num < 0:
                    count += 1
        return count

Complexity

• Time: O(m × n)
• Space: O(1)
• Notes: Simple to implement, but not the most efficient for larger matrices.

Binary Search

Intuition Each row is sorted in non-increasing order. This means all negative numbers in a row are grouped together at the end. We can use binary search to find the index of the first negative number in each row.

Steps

• Initialize a counter to 0.
• Iterate through each row of the matrix.
• Perform a binary search on the row to find the first index where the element is less than 0.
• If such an index is found, add the number of elements from that index to the end of the row to the counter.
• Return the counter.

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

Complexity

• Time: O(m log n)
• Space: O(1)
• Notes: More efficient than brute force for wide matrices.

Optimal Traversal

Intuition The matrix is sorted both row-wise and column-wise. We can start from the top-right corner. If the current element is negative, all elements below it in that column are also negative. If it is non-negative, we move to the left to find smaller numbers.

Steps

• Start at the top-right corner of the matrix (row 0, col n-1).
• Initialize a counter to 0.
• While the current position is within the matrix boundaries:
  • If the current element is negative, add the number of remaining rows in the current column to the count and move left.
  • If the current element is non-negative, move down to the next row.
• Return the counter.

class Solution:
    def countNegatives(self, grid: list[list[int]]) -> int:
        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

Complexity

• Time: O(m + n)
• Space: O(1)
• Notes: The most efficient approach, leveraging the sorted properties of both rows and columns.