Given a Boolean Matrix , find k such that all elements in k ' th ▁ row ▁ are ▁ 0 ▁ and ▁ k ' th column are 1. | Python program to find k such that all elements in k ' th ▁ row ▁ ▁ ▁ are ▁ 0 ▁ and ▁ k ' th column are 1 ; start from top right - most corner ; initialise result ; find the index ( This loop runs at most 2 n times , we either increment row number or decrement column number ) ; if the current element is 0 , then this row may be a solution ; check for all the elements in this row ; if all values are 0 , update result as row number ; if found a 1 in current row , the row can 't be a   solution, increment row number ; if the current element is 1 ; check for all the elements in this column ; if all elements are 1 , update result as col number ; if found a 0 in current column , the column can 't be a  solution, decrement column number ; if we couldn ' t ▁ find ▁ result ▁ in ▁ above ▁ loop , ▁ result ▁ doesn ' t exist ; check if the above computed res value is valid ; test find ( arr ) function
def find ( arr ) : NEW_LINE INDENT n = len ( arr ) NEW_LINE i = 0 NEW_LINE j = n - 1 NEW_LINE res = - 1 NEW_LINE while i < n and j >= 0 : NEW_LINE INDENT if arr [ i ] [ j ] == 0 : NEW_LINE INDENT while j >= 0 and ( arr [ i ] [ j ] == 0 or i == j ) : NEW_LINE INDENT j -= 1 NEW_LINE DEDENT if j == - 1 : NEW_LINE INDENT res = i NEW_LINE break NEW_LINE DEDENT else : i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT while i < n and ( arr [ i ] [ j ] == 1 or i == j ) : NEW_LINE INDENT i += 1 NEW_LINE DEDENT if i == n : NEW_LINE INDENT res = j NEW_LINE break NEW_LINE DEDENT else : j -= 1 NEW_LINE DEDENT DEDENT if res == - 1 : NEW_LINE INDENT return res NEW_LINE DEDENT for i in range ( 0 , n ) : NEW_LINE INDENT if res != i and arr [ i ] [ res ] != 1 : NEW_LINE INDENT return - 1 NEW_LINE DEDENT DEDENT for j in range ( 0 , j ) : NEW_LINE INDENT if res != j and arr [ res ] [ j ] != 0 : NEW_LINE INDENT return - 1 ; NEW_LINE DEDENT DEDENT return res ; NEW_LINE DEDENT arr = [ [ 0 , 0 , 1 , 1 , 0 ] , [ 0 , 0 , 0 , 1 , 0 ] , [ 1 , 1 , 1 , 1 , 0 ] , [ 0 , 0 , 0 , 0 , 0 ] , [ 1 , 1 , 1 , 1 , 1 ] ] NEW_LINE print find ( arr ) NEW_LINE