Max Black Square

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.

Approach : The idea is to create two matrices hor[][] and ver[][]. Where hor[x][y] represents the contiguous number of 1’s, taken horizontally till the point (x, y) and ver[x][y] represents the contiguous number of 1’s, taken vertically till the point (x, y). Now, for every possible square ending at (x, y). We find the minimum of hor[x][y], ver[x][y] let’s say this maxPossibleSize. Now, the condition for row x and column y is fulfilled, we’ll definitely have a maxPossibleSize number of ones in row x and column y, in a square ending at index (x,y). Now, to check for the other two corners we can try for every possible square from k = maxPossibleSize to 0, and check if ver[x][y - k + 1] >= k and hor[x - k + 1][y] >= k, if it is update the ans accordingly.

The algorithm is as follows :

1. Declare an ans variable to 0, to store the max size square matrix surrounded by ones.
2. Declare two tables hor[N][N], ver[N][N].
3. Iterate from i = 0 to N,
4. Iterate from j = 0 to N,
   • If matrix[i][j] is equal to 1, then set hor[i][j] = hor[i][j-1] + 1.
   • Else , set hor[i][j] = 0.
5. Iterate from j = 0 to N,
   • Iterate from i = 0 to N,
     • If matrix[i][j] is equal to 1, then set ver[i][j] = ver[i-1][j] + 1.
     • Else , set  ver[i][j] = 0.
6. Then, iterate through each cell of the matrix and fix the current cell as the bottom right corner of the subsquare -
7. Iterate from x = 0 to N,
   • Iterate from y = 0 to N,
     • Declare a variable maxPossibleSize to min(hor[x][y], ver[x][y]).
     • Now, the condition for row x and column y is fulfilled, we’ll definitely have a maxPossibleSize number of ones in row x and column y, in a square ending at index (x,y).
     • Checking for the other two corners.
     • Iterate from k = maxPossibleSize to 1,
       1. If ver[x][y - k + 1] >= k and hor[x - k + 1][y] >= k, this verifies all the corner conditions, since ver[x][y - k + 1] stores number of contiguous ones, taken vertically ending at (x, y - k +1)  which will be the bottom left corner of the subsquare and hor[x - k + 1][y], stores number of contiguous ones, taken horizontally ending at (x, y - k +1) which will be the top right corner of the subsquare,
          • Update ans = max(ans, k).
          • Break, because we are interested in maximum k.
8. Return the ans.