1351. Count Negative Numbers in a Sorted Matrix (Leetcode || Java || Easy)

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 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:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100

Follow up: Could you find an O(n + m) solution?

SOLUTION:

class Solution {
public int countNegatives(int[][] grid) {
int count = 0;//counter variable for counting the number of negatives

int row = 0;
int col = grid[0].length — 1;

while(row < grid.length && col >= 0){//Applying binary search

if(grid[row][col] < 0){//if the end element is less than 0 it means that all theh elements in that column are going to be less than 0, hence count all the elements after that negative element from that column and count that negative element also
col — ;
count += grid.length — row;
}else{
row++;//if the last element is not negative it means that all the elements in that row are also not negative as the row is arranged in descending order
}
}

return count;//return total negative elements
}
}

TIME COMPLEXITY :- O(log(n))

SPACE COMPLEXITY :- O(1)

Thank you for reading. If you have any queries, please let me know in the comment section.