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:
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.
Example 2:
Input: grid = [[3,2],[1,0]] Output: 0
Example 3:
Input: grid = [[1,-1],[-1,-1]] Output: 3
Example 4:
Input: grid = [[-1]] Output: 1
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100
Solution 1: Brute Force
Time complexity: O(m*n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua, 16 ms, 10.4 MB class Solution { public: int countNegatives(vector<vector<int>>& grid) { int ans = 0; for (const auto& row : grid) for (const auto x : row) ans += x < 0; return ans; } }; |
Solution 2: Find the frontier
Time complexity: O(m+n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua, 16 ms, 10.4 MB class Solution { public: int countNegatives(vector<vector<int>>& grid) { int ans = 0; int m = grid.size(); int n = grid[0].size(); int r = m - 1; int c = 0; while (r >= 0 && c < n) { if (grid[r][c] < 0) { ans += n - c; --r; } else { ++c; } } return ans; } }; |