Largest Subsquare

a) There is a square of nxn size which is comprised of n-square 1x1 squares.

Some of these 1x1 squares are colored. Find the biggest sub square which is not colored.
b) Also asked to extend it to find the biggest area rectangle.

Solution1:
1. take the colored squares as 0 and the non-colored squares as 1. then form a n*n matrix 'a'. 
2. now we have to find the largest square matrix having all 1's. 
3. fill up the 1st row of the result (n*n) matrix as the matrix 'a'. 
4. then from the second row on wards 
4.1. if you find a[i][j] == 0 then res[i][j] = 0. 
4.2. else res[i][j] = min(res[i-1][j], res[i][j-1], res[i-1][j-1])+1. 
5. after creating the 'res' matrix the size of largest uncolored square will be the largest element in the 'res' matrix. 

Run time complexity is O(n^2), space complexity is O(n^2).

public class LargestSubmatrix {
    public static void main(String[] args) {
        int[][] arr = {{0,1,1,0,1,0},
                       {1,1,0,0,1,0},
                       {0,1,1,1,0,1},
                       {0,1,1,0,0,1},
                       {0,1,1,1,0,1}};
        int col = arr[0].length;
        int row = arr.length;
        int [][] res = new int [row][col];
        for (int i = 0; i < col; i++) {
            res[0][i] = arr[0][i];
        }
        for (int i = 0; i < row; i++) {
            res[i][0] = arr[i][0];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (arr[i][j] == 1) {
                    res[i][j] = Math.min(Math.min(res[i][j-1], res[i-1][j]), res[i-1][j-1]) + 1;
                } else {
                    res[i][j] = 0;
                }
            }
        }
 
        System.out.println("the distance matrix is : ");
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                System.out.print(res[i][j]+" ");
            }
        System.out.println("");
        }
 
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                max = Math.max(max, res[i][j]);
            }
        }
        System.out.println("max square : "+max);
    }
}