Largest Square of 1 formed from Matrix

Largest Square of 1 formed from Matrix

  September 04, 2017    

---

Explanation :

First initialize matrix 1st row and column with original matrix value.
Start loop and check when a 1 occur then go with minimum value of left column,upper row ,upper diagonal value.

Why ?
Whenever a square is there then all of the values surrounding matrix will be atleast size of square.

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class hackerranksolutionc
 {
     public static int maxmatrixwith1(boolean mat[][],int r,int c)
{
    boolean flag=false;
int s[][]=new int[r][c];

int m=0;
for(int i=0;i<r;++i)
{
s[i][0]=(mat[i][0])?1:0;
if(s[i][0]==1)
m=1;
}
for(int i=0;i<c;++i)
{
s[0][i]=(mat[0][i])?1:0;
if(s[0][i]==1)
m=1;
}

for(int i=1;i<r;++i)
{
for(int j=1;j<c;++j)
{
if(mat[i][j])
{
   flag=true;
   s[i][j]=Math.min(s[i][j-1],Math.min(s[i-1][j],s[i-1][j-1]))+1;
m=Math.max(s[i][j],m);
}
else
s[i][j]=0;
}
}
if(flag && m==0)
return 1;
return m;
}
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   int r=ab.nextInt();
   int c=ab.nextInt();
   boolean arr[][]=new boolean[r][c];
   for(int i=0;i<r;i++)
   for(int j=0;j<c;++j)
   arr[i][j]=(ab.nextInt()==1)?true:false;
   System.out.println(maxmatrixwith1(arr,r,c));
}
}
}