Max Black Square

Moderate
0/80
Average time to solve is 30m
5 upvotes
Asked in companies
D.E.ShawLowe's India

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2
1 1
1 1
5
1 1 1 0 0
0 1 1 1 1
0 1 0 1 1
0 1 1 1 1
0 1 1 0 1
Sample Output 1:
2
3
Explanation For Sample Input 1:
For the first test case, the maximum square submatrix surrounded by all 1’s starts at (0, 0) and ends at (1, 1). And the size of this square matrix is 2.

For the second test case, the maximum square submatrix surrounded by all 1’s starts at (1, 1) and ends at (3, 3). And the size of this square matrix is 3.
Sample Input 2:
2
3
1 0 1
0 1 0
1 0 1
5
1 1 1 0 1
0 0 0 0 0
1 1 0 0 1 
1 1 1 0 1 
0 0 0 0 0
Sample Output 2:
1
2
Hint

Try every possible square submatrix.

Approaches (2)
Brute Force

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.
Time Complexity

O(N^4), where N is the size of the matrix.

 

Since, we are fixing 3 coordinates (x2, y2, x1), which is of order N^3, and then checking for the corner elements which are of order N. Hence, the overall time complexity is O(N^4).

Space Complexity

O(1).

 

Since we are using constant extra space.

Code Solution
(100% EXP penalty)
Max Black Square
Full screen
Console