Queries to count minimum flips required to fill a binary submatrix with 0 s only | javascript program of the above approach ; Function to compute the matrix prefixCnt [ M ] [ N ] from mat [ M ] [ N ] such that prefixCnt [ i ] [ j ] stores the count of 0 's from (0, 0) to (i, j) ; Initialize prefixCnt [ i ] [ j ] with 1 if mat [ i ] [ j ] is 0 ; Otherwise , assign with 0 ; Calculate prefix sum for each row ; Calculate prefix sum for each column ; Function to compute count of 0 's in submatrix from (pi, pj) to (qi, qj) from prefixCnt[M][N] ; Initialize that count of 0 's  in the sub-matrix within  indices (0, 0) to (qi, qj) ; Subtract count of 0 's within  indices (0, 0) and (pi-1, qj) ; Subtract count of 0 's within  indices (0, 0) and (qi, pj-1) ; Add prefixCnt [ pi - 1 ] [ pj - 1 ] because its value has been added ; once but subtracted twice ; Function to count the 0 s in the each given submatrix ; Stores the prefix sum of each row and column ; Compute matrix prefixCnt [ ] [ ] ; Function Call for each query ; Given matrix ; Function Call
let M = 6 ; let N = 7 ; function preCompute ( mat , prefixCnt ) { for ( let i = 0 ; i < M ; i ++ ) { for ( let j = 0 ; j < N ; j ++ ) { if ( mat [ i ] [ j ] == 0 ) { prefixCnt [ i ] [ j ] = 1 ; } else { prefixCnt [ i ] [ j ] = 0 ; } } } for ( let i = 0 ; i < M ; i ++ ) for ( let j = 1 ; j < N ; j ++ ) prefixCnt [ i ] [ j ] += prefixCnt [ i ] [ j - 1 ] ; for ( let i = 1 ; i < M ; i ++ ) for ( let j = 0 ; j < N ; j ++ ) prefixCnt [ i ] [ j ] += prefixCnt [ i - 1 ] [ j ] ; } function countQuery ( prefixCnt , pi , pj , qi , qj ) { let cnt = prefixCnt [ qi ] [ qj ] ; if ( pi > 0 ) cnt -= prefixCnt [ pi - 1 ] [ qj ] ; if ( pj > 0 ) cnt -= prefixCnt [ qi ] [ pj - 1 ] ; if ( pi > 0 && pj > 0 ) cnt += prefixCnt [ pi - 1 ] [ pj - 1 ] ; return cnt ; } function count0s ( mat , Q , sizeQ ) { let prefixCnt = new Array ( M ) ; for ( var i = 0 ; i < prefixCnt . length ; i ++ ) { prefixCnt [ i ] = new Array ( 2 ) ; } preCompute ( mat , prefixCnt ) ; for ( let i = 0 ; i < sizeQ ; i ++ ) { document . write ( countQuery ( prefixCnt , Q [ i ] [ 0 ] , Q [ i ] [ 1 ] , Q [ i ] [ 2 ] , Q [ i ] [ 3 ] ) + " " ) ; } } let mat = [ [ 0 , 1 , 0 , 1 , 1 , 1 , 0 ] , [ 1 , 0 , 1 , 1 , 1 , 0 , 1 ] , [ 1 , 1 , 0 , 0 , 1 , 1 , 0 ] , [ 1 , 1 , 1 , 1 , 1 , 0 , 1 ] , [ 0 , 0 , 1 , 0 , 1 , 1 , 1 ] , [ 1 , 1 , 0 , 1 , 1 , 0 , 1 ] ] ; let Q = [ [ 0 , 1 , 3 , 2 ] , [ 2 , 2 , 4 , 5 ] , [ 4 , 3 , 5 , 6 ] ] ; let sizeQ = Q . length ; count0s ( mat , Q , sizeQ ) ;