Count of square submatrices with average at least K | Java 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 ; Driver Code ; Given Input ; Function Call
import java . util . * ; class GFG { static int MAX = 1000 ; static int cntMatrices ( int [ ] [ ] arr , int N , int M , int K ) { int cnt = 0 ; int [ ] [ ] pre = new int [ N + 1 ] [ M + 1 ] ; for ( int i = 1 ; i <= N ; i ++ ) { for ( int 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 ( int i = 1 ; i <= N ; i ++ ) { for ( int j = 1 ; j <= M ; j ++ ) { for ( int l = i , r = j ; l > 0 && r > 0 ; l -- , r -- ) { int sum1 = ( K * ( i - l + 1 ) * ( i - r + 1 ) ) ; int sum2 = pre [ i ] [ j ] - pre [ l - 1 ] [ r ] - pre [ l ] [ r - 1 ] + pre [ l - 1 ] [ r - 1 ] ; if ( sum1 <= sum2 ) cnt ++ ; } } } return cnt ; } public static void main ( String args [ ] ) { int [ ] [ ] arr = { { 2 , 2 , 3 } , { 3 , 4 , 5 } , { 4 , 5 , 5 } } ; int K = 4 ; int N = arr . length ; int M = arr [ 0 ] . length ; System . out . println ( cntMatrices ( arr , N , M , K ) ) ; } }