text: Count Negative Numbers in a Column | 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: def getLastNegativeIndex ( array , start , end , n ) : NEW_LINE INDENT if ( start == end ) : NEW_LINE INDENT return start NEW_LINE DEDENT mid = start + ( end - start ) // 2 NEW_LINE if ( array [ mid ] < 0 ) : NEW_LINE INDENT if ( mid + 1 < n and array [ mid + 1 ] >= 0 ) : NEW_LINE INDENT return mid NEW_LINE DEDENT return getLastNegativeIndex ( array , mid + 1 , end , n ) NEW_LINE DEDENT else : NEW_LINE INDENT return getLastNegativeIndex ( array , start , mid - 1 , n ) NEW_LINE DEDENT DEDENT def countNegative ( M , n , m ) : NEW_LINE INDENT count = 0 NEW_LINE nextEnd = m - 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( M [ i ] [ 0 ] >= 0 ) : NEW_LINE INDENT break NEW_LINE DEDENT nextEnd = getLastNegativeIndex ( M [ i ] , 0 , nextEnd , 4 ) NEW_LINE count += nextEnd + 1 NEW_LINE DEDENT return count NEW_LINE DEDENT M = [ [ - 3 , - 2 , - 1 , 1 ] , [ - 2 , 2 , 3 , 4 ] , [ 4 , 5 , 7 , 8 ] ] NEW_LINE r = 3 NEW_LINE c = 4 NEW_LINE print ( countNegative ( M , r , c ) ) NEW_LINE