Last Updated: 1 Dec, 2021
Total Negative Numbers In A Sorted Matrix
Easy
Asked in company
You are given an ‘N’ x ‘M’ matrix ‘MAT’, which is sorted in non-increasing order both row-wise and column-wise. Your task is to count the number of negative numbers in ‘MAT’.
For Example:
You are given ‘N’ = 3, ‘M’ = 2 and ‘MAT’= [[3, 1],[2, -1],[1, 2]]. Then the answer will be two for the first test case because there are two negative numbers in the given matrix(-1, -2).
Input Format :
The first line of the input contains a single integer 'T', representing the number of test cases.
The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, representing the number of rows and columns in ‘MAT’, respectively.
The next ‘N’ lines contain ‘M’ space-separated integers representing the elements of ‘MAT’.
Output Format:
For each test case, print the number of negative numbers in ‘MAT’.
Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 5000
1 <= M <= 5000
-10^6 <= MAT[i][j] <= 10^6
Time Limit: 1 sec
Approaches
In this approach, we will check every element of the matrix, and for each negative number, we will increment our answer by 1. We will use two nested loops to traverse the given matrix and a variable ‘COUNT’ to store the count of the negative numbers. The final value of ‘COUNT’ will be our answer.
Algorithm :
- Initialize a variable ‘COUNT’ to store the count of negative numbers.
- Iterate ‘I’ in 0 to ‘MAT.LENGTH’:
- Iterate ‘J’ in 0 to ‘MAT[0].LENGTH’:
- If ‘MAT’[‘I’][‘J’] is less than 0, increment ‘COUNT’ by 1.
- Iterate ‘J’ in 0 to ‘MAT[0].LENGTH’:
- Return ‘COUNT’.
In this approach, we will use the fact that each row is sorted in non-increasing order. This means all the numbers lying left to a negative number will be negative. So, we will try to find a negative number in each row using binary search. For each row, we will start with the middle number. If the middle number is negative, we will skip searching the right partition and search for more negative numbers in the left partition. If the middle number is not negative, we will skip searching the left partition and search for negative numbers in the right partition.
Algorithm :
- Initialize a variable ‘COUNT’ to store the count of negative numbers.
- Iterate ‘I’ in 0 to ‘MAT.LENGTH’:
- Set ‘LOW’ as 0 and ‘HIGH’ as ‘MAT’[0].LENGTH.
- Iterate while ‘LOW’ is less than or equal to ‘HIGH’:
- Set ‘MID’ as ‘LOW’ + (‘HIGH’ - ‘LOW’)/2.
- If ‘MAT’[‘I’][‘MID’] is greater than or equal to 0:
- Set ‘LOW’ as ‘MID’ + 1.
- Otherwise:
- Set ‘COUNT’ as ‘COUNT’ + ‘HIGH’ - ‘MID’ + 1.
- Set ‘HIGH’ as ‘MID’ - 1.
- Return ‘COUNT’.
In this approach, we will use the fact that the matrix is sorted in non-increasing order, both row-wise and column-wise. For every negative number, all the numbers lying to its left and down will also be negative. We will start traversing the row from the rightmost element for every row starting from the top row. Now two cases arise:
- If the current element is negative, then all elements lying down will also be negative. So, we skip checking those elements and move to the left in the current row.
- If the current element is positive, all the elements to its left will be positive so we move downward in the same column.
Algorithm :
- Initialize a variable ‘COUNT’ to store the count of negative numbers.
- Initialize a variable ‘N’ to store the number of rows.
- Initialize a variable ‘M’ to store the number of columns.
- Set ‘I’ as 0 and ‘J’ as ‘M’ - 1.
- Iterate while ‘I’ is less than ‘N,’ and ‘J’ is greater or equal to 0:
- If ‘MAT’[‘I’][‘J’] is less than 0:
- Set ‘COUNT’ as ‘COUNT’ + ‘N’ - ‘I’.
- Decrement ‘J’ by 1.
- Otherwise, increment ‘I’ by 1.
- If ‘MAT’[‘I’][‘J’] is less than 0:
- Return ‘COUNT’.