431. Count Negative Numbers in Sorted Matrix

Given a m x n matrix grid where each row is sorted in non-increasing order and each column is sorted in non-increasing order, return the number of negative numbers in grid. Solve in O(m log n) using binary search per row.

Input: A 2D integer matrix grid sorted non-increasingly per row.

Output: Count of negative numbers in the grid.

Examples

Input: [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: Row 0: 1 negative. Row 1: 1 negative. Row 2: 2 negatives. Row 3: 4 negatives. Total=8.

Input: [[3,2],[1,0]]
Output: 0
Explanation: No negative numbers.

Input: [[-1]]
Output: 1
Explanation: Single negative element.

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m,n <= 100
• -100 <= grid[i][j] <= 100
• Each row non-increasing
• Each column non-increasing

Asked by