When to use iterative development? You should use iterative development only on projects that you
want to succeed

Largest Square Sub Matrix with all 1's

Introduction:

Welcome back, dear reader. So, in this article we are going to discuss a very interesting problem
called the LARGEST SQUARE SUB MATRIX WITH ALL 1's. What does this question say?

We are given a matrix of size n x m as the input. The matrix has only 0's and 1's as its values. We
are required to print the size of the Largest Square matrix within this matrix whose all values are
1. For instance, consider the example shown below:

So, in the example shown above, the largest square matrix with all 1's is of size 3. Hence, we
printed 3 as the answer. If we were asked the largest matrix, then the answer would have been
different as shown in the image below:

But, we just have to tell the size of a square matrix with all 1's and it should be the largest.
We recommend you refer to the video to understand the question completely and clear your
doubts about it if any. We also suggest that you try to solve this problem on your own first and
then go to the solution. This will build your concepts strong.

Approach:

Time Complexity:

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

Space Complexity:

O(n x m)

Explanation:

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

1.Storage and Meaning:

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.

2.Direction of solving:

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.

3. Traverse and solve:

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

import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int m =scn.nextInt();
int[][] arr = new int[n][m];
for(int i = 0 ; i < n; i++){ for(int j=0 ; j < m; j++){ arr[i][j]=scn.nextInt(); } }
System.out.println(solution(arr)); } public static int solution(int[][] arr) { int[][] dp=new
int[arr.length][arr[0].length]; int ans=0; for(int i=arr.length - 1; i>= 0; i--){
for(int j = arr[0].length - 1; j >= 0; j--){
if(arr[i][j] == 0){
dp[i][j] = 0;
}else{
if(i == arr.length - 1 || j == arr[0].length - 1){
dp[i][j] = 1;
}else{
dp[i][j] = Math.min(dp[i + 1][j + 1], Math.min(dp[i + 1][j], dp[i][j + 1])) + 1;
}
}
ans = Math.max(ans,dp[i][j]);
}
}
return ans;
}
}

java;
true";

So, dear reader, we hope that you have understood everything. The code above is written and explained
in the solution video (20:38 onwards). We recommend you refer to it if you have any doubts regarding
the code. Let us now discuss the time and space complexity of this code.

Time and Space Complexity Analysis:

Time Complexity:The time complexity of this code is O(n x m) as we have traversed a 2-D
matrix to solve the problem by filling the matrix and also to find the maximum value from that
matrix later.

Space Complexity: The space Complexity of the above solution is also O(n x m) as we have
created a 2-d matrix to solve the problem.
So, dear reader, we hope that you have understood everything. You may refer to the complete solution
video to clear all your doubts if any. With this, we have completed our discussion.