Count Negative Numbers in a Sorted Matrix
Easy · Binary Search · Array · Binary Search · Matrix
Problem
You are given an m x n matrix grid in which every row and every column is sorted in non-increasing order.
Return the number of negative values in grid.
Examples
Input: grid = [[5,2,-1],[3,0,-2],[1,-3,-4]] Output: 4
The negatives are -1, -2, -3 and -4.
Input: grid = [[4,1],[2,0]] Output: 0
No value is below zero; 0 is not negative.
Input: grid = [[-1]] Output: 1
The only value is negative.
Constraints
- m == len(grid), n == len(grid[i])
- 1 <= m, n <= 100
- -100 <= grid[i][j] <= 100
Approaches
- Binary search in every row — time O(m log n), space O(1)
Follow-up
Can you do it in O(m + n) time? The staircase walk does, by using the row and the column order together. See the use cases for a binary matrix where only the rows are sorted, and for counting the values at most any k in a matrix sorted the other way.
Related problems
Start free on Cariara · Coding problems · System design studio
