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):
- If the current element is negative, all elements above it in the same column are also negative.
- If the current element is non-negative, move right to the next element in the same row.
- 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)