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.
1#include <stdio.h>
2
3int countNegatives(int** grid, int gridSize, int* gridColSize) {
4 int count = 0;
5 for (int i = 0; i < gridSize; i++) {
6 for (int j = 0; j < gridColSize[i]; j++) {
7 if (grid[i][j] < 0) {
8 count++;
9 }
10 }
11 }
12 return count;
13}
14This C code iterates through each element of the matrix, checking if it is negative. If an element is negative, it increments the count. This is a straightforward implementation of the problem statement.
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)
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.