Prerequisites: Matrix, Loops, Observation.
Problem:
Given a N x M matrix which is sorted in non-increasing order both row-wise and column-wise, count the number of negative numbers in matrix.
Solution Approach:
The simple solution is to just iterate through entire matrix and count the no. of negative numbers in it. That will take O(N * M) time. However since matrix is sorted row/column wise non-increasingly, we can use that to our advantage. Let’s see how:
We start from the top-right corner of the matrix. At each row, we iterate column-wise from right to left until we encounter the first non-negative number. Since the matrix is sorted in non-increasing order, once we find a non-negative number, all the elements to its left in that row will also be non-negative. Therefore, we can determine the count of negative numbers in that row by subtracting the column index of the first negative number from the total number of columns and then subtracting one (to exclude the non-negative number itself). We accumulate this count for each row, and at the end of the traversal, we return the total count of negative numbers in the entire matrix.
Time Complexity: O(N + M), as we traverse from right to left and top to bottom only once, in staircase manner.
Space Complexity: O(1).