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} $$

1
2
3

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:

1
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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)