Count of square submatrices with average at least K | Javascript program for the above approach ; Function to count submatrixes with average greater than or equals to K ; Stores count of submatrices ; Stores the prefix sum of matrix ; Iterate over the range [ 1 , N ] ; Iterate over the range [ 1 , M ] ; Update the prefix sum ; Iterate over the range [ 1 , N ] ; Iterate over the range [ 1 , M ] ; Iterate until l and r are greater than 0 ; Update count ; Stores sum of submatrix with bottom right corner as ( i , j ) and top left corner as ( l , r ) ; If sum1 is less than or equal to sum2 ; Increment cnt by 1 ; Return cnt as the answer ; Given Input ; Function Call
let MAX = 1000 function cntMatrices ( arr , N , M , K ) { let cnt = 0 ; let pre = new Array ( N + 1 ) . fill ( 0 ) . map ( ( ) => new Array ( M + 1 ) . fill ( 0 ) ) for ( let i = 1 ; i <= N ; i ++ ) { for ( let j = 1 ; j <= M ; j ++ ) { pre [ i ] [ j ] = arr [ i - 1 ] [ j - 1 ] + pre [ i - 1 ] [ j ] + pre [ i ] [ j - 1 ] - pre [ i - 1 ] [ j - 1 ] ; } } for ( let i = 1 ; i <= N ; i ++ ) { for ( let j = 1 ; j <= M ; j ++ ) { for ( let l = i , r = j ; l > 0 && r > 0 ; l -- , r -- ) { let sum1 = ( K * ( i - l + 1 ) * ( i - r + 1 ) ) ; let sum2 = pre [ i ] [ j ] - pre [ l - 1 ] [ r ] - pre [ l ] [ r - 1 ] + pre [ l - 1 ] [ r - 1 ] ; if ( sum1 <= sum2 ) cnt ++ ; } } } return cnt ; } let arr = [ [ 2 , 2 , 3 ] , [ 3 , 4 , 5 ] , [ 4 , 5 , 5 ] ] ; let K = 4 ; let N = arr . length ; let M = arr [ 0 ] . length ; document . write ( cntMatrices ( arr , N , M , K ) ) ;