Problem

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

Example 1:

$$ \begin{bmatrix}

4 & 3 & 2 & -1 \

3 & 2 & 1 & -1 \

1 & 1 & -1 & -2 \

-1 & -1 & -2 & -3

\end{bmatrix} $$

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

Solution

Method 1 - Naive

The naive approach involves iterating through each element of the matrix grid and counting all negative elements one by one. This straightforward approach checks each element individually.

Code

Java
class Solution {
    public int countNegatives(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] < 0) {
                    count++;
                }
            }
        }
        
        return count;
    }
}
Python
class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        count: int = 0
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] < 0:
                    count += 1
        
        return count

Complexity

  • ⏰ Time complexity: O(m * n)
  • 🧺 Space complexity: O(1)

Method 2 - Optimal Solution

Given that the matrix grid is sorted in non-increasing order both row-wise and column-wise, we can use this property to optimize the search for negative numbers.

$$ \begin{bmatrix} 4 & 3 & 2 & -1 \ 3 & 2 & 1 & -1 \ 1 & 1 & -1 & -2 \ -1 & -1 & -2 & -3 \end{bmatrix} $$

Start from the bottom-left corner of the grid (in above matrix it is -3):

  1. If the current element is negative, all elements above it in the same column are also negative.
  2. If the current element is non-negative, move right to the next element in the same row.
  3. Continue until all possible negatives are counted.

Code

Java
class Solution {
    public int countNegatives(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int count = 0;
        
        int row = m - 1, col = 0;
        while (row >= 0 && col < n) {
            if (grid[row][col] < 0) {
                count += (n - col);
                row--;
            } else {
                col++;
            }
        }
        
        return count;
    }
}
Python
class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        count: int = 0
        
        row, col = m - 1, 0
        while row >= 0 and col < n:
            if grid[row][col] < 0:
                count += (n - col)
                row -= 1
            else:
                col += 1
        
        return count

Complexity

  • ⏰ Time complexity: O(m + n)
  • 🧺 Space complexity: O(1)