LeetCode 1351. Count Negative Numbers in a Sorted Matrix

, , ,

Question

Given a m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise.

Return the number of negative numbers in grid.

Example

1
2
3
4
5
6
7
8
9
Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

Input: grid = [[3,2],[1,0]]
Output: 0

Input: grid = [[1,-1],[-1,-1]]
Output: 3

Solution

You can solve it by brute force. But you also can traversal from the top-right position, when it is smaller than 0, we can add one columum in one time and move. Otherwise, we go to the next row.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// time:O(m + n) space:O(1)
public int countNegatives(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return 0;
        int m = grid.length;
        int n = grid[0].length;
        int row = 0; // 从右上角开始
        int col = n - 1;
        int res = 0;
        while (row < m && col >= 0) {
            if (grid[row][col] < 0) {
                res += m - row;
                col--;
            } else {
                row++;
            }
        }
        return res;
    }

Reference