Sponsored
Sponsored
The naive approach is to iterate over every element of the matrix and count the negative numbers. Since the matrix dimensions are at most 100x100, this method is feasible but not the most efficient. However, this approach is simple to implement and understand.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(1) as we are using constant extra space.
1public class Solution {
2 public int CountNegatives(int[][] grid) {
3 int count = 0;
4 foreach (var row in grid) {
5 foreach (var num in row) {
6 if (num < 0) {
7 count++;
8 }
9 }
10 }
11 return count;
12 }
13}
14This C# code uses nested foreach loops to traverse through the matrix. It counts each element if it is negative.
Utilizing the sorted nature of the matrix, start from the bottom-left or top-right corner to efficiently count negative numbers. You only need to traverse the elements once, either moving inward along a row or column while counting negatives. This can reduce the time complexity to O(n + m), significantly improving performance for large matrices.
Time Complexity: O(n + m)
Space Complexity: O(1)
This C solution leverages the sorted nature by starting from the top-right corner. It moves left if the current number is negative, counting all numbers below, and down if it is non-negative.