Max Black Square

Posted: 28 Feb, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given a square matrix with N rows and N columns, in which each cell (pixel) is either black or white. The black pixels are represented as ‘1’ and the white pixels are represented as ‘0’.

Design an algorithm to find the maximum length of a sub-square of the matrix such that all four borders are filled with black pixels.

Input Format
The first line of input contains an integer ‘T' representing the number of test cases.

The first line of each test case contains one integer ‘N’ denoting the size of the matrix.

The next ‘N’ lines contain ‘N’ integers separated by spaces describing rows of the matrix. (each element of the matrix is either 0 or 1).
Output Format:
For each test case, on a separate line, output one integer - the maximum length of a side of a subsquare such that all four borders are filled with black pixels.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^3
MATRIX[i][j] = 0 or 1

Where ‘T’ is the number of test cases, ‘N’  is the size of the given array, and ‘MATRIX[i][j]’ denotes the j’th element of the i’th row of the matrix "MATRIX".

Time Limit: 1 sec
Approach 1

The idea is to try every possible square submatrix and check whether all the corner elements are ‘1’. A submatrix is defined by a top left corner (x1, y1) and bottom right corner (x2,y2). Since we are interested in finding a square. If we fix the bottom right corner and fix either the x or the y coordinate of the top left corner, we can calculate the other coordinate using the equation x2 - x1 = y2 - y1.

 

The algorithm is as follows :

 

  1. Declare an ans variable to 0, to store the max size square matrix surrounded by ones.
  2. Iterate from x2 = 0 to n,
  3. Iterate from y2 = 0 to n,
    • Iterate from x1 = 0 to x2,
      • Calculate y1 from, y1 = y2 - (x2 - x1).
      • If y1 < 0, then continue because we can’t have a negative index.
      • Check all the corner elements of the current square matrix are one or not.
      • Declare a boolean variable isPossible to 1, to check whether this square matrix is surrounded by one or not.
      • Iterate from i = x1 to x2,
        • If matrix[i][y1] == 0, set isPossible = 0.
      • Iterate from i = x1 to x2,
        • If matrix[i][y2] == 0, set isPossible = 0.
      • Iterate from j = y1 to y2
        1. If matrix[x1][j] == 0, set isPossible = 0.
      • Iterate from j = y1 to y2,
        1. If matrix[x2][j] == 0, set isPossible = 0.
      • If isPossible == 1, update ans = max(ans, x2 - x1 + 1). Since (x2 - x1 + 1) is the size of the current square submatrix.
  4. Return ans.
Try Problem