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 int in the above row ; Driver code
code: using System ; using System . Collections . Generic ; class GFG { static int getLastNegativeIndex ( int [ ] array , int start , int end ) { if ( start == end ) { return start ; } int mid = start + ( end - start ) / 2 ; if ( array [ mid ] < 0 ) { if ( mid + 1 < array . GetLength ( 0 ) && array [ mid + 1 ] >= 0 ) { return mid ; } return getLastNegativeIndex ( array , mid + 1 , end ) ; } else { return getLastNegativeIndex ( array , start , mid - 1 ) ; } } static int countNegative ( int [ , ] M , 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 ( GetRow ( M , i ) , 0 , nextEnd ) ; count += nextEnd + 1 ; } return count ; } public static int [ ] GetRow ( int [ , ] matrix , int row ) { var rowLength = matrix . GetLength ( 1 ) ; var rowVector = new int [ rowLength ] ; for ( var i = 0 ; i < rowLength ; i ++ ) rowVector [ i ] = matrix [ row , i ] ; return rowVector ; } public static void Main ( String [ ] args ) { int [ , ] M = { { - 3 , - 2 , - 1 , 1 } , { - 2 , 2 , 3 , 4 } , { 4 , 5 , 7 , 8 } } ; int r = M . GetLength ( 0 ) ; int c = M . GetLength ( 1 ) ; Console . WriteLine ( countNegative ( M , r , c ) ) ; } }