Check if a matrix contains a square submatrix with 0 as boundary element
Given an N*N binary matrix arr[][], the task is to check if the matrix contains a square of at least size 2 x 2 whose boundaries are made up of only 0s.
Examples:
Input:
arr[][] = {
{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}
}
Output: True
Explanation:
Since, arr[][] contains square matrix with all 0’s at boundary, so answer is True.
{
{ ?, ?, ?, ?, ?, },
{0, ? 0, ? 0, ? 0, ? 0, },
{0, ?, ?, ?, ? 0, },
{0, ?, ?, ?, ? 0, },
{0, ?, ?, ?, ?0, },
{0, ? 0, ? 0, ? 0, ? 0, }
}Input:
arr[][] = {
{1, 1, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 1},
{0, 1, 1, 1, 0, 1},
{0, 0, 0, 1, 1, 1},
{0, 1, 1, 1, 0, 1},
{0, 0, 0, 0, 0, 1}
}
Output: False
Explanation: There is no square in the matrix whose borders are made up of only 0s.
Approach:
- A square is defined by its topmost and bottommost rows and by its leftmost and rightmost columns.
- Given a pair of rows and a pair of columns that form a valid square, you can easily determine if the relevant square is a square of zeroes with two for loops.
- It is required to iterate over every valid square in the input matrix, arr[][].
- We can start iterating from the outermost square and recursively go inwards in the matrix.
- On moving inward, from (r1, c1) and (r2, c2) we have 5 options, which will generate square matrix:-
a) (r1 + 1, c1 + 1), (r2 – 1, c2 – 1)
b) (r1, c1 + 1), (r2 – 1, c2)
c) (r1 + 1, c1), (r2, c2 – 1)
d) (r1 + 1, c1 + 1), (r2, c2)
e) (r1, c1), (r2 – 1, c2 – 1) - Since, the problem has many overlapping sub-problem, so we need to use cache/memoization to avoid duplicate computations.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; bool hasSquareOfZeroes( vector<vector< int > >& matrix, int r1, int c1, int r2, int c2, unordered_map<string, bool >& cache); bool isSquareOfZeroes( vector<vector< int > >& matrix, int r1, int c1, int r2, int c2); // Function checks if square // with all 0's in boundary // exists in the matrix bool squareOfZeroes( vector<vector< int > > matrix) { int lastIdx = matrix.size() - 1; unordered_map<string, bool > cache; return hasSquareOfZeroes( matrix, 0, 0, lastIdx, lastIdx, cache); } // Function iterate inward in // the matrix and checks the // square obtained and memoize/cache // the result to avoid duplicate computation // r1 is the top row, // c1 is the left col // r2 is the bottom row, // c2 is the right bool hasSquareOfZeroes( vector<vector< int > >& matrix, int r1, int c1, int r2, int c2, unordered_map<string, bool >& cache) { if (r1 >= r2 || c1 >= c2) return false ; string key = to_string(r1) + '-' + to_string(c1) + '-' + to_string(r2) + '-' + to_string(c2); if (cache.find(key) != cache.end()) return cache[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 checks if the // boundary of the square // consists of 0's bool isSquareOfZeroes( vector<vector< int > >& matrix, int r1, int c1, int r2, int c2) { for ( int row = r1; row < r2 + 1; row++) { if (matrix[row][c1] != 0 || matrix[row][c2] != 0) return false ; } for ( int col = c1; col < c2 + 1; col++) { if (matrix[r1][col] != 0 || matrix[r2][col] != 0) return false ; } return true ; } // Driver Code int main() { vector<vector< int > > 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 } }; int ans; ans = squareOfZeroes(matrix); if (ans == 1) { cout << "True" << endl; } else { cout << "False" << endl; } } |
Java
// Java implementation of the above approach import java.io.*; import java.util.*; class GFG { // Function checks if square // with all 0's in boundary // exists in the matrix static int squareOfZeroes( int [][] matrix) { int lastIdx = matrix.length - 1 ; Map<String, Boolean> cache = new HashMap<String, Boolean>(); return (hasSquareOfZeroes(matrix, 0 , 0 , lastIdx, lastIdx, cache)) ? 1 : 0 ; } // Function iterate inward in // the matrix and checks the // square obtained and memoize/cache // the result to avoid duplicate computation // r1 is the top row, // c1 is the left col // r2 is the bottom row, // c2 is the right static boolean hasSquareOfZeroes( int [][] matrix, int r1, int c1, int r2, int c2, Map<String, Boolean> cache) { if (r1 >= r2 || c1 >= c2) return false ; String key = r1 + "-" + c1 + "-" + r2 + "-" + c2; if (cache.containsKey(key)) return cache.get(key); cache.put( 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.get(key); } // Function checks if the // boundary of the square // consists of 0's static boolean isSquareOfZeroes( int [][] matrix, int r1, int c1, int r2, int c2) { for ( int row = r1; row < r2 + 1 ; row++) { if (matrix[row][c1] != 0 || matrix[row][c2] != 0 ) return false ; } for ( int col = c1; col < c2 + 1 ; col++) { if (matrix[r1][col] != 0 || matrix[r2][col] != 0 ) return false ; } return true ; } // Driver Code public static void main(String[] args) { int [][] 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 } }; int ans; ans = squareOfZeroes(matrix); if (ans == 1 ) { System.out.println( "True" ); } else { System.out.println( "False" ); } } } // This code is contributed by jitin |
Python3
# Python3 implementation of the above approach # Function checks if square # with all 0's in boundary # exists in the matrix def squareOfZeroes(): global matrix, cache lastIdx = len (matrix) - 1 return hasSquareOfZeroes( 0 , 0 , lastIdx, lastIdx) # Function iterate inward in # the matrix and checks the # square obtained and memoize/cache # the result to avoid duplicate computation # r1 is the top row, # c1 is the left col # r2 is the bottom row, # c2 is the right def hasSquareOfZeroes(r1, c1, r2, c2): global matrix, cache if (r1 > = r2 or c1 > = c2): return False key = ( str (r1) + '-' + str (c1) + '-' + str (r2) + '-' + str (c2)) if (key in cache): return cache[key] cache[key] = (isSquareOfZeroes(r1, c1, r2, c2) or hasSquareOfZeroes(r1 + 1 , c1 + 1 , r2 - 1 , c2 - 1 )) cache[key] = (cache[key] or hasSquareOfZeroes(r1, c1 + 1 , r2 - 1 , c2) or hasSquareOfZeroes(r1 + 1 , c1, r2, c2 - 1 )) cache[key] = (cache[key] or hasSquareOfZeroes(r1 + 1 , c1 + 1 , r2, c2) or hasSquareOfZeroes(r1, c1, r2 - 1 , c2 - 1 )) return cache[key] # Function checks if the # boundary of the square # consists of 0's def isSquareOfZeroes(r1, c1, r2, c2): global matrix for row in range (r1, r2 + 1 ): if (matrix[row][c1] ! = 0 or matrix[row][c2] ! = 0 ): return False for col in range (c1, c2 + 1 ): if (matrix[r1][col] ! = 0 or matrix[r2][col] ! = 0 ): return False return True # Driver Code if __name__ = = '__main__' : cache = {} 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 ] ] ans = squareOfZeroes() if (ans = = 1 ): print ( "True" ) else : print ( "False" ) # This code is contributed by mohit kumar 29 |
C#
// C# implementation of the above approach using System; using System.Collections.Generic; class GFG { // Function checks if square // with all 0's in boundary // exists in the matrix static int squareOfZeroes( int [,] matrix) { int lastIdx = matrix.GetLength(0) - 1; Dictionary< string , bool > cache = new Dictionary< string , bool >(); if (hasSquareOfZeroes(matrix, 0, 0, lastIdx,lastIdx, cache)) { return 1; } else { return 0; } } // Function iterate inward in // the matrix and checks the // square obtained and memoize/cache // the result to avoid duplicate computation // r1 is the top row, // c1 is the left col // r2 is the bottom row, // c2 is the right static bool hasSquareOfZeroes( int [,] matrix, int r1, int c1, int r2, int c2, Dictionary< string , bool > cache) { if (r1 >= r2 || c1 >= c2) { return false ; } string key = r1 + "-" + c1 + "-" + r2 + "-" + c2; if (cache.ContainsKey(key)) { return cache[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 checks if the // boundary of the square // consists of 0's static bool isSquareOfZeroes( int [,] matrix, int r1, int c1, int r2, int c2) { for ( int row = r1; row < r2 + 1; row++) { if (matrix[row,c1] != 0 || matrix[row,c2] != 0) { return false ; } } for ( int col = c1; col < c2 + 1; col++) { if (matrix[r1,col] != 0 || matrix[r2,col] != 0) { return false ; } } return true ; } // Driver Code static public void Main () { int [,] 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 }}; int ans; ans = squareOfZeroes(matrix); if (ans == 1) { Console.WriteLine( "True" ); } else { Console.WriteLine( "False" ); } } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // Javascript implementation of the above approach // Function checks if square // with all 0's in boundary // exists in the matrix function squareOfZeroes( matrix) { var lastIdx = matrix.length - 1; var cache = new Map(); return hasSquareOfZeroes( matrix, 0, 0, lastIdx, lastIdx, cache); } // Function iterate inward in // the matrix and checks the // square obtained and memoize/cache // the result to avoid duplicate computation // r1 is the top row, // c1 is the left col // r2 is the bottom row, // c2 is the right 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 checks if the // boundary of the square // consists of 0' s 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 ; } // Driver Code 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( "True" ); } else { document.write( "False" ); } </script> |
True
Time Complexity: O(N^4), as we are using nested loops for traversing N^4 times.
Space Complexity: O(N^3), as we are using extra space.
Efficient Approach: In order to optimize the above approach, we need to follow the below steps:
- We need to precompute two values for every element in the matrix: the number of 0s to the right of each element (including the element itself) and the number of 0s below each element (including the element itself).
- We can compute these values by iterating through the matrix starting at the bottom right corner and moving way up by traversing each row from right to left.
- Once, we have computed the matrix, then we can check the boundary of square whether it is made up of all 0’s in constant time.
- To check the boundary of the square, we just need to look at the number of 0s below any square’s two top corners and the number of 0s to the right of the same square’s two left corners.
Contact Us