Skip to main content

Count Negative Numbers in a Sorted Matrix

Problem Description​

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.

Example​

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​

  • 0 <= num <= 106

Solution Approach​

Intuition:​

To efficiently determine the Count Negative Numbers in a Sorted Matrix

Solution Implementation​

Code In Different Languages:​

Written by @Ishitamukherjee2004
 
class Solution {
countNegatives(grid) {
let m = grid.length;
let n = grid[0].length;
let cnt = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] < 0) cnt++;
}
}
return cnt;
}
}

Complexity Analysis​

  • Time Complexity: O(m∗n)O(m*n)
  • Space Complexity: O(1)O(1)
  • The time complexity is O(log(n))O(log(n)) where m and n are the number of rows and columns in the grid, respectively. This is because the algorithm iterates over each element in the grid once.
  • The space complexity is O(1)O(1) because we are not using any extra space.