Queries on number of Binary sub | Javascript Program to answer queries on number of submatrix of given size ; Return the minimum of three numbers ; Solve each query on matrix ; For each of the cell . ; finding submatrix size of oth row and column . ; intermediate cells . ; Find frequency of each distinct size for 0 s and 1 s . ; Find the Cumulative Sum . ; Output the answer for each query ; Driver Program
var MAX = 100 var N = 5 var M = 4 function min ( a , b , c ) { return Math . min ( a , Math . min ( b , c ) ) ; } function solveQuery ( n , m , mat , q , a , binary ) { var dp = Array . from ( Array ( n ) , ( ) => Array ( m ) ) ; var max = 1 ; for ( var i = 0 ; i < n ; i ++ ) { for ( var j = 0 ; j < m ; j ++ ) { if ( i == 0 j == 0 ) dp [ i ] [ j ] = 1 ; else if ( ( mat [ i ] [ j ] == mat [ i - 1 ] [ j ] ) && ( mat [ i ] [ j ] == mat [ i ] [ j - 1 ] ) && ( mat [ i ] [ j ] == mat [ i - 1 ] [ j - 1 ] ) ) { dp [ i ] [ j ] = Math . min ( dp [ i - 1 ] [ j ] , dp [ i - 1 ] [ j - 1 ] , dp [ i ] [ j - 1 ] ) + 1 ; if ( max < dp [ i ] [ j ] ) max = dp [ i ] [ j ] ; } else dp [ i ] [ j ] = 1 ; } } var freq0 = Array ( MAX ) . fill ( 0 ) ; var freq1 = Array ( MAX ) . fill ( 0 ) ; for ( var i = 0 ; i < n ; i ++ ) { for ( var j = 0 ; j < m ; j ++ ) { if ( mat [ i ] [ j ] == 0 ) freq0 [ dp [ i ] [ j ] ] ++ ; else freq1 [ dp [ i ] [ j ] ] ++ ; } } for ( var i = max - 1 ; i >= 0 ; i -- ) { freq0 [ i ] += freq0 [ i + 1 ] ; freq1 [ i ] += freq1 [ i + 1 ] ; } for ( var i = 0 ; i < q ; i ++ ) { if ( binary [ i ] == 0 ) document . write ( freq0 [ a [ i ] ] + " " ) ; else document . write ( freq1 [ a [ i ] ] + " " ) ; } } var n = 5 , m = 4 ; var mat = [ [ 0 , 0 , 1 , 1 ] , [ 0 , 0 , 1 , 0 ] , [ 0 , 1 , 1 , 1 ] , [ 1 , 1 , 1 , 1 ] , [ 0 , 1 , 1 , 1 ] ] ; var q = 2 ; var a = [ 2 , 2 ] ; var binary = [ 1 , 0 ] ; solveQuery ( n , m , mat , q , a , binary ) ;