LeetCode //C - 1351. Count Negative Numbers in a Sorted Matrix

1351. 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:

Example 2:

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100

From: LeetCode
Link: 1351. Count Negative Numbers in a Sorted Matrix

---

Solution:

Ideas:

This function takes a 2D array grid, the size of the grid gridSize (number of rows), and an array gridColSize containing the size of each column (in this context, it’s the size of each row since it’s a 2D array). The function iterates through each element of the matrix and increments the count whenever it encounters a negative number. Once a negative number is found in a row, it adds the rest of the elements in that row to the count without checking them, as they are guaranteed to be negative, and then breaks out to the next row to optimize performance.

Code:

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    int count = 0;
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridColSize[i]; j++) {
            if (grid[i][j] < 0) {
                // Since the row is sorted in non-increasing order,
                // all following elements in the row are also negative.
                count += gridColSize[i] - j;
                break;
            }
        }
    }
    return count;
}