Leetcode 1351. Count Negative Numbers in a Sorted Matrix

Problem Explanation:

The problem asks to find the count of negative numbers in a sorted two-dimensional matrix. The matrix is sorted in non-increasing order both row-wise and column-wise.

This means that in every row, the numbers are sorted from the biggest on the left to the smallest on the right. And in every column, numbers are sorted from the biggest on the top to the smallest at the bottom.

Let's walk through an example with this matrix:

1
2
3matrix = [
4[ 4, 2, 0,-1],
5[ 3, 1, 0,-2],
6[ 1, 0,-1,-2],
7[-1,-1,-2,-3]
8]

We need to count how many numbers in this matrix are negatives.

The answer is 8, because we have eight negative numbers (-1, -2, -1, -2, -1, -1, -2, -3).

So the function countNegatives(matrix) will return 8.

Approach Explanation:

The solution uses a direct approach to find the count of negative numbers in the sorted two-dimensional matrix. The idea comes from the characteristic of this matrix: Row and Column are both sorted from the biggest number to the smallest one.

We will start from the bottom-left corner of the matrix. If the number is negative, this means all the numbers from current position to the right in the same row are all negative because of the row-wise sorted rule. We can directly add these counts (from current position to the right edge) into our answer. Then we move upward to the next number (same column but the previous row).

If the number is non-negative, we just move to the right (same row but the next column), because all numbers above it in the same column are all bigger (non-negative), so doesn't need to be counted.

We repeat these steps until we finished scanning the entire matrix.

#Python

1
2python
3class Solution:
4    def countNegatives(self, grid):
5        m, n = len(grid), len(grid[0])
6        r, c, cnt = m - 1, 0, 0
7        while r >= 0 and c < n:
8            if grid[r][c] < 0: 
9                cnt += n - c 
10                r -= 1
11            else:
12                c += 1
13        return cnt

#Java

1
2java
3class Solution {
4    public int countNegatives(int[][] grid) {
5        int m = grid.length, n = grid[0].length;
6        int r = m - 1, c = 0, cnt = 0;
7        while (r >= 0 && c < n) {
8            if (grid[r][c] < 0) {
9                cnt += n - c;
10                r--;
11            } else {
12                c++;
13            }
14        }
15        return cnt;
16    }
17}

#C++

1
2c++
3class Solution {
4public:
5    int countNegatives(vector<vector<int>>& grid) {
6        int m = grid.size(), n = grid[0].size();
7        int r = m - 1, c = 0, cnt = 0;
8        while (r >= 0 && c < n) {
9            if (grid[r][c] < 0) {
10                cnt += n - c;
11                r--;
12            } else {
13                c++;
14            }
15        }
16        return cnt;
17    }
18};

#JavaScript

1
2js
3class Solution {
4    countNegatives(grid) {
5        const m = grid.length, n = grid[0].length;
6        let r = m - 1, c = 0, cnt = 0;
7        while (r >= 0 && c < n) {
8            if (grid[r][c] < 0) {
9                cnt += n - c;
10                r--;
11            } else {
12                c++;
13            }
14        }
15        return cnt;
16    }
17}

#Csharp

1
2csharp
3public class Solution {
4    public int CountNegatives(int[][] grid) {
5        int m = grid.Length, n = grid[0].Length;
6        int r = m - 1, c = 0, cnt = 0;
7        while (r >= 0 && c < n) {
8            if (grid[r][c] < 0) {
9                cnt += n - c;
10                r--;
11            } else {
12                c++;
13            }
14        }
15        return cnt;
16    }
17}

#Final Thoughts:

Understanding how the matrix is sorted row-wise and column-wise is the key to the solution. By starting from the bottom-left corner, you can streamline the process and perform the function in less time.

In terms of time complexity, this solution has O(M + N) time complexity where M is the number of rows and N is the number of columns. This is because in the worst-case scenario, you may have to traverse all columns for a single row (when all numbers are positive) and all rows for a single column (when negative numbers are present in every row).

In terms of space complexity, this solution has O(1) space complexity. This is because no matter how large the matrix is, the function doesn't require any additional space to store variables.

Conclusively, the solution is efficient and economical in both time and space aspects.

In addition, the solution is generalizable and can be written in numerous programming languages, including Python, Java, C#, JavaScript, and C++, as provided in the explanation above. Each of these solutions maintains the same logic and strays not from the methodology detailed. As a result, regardless of the programming language used, your approach towards solving the problem would remain the same.