Solved! Leetcode 1351. Count Negative Numbers in a Sorted Matrix

source: https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/description/

Count Negative Numbers in a Sorted Matrix

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

Solution

class Solution {
    public int countNegatives(int[][] grid) {
         if(grid==null)
            return 0;
        int i=0;
        int j=grid[i].length-1;
        int count = 0;
        while(isValid(grid, i, j)){
            //move to the right till you find a negative number
            while(j-1>=0 && grid[i][j-1]<0){
                j--;
            }
            //add it to the count
            if(grid[i][j]<0)
                count += (grid[i].length - j);
            //move to the next row
            i++;
        }
        return count;
    }

    private boolean isValid(int[][] grid, int i, int j){
        if(i<0 || i>=grid.length
        || j<0 || j>=grid[i].length)
            return false;
        return true;
    }
}

class Solution {

public int countNegatives(int[][] grid) {

if(grid==null)

return 0;

int i=0;

int j=grid[i].length-1;

int count = 0;

while(isValid(grid, i, j)){

//move to the right till you find a negative number

while(j-1>=0 && grid[i][j-1]<0){

j--;

}

//add it to the count

if(grid[i][j]<0)

count += (grid[i].length - j);

//move to the next row

i++;

}

return count;

}

private boolean isValid(int[][] grid, int i, int j){

if(i<0 || i>=grid.length

|| j<0 || j>=grid[i].length)

return false;

return true;

}

Follow up

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

Rate this post

Coddicted