Number of submatrices with OR value 1 | Javascript program to count 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
var n = 3 function findPrefixCount ( p_arr , arr ) { for ( var i = 0 ; i < n ; i ++ ) for ( var j = n - 1 ; j >= 0 ; j -- ) { if ( arr [ i ] [ j ] ) continue ; if ( j != n - 1 ) p_arr [ i ] [ j ] += p_arr [ i ] [ j + 1 ] ; p_arr [ i ] [ j ] += ( ! arr [ i ] [ j ] ) ; } } function matrixOrValueOne ( arr ) { var p_arr = Array . from ( Array ( n ) , ( ) => Array ( n ) . fill ( 0 ) ) ; findPrefixCount ( p_arr , arr ) ; var count_zero_submatrices = 0 ; for ( var j = 0 ; j < n ; j ++ ) { var i = n - 1 ; var q = [ ] ; var to_sum = 0 ; while ( i >= 0 ) { var c = 0 ; while ( q . length != 0 && q [ q . length - 1 ] [ 0 ] > p_arr [ i ] [ j ] ) { to_sum -= ( q [ q . length - 1 ] [ 1 ] + 1 ) * ( q [ q . length - 1 ] [ 0 ] - p_arr [ i ] [ j ] ) ; c += q [ q . length - 1 ] [ 1 ] + 1 ; q . pop ( ) ; } to_sum += p_arr [ i ] [ j ] ; count_zero_submatrices += to_sum ; q . push ( [ p_arr [ i ] [ j ] , c ] ) ; i -- ; } } return ( n * ( n + 1 ) * n * ( n + 1 ) ) / 4 - count_zero_submatrices ; } var arr = [ [ 0 , 0 , 0 ] , [ 0 , 1 , 0 ] , [ 0 , 0 , 0 ] ] ; document . write ( matrixOrValueOne ( arr ) ) ;