Count Below-Zero Cells
EasyMatrixFree
Problem
A cold-storage warehouse logs temperatures on an m × n grid of sensors. Because the cooling unit sits in the bottom-right corner, every row is sorted in non-increasing order from left to right and every column is sorted in non-increasing order from top to bottom.
Return how many sensors read a strictly negative temperature. Aim for O(m + n) time.
Example 1
- Input:
- grid = [[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]]
- Output:
- 8
The rows contain 1, 1, 2 and 4 negative values.
Example 2
- Input:
- grid = [[3, 2], [1, 0]]
- Output:
- 0
Zero is not negative.
Constraints
- 1 ≤ m, n ≤ 1000
- -100 ≤ grid[i][j] ≤ 100
- Rows and columns are sorted in non-increasing order.
Hint
Show the first hint
Because rows are sorted, the negatives in each row form a suffix. Because columns are sorted too, how does that suffix move from one row to the next?
Walkthrough
How to approach it
01Clarify before coding
- Does zero count? No, only strictly negative readings.
- Are both rows and columns sorted? Yes, both non-increasing, which is what allows a linear walk.
- Can the whole grid be negative or non-negative? Yes, return m · n or 0.
02Brute force
Check every cell, or binary-search the first negative in each row.
Cost: Full scan O(m · n); per-row binary search O(m log n). Neither uses the column order.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.