Leetcode 1351: Count Negative Numbers in a Sorted Matrix

#leetcode #2darray #python #cpp

Problem statement:
https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/

Let's say we are at i-th row and j-th column. If grid[i][j] < 0, we can say that numbers below grid[i][j] are all negative and count them up. With this, we just start from top right corner to bottom left corner and count the negative numbers column by column.

Runtime: O(M+N)

Python

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        i = 0
        j = n - 1
        count = 0
        while i < m and j >= 0:
            if grid[i][j] < 0:
                count += m - i
                j = j - 1
            else:
                i = i + 1
        return count

C++

class Solution {
  public:
    int countNegatives(const vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int i = 0;
        int j = n - 1;
        int count = 0;
        while(i < m && j >= 0) {
            if(grid[i][j] < 0) {
                count += m - i;
                j = j - 1;
            } else {
                i = i + 1;
            }                
        }
        return count;
    }
};