Given an n x n square matrix , find sum of all sub | Size of given matrix ; A O ( n ^ 2 ) function to find sum of all sub - squares of size k x k in a given square matrix of size n x n ; k must be smaller than or equal to n ; 1 : PREPROCESSING To store sums of all strips of size k x 1 ; Go column by column ; Calculate sum of first k x 1 rectangle in this column ; Calculate sum of remaining rectangles ; 2 : CALCULATE SUM of Sub - Squares using stripSum [ ] [ ] ; Calculate and print sum of first subsquare in this row ; Calculate sum of remaining squares in current row by removing the leftmost strip of previous sub - square and adding a new strip ; Driver code
let n = 5 ; function printSumTricky ( mat , k ) { if ( k > n ) return ; let stripSum = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { stripSum [ i ] = new Array ( n ) ; } for ( let i = 0 ; i < n ; i ++ ) { for ( let j = 0 ; j < n ; j ++ ) { stripSum [ i ] [ j ] = 0 ; } } for ( let j = 0 ; j < n ; j ++ ) { let sum = 0 ; for ( let i = 0 ; i < k ; i ++ ) sum += mat [ i ] [ j ] ; stripSum [ 0 ] [ j ] = sum ; for ( let i = 1 ; i < n - k + 1 ; i ++ ) { sum += ( mat [ i + k - 1 ] [ j ] - mat [ i - 1 ] [ j ] ) ; stripSum [ i ] [ j ] = sum ; } } for ( let i = 0 ; i < n - k + 1 ; i ++ ) { let sum = 0 ; for ( let j = 0 ; j < k ; j ++ ) sum += stripSum [ i ] [ j ] ; document . write ( sum + " " ) ; for ( let j = 1 ; j < n - k + 1 ; j ++ ) { sum += ( stripSum [ i ] [ j + k - 1 ] - stripSum [ i ] [ j - 1 ] ) ; document . write ( sum + " " ) ; } document . write ( " " ) ; } } let mat = [ [ 1 , 1 , 1 , 1 , 1 ] , [ 2 , 2 , 2 , 2 , 2 ] , [ 3 , 3 , 3 , 3 , 3 ] , [ 4 , 4 , 4 , 4 , 4 ] , [ 5 , 5 , 5 , 5 , 5 ] ] ; let k = 3 ; printSumTricky ( mat , k ) ;