text: Count Negative Numbers in a Column | C ++ implementation of More efficient method to count number of negative numbers in row - column sorted matrix M [ n ] [ m ] ; Recursive binary search to get last negative value in a row between a start and an end ; Base case ; Get the mid for binary search ; If current element is negative ; If it is the rightmost negative element in the current row ; Check in the right half of the array ; Check in the left half of the array ; Function to return the count of negative numbers in the given matrix ; Initialize result ; To store the index of the rightmost negative element in the row under consideration ; Iterate over all rows of the matrix ; If the first element of the current row is positive then there will be no negatives in the matrix below or after it ; Run binary search only until the index of last negative Integer in the above row ; Driver code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int getLastNegativeIndex ( int array [ ] , int start , int end , int n ) { if ( start == end ) { return start ; } int mid = start + ( end - start ) / 2 ; if ( array [ mid ] < 0 ) { if ( mid + 1 < n && array [ mid + 1 ] >= 0 ) { return mid ; } return getLastNegativeIndex ( array , mid + 1 , end , n ) ; } else { return getLastNegativeIndex ( array , start , mid - 1 , n ) ; } } int countNegative ( int M [ ] [ 4 ] , int n , int m ) { int count = 0 ; int nextEnd = m - 1 ; for ( int i = 0 ; i < n ; i ++ ) { if ( M [ i ] [ 0 ] >= 0 ) { break ; } nextEnd = getLastNegativeIndex ( M [ i ] , 0 , nextEnd , 4 ) ; count += nextEnd + 1 ; } return count ; } int main ( ) { int M [ ] [ 4 ] = { { -3 , -2 , -1 , 1 } , { -2 , 2 , 3 , 4 } , { 4 , 5 , 7 , 8 } } ; int r = 3 ; int c = 4 ; cout << ( countNegative ( M , r , c ) ) ; return 0 ; }