Find the number of negative integers in a row wise / column wise sorted matrix.
-3 | -2 | -1 | 4 |
-2 | 2 | 3 | 5 |
-1 | 5 | 7 | 8 |
O/P : 5
Lets understand the question
We need to find the total number of negative integers in a matrix which is both row and column wise sorted.
At 1st row → 3 –ve integers
At 2nd row → 1 –ve integer
At 3rd row → 1 –ve integer
Total → 5 integers
Naïve Approach
We will run a loop for each row and count the numbers which are less than 0.
CODE: In Python
def func(M, n, m): / M = matrix; n = no. of row; m = no. of column
count = 0
for i in range (0, n)
for j in range (0, m)
if M[i][j] < 0
count = count + 1
return count
Time complexity: O(n x m) for the two for loops
Space complexity: O(1)
Optimal Solution:
Let’s read the question once again.
Do you find anything interesting? If not, let me tell you.
There is an important thing written the question “row/column” wise sorted matrix.
-3 | -2 | -1 | 4 |
-2 | 2 | 3 | 5 |
-1 | 5 | 7 | 8 |
For the 1st row the last negative number is – 1
Look carefully and understand that –
If we can find the last negative number in a row then the index associated with it will be the total number of negative numbers in that row.
i.e. for the above example the index of the last negative number is 8.
∴ There are 3 negative numbers in the first row. (as pylon is 0 indexed)
There is also another important thing, it is told that the matrix is also column wise sorted.
∴ After finding the last negative number in the row we can prove to second row at the same index of the last negative number found as it is told already sorted and from there onwards we will find the least negative number in the second row.
This will continue until all the rows are covered.
Let’s move to the algorithm
Step 1: Initialize a variable with 0 to count the negative numbers, i = 0 to store the row number.
Step 2: Run a loop on the condition till the column reaches to 0 and current value of i < the value of total rows.
Step 3: If the current value at M[i][j] < 0
Add count = count + (j + 1)
Step 4: Increment i
Step 5: Else decrement j
Step 6: Run from step 3 to step 5 till the condition fails
Step 7: Return the condition value
Time complexity: O(Max(n, m))
Space complexity: O(1)