Count Negative Numbers in a Sorted Matrix: An Efficient Algorithmic Approach

Introduction

Working with matrices is a common task in computer science and mathematics. In this blog, we will discuss an efficient algorithmic approach to count the negative numbers in a sorted matrix.

Problem Statement

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 the grid.

Background Theory

A matrix is a two-dimensional data structure that consists of rows and columns. It can be represented using a vector of vectors in C++. In this problem, we are given a sorted matrix, which means that the elements in each row and column are sorted in non-increasing order.

Algorithmic Approach

The algorithmic approach to count the negative numbers in a sorted matrix involves the following steps:

Initialize a counter to keep track of the number of negative numbers.
Start from the bottom-left corner of the matrix.
Traverse the matrix using two pointers, one for rows (i) and one for columns (j).
If the current element is negative, increment the counter by the number of remaining elements in the current row and move up to the previous row.
If the current element is non-negative, move to the next column.
Repeat steps 4 and 5 until the pointers reach the boundaries of the matrix.
Return the counter.

Here is the implementation of the algorithm in C++:

int countNegatives(vector<vector<int>>& grid) {
    int count = 0;
    int m = grid.size();
    int n = grid[0].size();
    int i = m - 1;
    int j = 0;

    while (i >= 0 && j < n) {
        if (grid[i][j] < 0) {
            count += n - j;
            i--;
        } else {
            j++;
        }
    }

    return count;
}

Time Complexity

The time complexity of this algorithm is O(m + n), where m is the number of rows and n is the number of columns in the matrix.

Space Complexity

The space complexity of this algorithm is O(1), as we are not using any additional data structures.

Conclusion

In conclusion, we have discussed an efficient algorithmic approach to count the negative numbers in a sorted matrix. This approach has a time complexity of O(m + n) and a space complexity of O(1). This algorithm is efficient and can be used in various applications that involve matrices.

Stackable