1351. Count Negative Numbers In A Sorted Matrix

1351. Count Negative Numbers in a Sorted Matrix

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?




 class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:

        # brute force 

        count = 0
        for col in grid:
            for item in col:
                if item < 0:
                    count += 1

        return count

Random Note

From python 3.7 dict guarantees that order will be kept as they inserted, and popitem will use LIFO order but we need FIFO type system. so we need OrderedDict which have popIten(last = T/F) for this req. One thing, next(iter(dict)) will return the first key of the dict

Python