Maximum size of square such that all submatrices of that size have sum less than K | C ++ implementation to find the maximum size square submatrix such that their sum is less than K ; Size of matrix ; Function to preprocess the matrix for computing the sum of every possible matrix of the given size ; Loop to copy the first row of the matrix into the aux matrix ; Computing the sum column - wise ; Computing row wise sum ; Function to find the sum of a submatrix with the given indices ; Overall sum from the top to right corner of matrix ; Removing the sum from the top corer of the matrix ; Remove the overlapping sum ; Add the sum of top corner which is subtracted twice ; Function to check whether square sub matrices of size mid satisfy the condition or not ; Iterating throught all possible submatrices of given size ; Function to find the maximum square size possible with the such that every submatrix have sum less than the given sum ; Search space ; Binary search for size ; Check if the mid satisfies the given condition ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  4 NEW_LINE #define M  5 NEW_LINE void preProcess ( int mat [ N ] [ M ] , int aux [ N ] [ M ] ) { for ( int i = 0 ; i < M ; i ++ ) aux [ 0 ] [ i ] = mat [ 0 ] [ i ] ; for ( int i = 1 ; i < N ; i ++ ) for ( int j = 0 ; j < M ; j ++ ) aux [ i ] [ j ] = mat [ i ] [ j ] + aux [ i - 1 ] [ j ] ; for ( int i = 0 ; i < N ; i ++ ) for ( int j = 1 ; j < M ; j ++ ) aux [ i ] [ j ] += aux [ i ] [ j - 1 ] ; } int sumQuery ( int aux [ N ] [ M ] , int tli , int tlj , int rbi , int rbj ) { int res = aux [ rbi ] [ rbj ] ; if ( tli > 0 ) res = res - aux [ tli - 1 ] [ rbj ] ; if ( tlj > 0 ) res = res - aux [ rbi ] [ tlj - 1 ] ; if ( tli > 0 && tlj > 0 ) res = res + aux [ tli - 1 ] [ tlj - 1 ] ; return res ; } bool check ( int mid , int aux [ N ] [ M ] , int K ) { bool satisfies = true ; for ( int x = 0 ; x < N ; x ++ ) { for ( int y = 0 ; y < M ; y ++ ) { if ( x + mid - 1 <= N - 1 && y + mid - 1 <= M - 1 ) { if ( sumQuery ( aux , x , y , x + mid - 1 , y + mid - 1 ) > K ) satisfies = false ; } } } return ( satisfies == true ) ; } int maximumSquareSize ( int mat [ N ] [ M ] , int K ) { int aux [ N ] [ M ] ; preProcess ( mat , aux ) ; int low = 1 , high = min ( N , M ) ; int mid ; while ( high - low > 1 ) { mid = ( low + high ) / 2 ; if ( check ( mid , aux , K ) ) { low = mid ; } else high = mid ; } if ( check ( high , aux , K ) ) return high ; return low ; } int main ( ) { int K = 30 ; int mat [ N ] [ M ] = { { 1 , 2 , 3 , 4 , 6 } , { 5 , 3 , 8 , 1 , 2 } , { 4 , 6 , 7 , 5 , 5 } , { 2 , 4 , 8 , 9 , 4 } } ; cout << maximumSquareSize ( mat , K ) ; return 0 ; }