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:

JavaScript

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

TypeScript

Written by @Ishitamukherjee2004

 class Solution {
 countNegatives(grid: number[][]): number {
     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;
 }
}

Python

Written by @Ishitamukherjee2004

 class Solution:
 def countNegatives(self, grid: List[List[int]]) -> int:
     m = len(grid)
     n = len(grid[0])
     cnt = 0
     for i in range(m):
         for j in range(n):
             if grid[i][j] < 0:
                 cnt += 1
     return cnt

Java

Written by @Ishitamukherjee2004

 public class Solution {
 public int countNegatives(int[][] grid) {
     int m = grid.length;
     int n = grid[0].length;
     int cnt = 0;
     for (int i = 0; i < m; i++) {
         for (int j = 0; j < n; j++) {
             if (grid[i][j] < 0) cnt++;
         }
     }
     return cnt;
 }
}

C++

Written by @Ishitamukherjee2004

class Solution {
public:
 int countNegatives(vector<vector<int>>& grid) {
     int m = grid.size();
     int n = grid[0].size();
     int cnt = 0;
     for(int i=0; i<m; i++){
         for(int j=0; j<n; j++){
             if(grid[i][j]<0) cnt++;
         }
     }
     return cnt;
 }
};

Complexity Analysis

• Time Complexity: $O(m*n)$
• Space Complexity: $O(1)$
• The time complexity is $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)$ because we are not using any extra space.