Number of submatrices with OR value 1 | Function to find required prefix - count for each row from right to left ; Function to find the count of submatrices with OR value 1 ; Array to store prefix count of zeros from right to left for boolean array ; Variable to store the count of submatrices with OR value 0 ; Loop to evaluate each column of the prefix matrix uniquely . For each index of a column we will try to determine the number of sub - matrices starting from that index and has all 1 s ; First part of pair will be the value of inserted element . Second part will be the count of the number of elements pushed before with a greater value ; Variable to store the number of submatrices with all 0 s ; Return the final answer ; Driver Code
def findPrefixCount ( p_arr , arr ) : NEW_LINE INDENT for i in range ( 0 , n ) : NEW_LINE INDENT for j in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT if arr [ i ] [ j ] : NEW_LINE INDENT continue NEW_LINE DEDENT if j != n - 1 : NEW_LINE INDENT p_arr [ i ] [ j ] += p_arr [ i ] [ j + 1 ] NEW_LINE DEDENT p_arr [ i ] [ j ] += int ( not arr [ i ] [ j ] ) NEW_LINE DEDENT DEDENT DEDENT def matrixOrValueOne ( arr ) : NEW_LINE INDENT p_arr = [ [ 0 for i in range ( n ) ] for j in range ( n ) ] NEW_LINE findPrefixCount ( p_arr , arr ) NEW_LINE count_zero_submatrices = 0 NEW_LINE for j in range ( 0 , n ) : NEW_LINE INDENT i = n - 1 NEW_LINE q = [ ] NEW_LINE to_sum = 0 NEW_LINE while i >= 0 : NEW_LINE INDENT c = 0 NEW_LINE while ( len ( q ) != 0 and q [ - 1 ] [ 0 ] > p_arr [ i ] [ j ] ) : NEW_LINE INDENT to_sum -= ( ( q [ - 1 ] [ 1 ] + 1 ) * ( q [ - 1 ] [ 0 ] - p_arr [ i ] [ j ] ) ) NEW_LINE c += q . pop ( ) [ 1 ] + 1 NEW_LINE DEDENT to_sum += p_arr [ i ] [ j ] NEW_LINE count_zero_submatrices += to_sum NEW_LINE q . append ( ( p_arr [ i ] [ j ] , c ) ) NEW_LINE i -= 1 NEW_LINE DEDENT DEDENT return ( ( n * ( n + 1 ) * n * ( n + 1 ) ) // 4 - count_zero_submatrices ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 3 NEW_LINE arr = [ [ 0 , 0 , 0 ] , [ 0 , 1 , 0 ] , [ 0 , 0 , 0 ] ] NEW_LINE print ( matrixOrValueOne ( arr ) ) NEW_LINE DEDENT