Leftmost Column with atleast one 1 in a row | Python3 implementation to find the Leftmost Column with atleast a 1 in a sorted binary matrix ; Function to search for the leftmost column of the matrix with atleast a 1 in sorted binary matrix ; Loop to iterate over all the rows of the matrix ; Binary Search to find the leftmost occurence of the 1 ; Condition if the column contains the 1 at this position of matrix ; If there is a better solution then update the answer ; Condition if the solution doesn 't exist in the matrix ; Driver Code
import sys NEW_LINE N = 3 NEW_LINE def search ( mat , n , m ) : NEW_LINE INDENT a = sys . maxsize NEW_LINE for i in range ( n ) : NEW_LINE INDENT low = 0 NEW_LINE high = m - 1 NEW_LINE ans = sys . maxsize NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = ( low + high ) // 2 NEW_LINE if ( mat [ i ] [ mid ] == 1 ) : NEW_LINE INDENT if ( mid == 0 ) : NEW_LINE INDENT ans = 0 NEW_LINE break NEW_LINE DEDENT elif ( mat [ i ] [ mid - 1 ] == 0 ) : NEW_LINE INDENT ans = mid NEW_LINE break NEW_LINE DEDENT DEDENT if ( mat [ i ] [ mid ] == 1 ) : NEW_LINE INDENT high = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT DEDENT if ( ans < a ) : NEW_LINE INDENT a = ans NEW_LINE DEDENT DEDENT if ( a == sys . maxsize ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT return a + 1 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT mat = [ [ 0 , 0 , 0 ] , [ 0 , 0 , 1 ] , [ 0 , 1 , 1 ] ] NEW_LINE print ( search ( mat , 3 , 3 ) ) NEW_LINE DEDENT