Count negative numbers in a sorted matrix
June 7, 2023
array-and-hashmapProblem URL: Count negative numbers in a sorted matrix
We will iterate through each row and count the number of negative numbers in each row. We will add the count to the total count.
class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
res = 0
r, c = ROWS-1, 0
while r >= 0 and c < COLS:
if grid[r][c] < 0:
res += COLS - c
r -= 1
else:
c += 1
return res
Time complexity: O(n)
Space complexity: O(1)