FOR FREE YEAR SOLVED

Find the number of negative integers in a row wise / column wise sorted matrix.

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.

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