232. Below Zero Count
A thermometer network reports temperatures in a grid grid. Because of the way the sensors are laid out, the readings never increase as you move to the right along a row, and never increase as you move down along a column. In other words every row is sorted in non-increasing order and every column is sorted in non-increasing order.
Count how many readings are below zero (strictly negative) and return that count. Because of the sorted layout, all the negative readings are gathered in the bottom-right part of the grid, which means you can count them without looking at every single cell.
Example 1
- Input:
- grid = [[9,7,4,-1],[8,5,0,-2],[3,-3,-5,-6]]
- Output:
- 5
- Explanation:
Row 0 has 1 negative (-1), row 1 has 1 negative (-2) and row 2 has 3 negatives (-3, -5, -6): 5 in total.
Example 2
- Input:
- grid = [[3,2],[1,0]]
- Output:
- 0
- Explanation:
No reading is below zero, because 0 is not negative.
Example 3
- Input:
- grid = [[-1,-2,-3]]
- Output:
- 3
- Explanation:
All three readings of the single row are negative.
Constraints
1 ≤ grid.length, grid[0].length ≤ 100
-100 ≤ grid[i][j] ≤ 100
Rows and columns are sorted in non-increasing order.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(m + n)
- Space
- O(1)