Count Negative Numbers in a Sorted Matrix

class Solution {
public:
    int countNegatives(vector<vector<int>>& matrix) {
        int negativeCount = 0;
        int columnCount = matrix[0].size();
        int negativeStartIndex = columnCount - 1;

        for (auto& eachRow : matrix) {
            while (negativeStartIndex >= 0 && eachRow[negativeStartIndex] < 0) {
                negativeStartIndex--;
            }
            negativeCount += (columnCount - (negativeStartIndex + 1));
        }
        return negativeCount;
    }
};

The provided C++ solution efficiently counts the number of negative numbers in a sorted matrix, where each row is sorted in non-increasing order. Upon examining the code, one recognizes a strategy that combines a linear traversal of the matrix rows with a linear scan from the end of each row. This is aimed at quickly locating the transition point between non-negative and negative numbers.

Here's the solution breakdown:

• Initialize negativeCount to accumulate the number of negative numbers across all the rows.
• Utilize columnCount to hold the total number of elements in a row for easy indexing.
• Start negativeStartIndex from the last element of the row, aiming to find the first negative number in reverse order.
• Iterate through each row in the matrix with a for-loop.
• Inside the loop, use while-loop to decrement negativeStartIndex as long as the elements are negative, stopping when a non-negative value is encountered or when it exceeds the row boundaries.
• Update negativeCount after each row iteration, adding up the number of negative elements from the current row based on the final position of negativeStartIndex.
• The function finally returns negativeCount, representing the total count of negative numbers in the matrix.

The algorithm leverages the sorted nature of the matrix to effectively reduce the number of required comparisons, offering a more direct path to counting negatives without checking each element individually. This approach is more efficient than a brute-force method, especially for larger matrices or matrices with many negative numbers skewed towards the end of each row.

int totalNegatives = 0;
    int columns = grid[0].length;
    int lastPositiveIndex = columns - 1;

    for (int[] eachRow : grid) {
        while (lastPositiveIndex >= 0 && eachRow[lastPositiveIndex] < 0) {
            lastPositiveIndex--;
        }
        totalNegatives += (columns - (lastPositiveIndex + 1));
    }
    return totalNegatives;

The provided Java code efficiently counts the number of negative numbers in a sorted matrix where each row is sorted in non-decreasing order. Here's a breakdown of how the code accomplishes this:

• Initialize totalNegatives to keep track of the number of negative elements throughout the matrix.
• Determine the number of columns in the matrix with columns = grid[0].length;.
• Use lastPositiveIndex to find the transition point between positive and negative numbers in each row. It starts at the last index of each row.
• Iterate over each row of the matrix. For each row:
  • Utilize a while loop to decrement lastPositiveIndex as long as the current element at this index is negative. This helps in finding the first negative element of the row.
  • Add the count of negative numbers in the current row to totalNegatives by subtracting the position of the first non-negative number from the total number of columns.
• Finally, return totalNegatives, which now contains the count of all negative numbers in the matrix.

This approach leverages the sorted nature of the matrix efficiently by minimizing the number of elements checked in each row once the first negative element is found.

var countNegativeNumbers = function(matrix) {
    let totalNegatives = 0;
    let columns = matrix[0].length;
    let lastPositiveIndex = columns - 1;

    for (let currentRow of matrix) {
        while (lastPositiveIndex >= 0 && currentRow[lastPositiveIndex] < 0) {
            lastPositiveIndex--;
        }
        totalNegatives += (columns - (lastPositiveIndex + 1));
    }
    return totalNegatives;
};

The provided solution counts the number of negative numbers in a matrix that is sorted in non-increasing order both row-wise and column-wise. The JavaScript function countNegativeNumbers uses an efficient approach leveraging the matrix's sorted property.

• Start by initializing totalNegatives to zero to keep track of the negative numbers.
• Determine the number of columns in the matrix with columns = matrix[0].length.
• Initialize lastPositiveIndex to the last index of a row since the matrix is sorted in a non-increasing order.
• Use a for loop to iterate through each row of the matrix using currentRow.
• Within the loop, use a while loop to update the lastPositiveIndex. This loop decrements lastPositiveIndex until a non-negative number is found or it reaches the beginning of the row.
• Calculate the number of negative numbers in the current row by subtracting (lastPositiveIndex + 1) from columns and add it to totalNegatives.
• Finally, return the totalNegatives.

This method significantly reduces the search space by not re-evaluating the positions in each row starting from the end every time, as the sorted nature means once a negative number is found, all subsequent numbers to the left are also negative. This makes the function run efficiently even for larger matrices.

class Solution:
    def negativeCount(self, matrix: List[List[int]]) -> int:
        total_negatives = 0
        columns = len(matrix[0])
        last_positive_index = columns - 1

        # Process each row in the matrix to count negatives
        for row in matrix:
            # Adjust 'last_positive_index' to always point to last non-negative element in the row
            while last_positive_index >= 0 and row[last_positive_index] < 0:
                last_positive_index -= 1
            # Using 'last_positive_index', count the negatives in current row
            total_negatives += (columns - (last_positive_index + 1))
        return total_negatives

The provided Python solution efficiently counts all negative numbers in a matrix that is sorted in non-descending order by row and column. The matrix is represented as a list of lists, where each inner list is a row of the matrix.

Here's a brief rundown of the implemented logic:

• Initialize a counter total_negatives to track the total count of negative numbers across all rows.
• Determine the number of columns in the matrix by getting the length of the first row.
• last_positive_index is initialized to the last index of each row; it indicates the boundary index beyond which elements become negative.

For each row in the matrix:

1. Adjust last_positive_index to always point to the last non-negative element in the current row. This is performed by checking elements from the current last_positive_index backwards until a negative number is encountered.
2. Calculate the number of negative numbers in the current row by subtracting last_positive_index + 1 (the index of the first negative element) from the total number of columns.
3. Accumulate the count of negatives for each row into total_negatives.

Finally, the function returns the total count of negative numbers in the matrix. This approach ensures that the function only scans back from the last positive index identified in the previous row, leveraging the sorted order of the rows to reduce the number of comparisons and thus improve efficiency.