Code Implementation

class Solution:
    def countNegatives(self, grid):
        rows = len(grid)
        cols = len(grid[0])
        count = 0
        row = 0
        col = cols - 1
        while row < rows and col >= 0:
            if grid[row][col] < 0:
                count += rows - row
                col -= 1
            else:
                row += 1
        return count
      

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();
        int count = 0;
        int row = 0, col = cols - 1;
        while (row < rows && col >= 0) {
            if (grid[row][col] < 0) {
                count += rows - row;
                col--;
            } else {
                row++;
            }
        }
        return count;
    }
};
      

class Solution {
    public int countNegatives(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int count = 0;
        int row = 0, col = cols - 1;
        while (row < rows && col >= 0) {
            if (grid[row][col] < 0) {
                count += rows - row;
                col--;
            } else {
                row++;
            }
        }
        return count;
    }
}
      

var countNegatives = function(grid) {
    let rows = grid.length;
    let cols = grid[0].length;
    let count = 0;
    let row = 0, col = cols - 1;
    while (row < rows && col >= 0) {
        if (grid[row][col] < 0) {
            count += rows - row;
            col--;
        } else {
            row++;
        }
    }
    return count;
};
      

Problem Description

You are given a m x n matrix called grid, where each row and each column of the matrix is sorted in non-increasing order (from left to right and from top to bottom). Your task is to count the total number of negative numbers present in the entire matrix.

• Each element in the matrix is an integer.
• The matrix may have multiple rows and columns.
• The sorting constraint means that for any row, the numbers decrease as you move right, and for any column, the numbers decrease as you move down.

Constraints:

• There is only one valid answer for each input.
• You must count each negative number exactly once; do not reuse elements.

Thought Process

At first glance, the most straightforward way to solve this problem is to check every number in the matrix and count how many are negative. However, this approach does not take advantage of the fact that the matrix is sorted in non-increasing order both row-wise and column-wise.

If we think carefully, the sorting property allows us to skip checking certain parts of the matrix. For example, if we find a negative number in a row, all numbers to its right are also negative because the row is sorted in decreasing order. Similarly, if we find a non-negative number, all numbers above it in the same column must be greater or equal, so we don't need to check them.

Our goal is to find an efficient way to traverse the matrix that leverages the sorting to minimize unnecessary checks, moving from a brute-force approach to an optimized solution.

Solution Approach

Let's break down the steps for an optimized solution:

1. Start from the Top-Right Corner:
   • Begin at the element in the first row and last column (top-right of the matrix).
   • This position is strategic because moving left decreases the value (since rows are sorted), and moving down also decreases the value (since columns are sorted).
2. Traverse the Matrix:
   • If the current element is negative, then all elements below it in the same column are also negative (since columns are sorted). So, we can count all those negatives at once: rows - current_row.
   • After counting, move one column to the left (since there might be more negatives in the same row).
   • If the current element is non-negative, move one row down (since there might be negatives further down in the same column).
3. Repeat Until Out of Bounds:
   • Continue this process until you move past the last column (left) or the last row (down).
4. Return the Total Count:
   • The final count will be the total number of negative numbers in the matrix.

This approach is efficient because it skips over large blocks of numbers that are guaranteed to be negative or non-negative, thanks to the matrix's sorting.

Example Walkthrough

Let's consider the following matrix as input:

grid = [
  [4, 3, 2, -1],
  [3, 2, 1, -1],
  [1, 1, -1, -2],
  [-1, -1, -2, -3]
]
  

1. Start at the top-right corner: grid[0][3] = -1 (negative).
   • All elements below in column 3 are also negative. There are 4 rows, and we are at row 0, so 4 - 0 = 4 negatives in this column (rows 0,1,2,3).
   • Add 4 to the count. Move left to column 2.
2. grid[0][2] = 2 (not negative). Move down to row 1.
3. grid[1][2] = 1 (not negative). Move down to row 2.
4. grid[2][2] = -1 (negative).
   • All elements below in column 2 are also negative. There are 4 rows, we are at row 2, so 4 - 2 = 2 negatives.
   • Add 2 to the count. Move left to column 1.
5. grid[2][1] = 1 (not negative). Move down to row 3.
6. grid[3][1] = -1 (negative).
   • All elements below in column 1 (only row 3) are negative. 4 - 3 = 1 negative.
   • Add 1 to the count. Move left to column 0.
7. grid[3][0] = -1 (negative).
   • All elements below in column 0 (only row 3) are negative. 4 - 3 = 1 negative.
   • Add 1 to the count. Move left to column -1 (out of bounds).
8. Done. Total negatives: 4 + 2 + 1 + 1 = 8.

Time and Space Complexity

• Brute-force approach:
  • Check every element in the matrix. If the matrix has m rows and n columns, that's O(m * n) time.
  • Space complexity is O(1) (not counting the input matrix).
• Optimized approach (as above):
  • At most, we make m + n steps (since each move is either down or left, and we can only move down m times or left n times before going out of bounds).
  • So, time complexity is O(m + n).
  • Space complexity remains O(1).

The optimized approach is much faster, especially for large matrices.

Summary

By leveraging the matrix's sorting property, we can efficiently count all negative numbers without scanning every element. Starting from the top-right and moving only left or down allows us to skip over large portions of the matrix, making the solution both elegant and fast. The key insight is recognizing when entire blocks of the matrix are guaranteed to be negative, allowing us to count them in a single step.