O(n x m) where n and m are the dimension of the input matrix

O(n x m)

Let us start with the dynamic programming method of 3 steps.

We will make a 2-D array of the same size as that of the input matrix. This array will be of type integer. What will this array represent?

Each element of this matrix will store the largest possible square matrix with all 1's that can be made by selecting the current cell as the top-left corner of the square matrix. You may refer to the solution video to understand the store and meaning step if you have any doubts about it.

If you have understood the storage and meaning step properly, you would be very comfortable guessing the direction of solving. The smallest problem will be at the position where we can make the smallest possible square matrix with all 1's. So, if we take the last element of the matrix as our top-left corner, this will be our smallest problem. The largest problem will be if the first element of the matrix is chosen as the top-left corner of the matrix. So, we will start solving from dp[n-1][m-1] till dp[0][0] and we will move row-wise.

Before we start traversing this matrix, let us first discuss some cases that we can directly complete.

Case: If matrix[i][j]=0

If matrix[i][j]=0, dp[i][j] will also be equal to 0 as the top-left corner is 0, no square matrix can be formed using this corner. (Think!!!) So, wherever we have 0's in the matrix, we will have 0's at all those positions in our dp matrix too.

Case: if i=n-1

If we are in the last row, we have already filled into the dp matrix all the positions where 0 was present in the array. Now, we have to fill the positions where 1 value was present. In the last row, the maximum size of the square matrix can be 1 only, otherwise the matrix will go outside the dp matrix. (Why? Think!!!!) Hence, if i=n-1, put 1 in the dp matrix corresponding to the 1's in the input matrix.

Case: if j=m-1

If we are in the last column, the dp matrix will contain 1 at those positions where we have 1 in the input matrix. The reason is the same as the case with the last row given above i.e. the matrix will go out of the dp matrix boundaries. The dp matrix partially filled following all the three above conditions is shown in the image below:

Let us now try to traverse and solve the rest of the matrix.

What of the problem

Let us tell you what we are going to do. If we are at dp[i][j], we will compare dp[i][j+1], dp[i+1][j], and dp[i+1][j+1]. The answer to be kept at dp[i][j] is the minimum out of these 3 plus 1. Why? Think about this!!! We will discuss it in the "why" of the problem.

How of the problem

So, we know the "what" of the problem. Let us now traverse the matrix so that we can implement the "how" of this problem. We are initially at dp[3][4]. We compare the next value in the same row, the next value in the same column and the diagonally next value with each other i.e. dp[3][5], dp[4][4] and dp[4][5] respectively. The minimum value out of this is 1. So, we will put 1 at dp[3][4].

Let us now fill dp[3][3]. Here, the minimum value comes out to be 1, so we will put 1+1=2 at dp[3][3] meaning we can have a maximum of 2 sized square matrix of all 1's keeping dp[3][3] as the top-left corner.

So, dear reader, you have understood the procedure that we have to follow at every cell in this matrix. So, let us continue that procedure and fill the entire matrix. We request you to fill this matrix completely on your own.

So, the maximum value in this dp matrix will be our answer. We can see that there are 2 places where we have the max value=3. This means that at both of these places, we can make a square matrix of max size=3. This is shown in the image below:

So, let us now understand the "why" of the problem i.e. why we followed the above procedure.

Why of the problem.

Let us take an example as shown in the image below:

Let us consider only the values shown in this dp matrix. Say we have 2 at dp[0][1] meaning that we can draw a square matrix of max size=2 taking dp[0][1] as the top-left corner and so on for other values as well. So, what does dp[0][1] tell us? Have a look at the image shown below:

The area marked with square shows the 2 sized square matrix i.e. all the values in which we have drawn the square will be 1. The stars show that any of those positions marked with a star can be a 0. Why? This is because only if even one of those values is 0 even then, the max size of the matrix starting at dp[0][1] will be 2. Therefore, we may have any of those values 0 that are marked with a yellow star. Now, let us do the same for dp[1][1].

So, we can see that the possibility of creation of a 3 sized square matrix at dp[1][1], removed many stars from the 3rd column and from the 2nd row. But, there are more stars now which indicate that any of those positions might contain 0 value and that is the reason for the maximum size of the matrix starting at dp[1][1] to be 3. The star at dp[0][3] still represents a 00 because of which the matrix at dp[0][1] could not be of size 3. Let us move to dp[1][0].

So, we have drawn all the three other matrices. Let us answer 2 questions quickly.

Why did our answer was minimum of three values?

The answer was a minimum of three values as you can see that the minimum sized square matrix has a star at its right i.e. the value there is 0. This 0 is stopping this matrix from becoming of size 3. This is also the reason that the matrix starting from dp[0][0] cannot be of size 4 as there is a 0 kept at dp[0][3]. Hence, you will notice that the reason which stops the minimum sized matrix to grow will also be the reason for stopping our matrix to grow in size. Hence, we took the minimum.

Why did we add 1 to the minimum value?

This is very simple. The minimum value is one step ahead of us either diagonally or row-wise or column-wise. Hence, we have to consider the cell we are at also to form the matrix. Hence, we added 1 to the answer. So, dear reader, we hope that you are clear with all the things now. We recommend you refer to the solution video to understand the process that we have done above and also the complete explanation of "what", "how", and why of the problem. Now that we have talked about everything, let us write the code.

JAVA CODE