Check if a matrix contains a square submatrix with 0 as boundary element | Function checks if square with all 0 's in boundary exists in the matrix ; r1 is the top row , c1 is the left col r2 is the bottom row , c2 is the right ; Function checks if the boundary of the square consists of 0 's ; Driver Code
function squareOfZeroes ( matrix ) { var lastIdx = matrix . length - 1 ; var cache = new Map ( ) ; return hasSquareOfZeroes ( matrix , 0 , 0 , lastIdx , lastIdx , cache ) ; } function hasSquareOfZeroes ( matrix , r1 , c1 , r2 , c2 , cache ) { if ( r1 >= r2 c1 >= c2 ) return false ; var key = ( r1 . toString ( ) ) + ' ' + ( c1 . toString ( ) ) + ' ' + ( r2 . toString ( ) ) + ' ' + ( c2 . toString ( ) ) ; if ( cache . has ( key ) ) return cache . get ( key ) ; cache [ key ] = isSquareOfZeroes ( matrix , r1 , c1 , r2 , c2 ) || hasSquareOfZeroes ( matrix , r1 + 1 , c1 + 1 , r2 - 1 , c2 - 1 , cache ) || hasSquareOfZeroes ( matrix , r1 , c1 + 1 , r2 - 1 , c2 , cache ) || hasSquareOfZeroes ( matrix , r1 + 1 , c1 , r2 , c2 - 1 , cache ) || hasSquareOfZeroes ( matrix , r1 + 1 , c1 + 1 , r2 , c2 , cache ) || hasSquareOfZeroes ( matrix , r1 , c1 , r2 - 1 , c2 - 1 , cache ) ; return cache [ key ] ; } function isSquareOfZeroes ( matrix , r1 , c1 , r2 , c2 ) { for ( var row = r1 ; row < r2 + 1 ; row ++ ) { if ( matrix [ row ] [ c1 ] != 0 matrix [ row ] [ c2 ] != 0 ) return false ; } for ( var col = c1 ; col < c2 + 1 ; col ++ ) { if ( matrix [ r1 ] [ col ] != 0 matrix [ r2 ] [ col ] != 0 ) return false ; } return true ; } var matrix = [ [ 1 , 1 , 1 , 0 , 1 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 1 ] , [ 0 , 1 , 1 , 1 , 0 , 1 ] , [ 0 , 0 , 0 , 1 , 0 , 1 ] , [ 0 , 1 , 1 , 1 , 0 , 1 ] , [ 0 , 0 , 0 , 0 , 0 , 1 ] ] ; var ans ; ans = squareOfZeroes ( matrix ) ; if ( ans == 1 ) { document . write ( " " ) ; } else { document . write ( " " ) ; }