1351. Count Negative Numbers in a Sorted Matrix LeetCode Solution
In this guide, you will get 1351. Count Negative Numbers in a Sorted Matrix LeetCode Solution with the best time and space complexity. The solution to Count Negative Numbers in a Sorted Matrix problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count Negative Numbers in a Sorted Matrix
Given a m x 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
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100
Follow up: Could you find an O(n + m) solution?
Complexity Analysis
Time Complexity: O(m + n)
Space Complexity: O(1)
1351. Count Negative Numbers in a Sorted Matrix LeetCode Solution in C++
class Solution {
public:
int countNegatives(vector<vector<int>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
int ans = 0;
int i = m - 1;
int j = 0;
while (i >= 0 && j < n) {
if (grid[i][j] < 0) {
ans += n - j;
--i;
} else {
++j;
}
}
return ans;
}
}; /* code provided by PROGIEZ */
1351. Count Negative Numbers in a Sorted Matrix LeetCode Solution in Java
class Solution {
public int countNegatives(int[][] grid) {
final int m = grid.length;
final int n = grid[0].length;
int ans = 0;
int i = m - 1;
int j = 0;
while (i >= 0 && j < n) {
if (grid[i][j] < 0) {
ans += n - j;
--i;
} else {
++j;
}
}
return ans;
}
} // code provided by PROGIEZ
1351. Count Negative Numbers in a Sorted Matrix LeetCode Solution in Python
class Solution:
def countNegatives(self, grid: list[list[int]]) -> int:
m = len(grid)
n = len(grid[0])
ans = 0
i = m - 1
j = 0
while i >= 0 and j < n:
if grid[i][j] < 0:
ans += n - j
i -= 1
else:
j += 1
return ans # code by PROGIEZ
