Queries to count minimum flips required to fill a binary submatrix with 0 s only | Java program for 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 ; Driver Code ; Given matrix ; Function Call
class GFG { final static int M = 6 ; final static int N = 7 ; static void preCompute ( int mat [ ] [ ] , int prefixCnt [ ] [ ] ) { for ( int i = 0 ; i < M ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { if ( mat [ i ] [ j ] == 0 ) { prefixCnt [ i ] [ j ] = 1 ; } else { prefixCnt [ i ] [ j ] = 0 ; } } } for ( int i = 0 ; i < M ; i ++ ) for ( int j = 1 ; j < N ; j ++ ) prefixCnt [ i ] [ j ] += prefixCnt [ i ] [ j - 1 ] ; for ( int i = 1 ; i < M ; i ++ ) for ( int j = 0 ; j < N ; j ++ ) prefixCnt [ i ] [ j ] += prefixCnt [ i - 1 ] [ j ] ; } static int countQuery ( int prefixCnt [ ] [ ] , int pi , int pj , int qi , int qj ) { int 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 ; } static void count0s ( int mat [ ] [ ] , int Q [ ] [ ] , int sizeQ ) { int prefixCnt [ ] [ ] = new int [ M ] [ N ] ; preCompute ( mat , prefixCnt ) ; for ( int i = 0 ; i < sizeQ ; i ++ ) { System . out . print ( countQuery ( prefixCnt , Q [ i ] [ 0 ] , Q [ i ] [ 1 ] , Q [ i ] [ 2 ] , Q [ i ] [ 3 ] ) + " ▁ " ) ; } } public static void main ( String [ ] args ) { int 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 } } ; int Q [ ] [ ] = { { 0 , 1 , 3 , 2 } , { 2 , 2 , 4 , 5 } , { 4 , 3 , 5 , 6 } } ; int sizeQ = Q . length ; count0s ( mat , Q , sizeQ ) ; } }