Count Negative Numbers in a Column | Java 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
import java . util . * ; import java . lang . * ; import java . io . * ; 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 . length && 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 ( M [ i ] , 0 , nextEnd ) ; count += nextEnd + 1 ; } return count ; } public static void main ( String [ ] args ) { int M [ ] [ ] = { { - 3 , - 2 , - 1 , 1 } , { - 2 , 2 , 3 , 4 } , { 4 , 5 , 7 , 8 } } ; int r = M . length ; int c = M [ 0 ] . length ; System . out . println ( countNegative ( M , r , c ) ) ; } }