/* Author: Denise Roßberg Date: 06.05.2020 Program: Maximum Area of Square Challenge by Bobby Fischer (see comments). Given a 2D binary matrix filled with 0’s and 1’s, find the largest area of square containing only 1’s. Input: 1, 0, 1, 0, 0 1, 0, 1, 1, 1 1, 1, 1, 1, 1 1, 0, 0, 1, 0 Output: 4 Explanation: The ones that form the largest square lies on (1,2), (1,3), (2,2), (2,3) Source: https://youtu.be/_Lf1looyJMU */ import java.util.Random; public class Program { public static int[][] getMatrix(){ Random rand = new Random(); int sizeA = rand.nextInt(19) + 4; int sizeB = rand.nextInt(19) + 4; int[][] matrix = new int[sizeA][sizeB]; for(int i = 0; i < sizeA; i++){ for(int j = 0; j < sizeB; j++){ matrix[i][j] = rand.nextInt(2); } } return matrix; } public static void printMatrix(int[][] matrix){ for(int i = 0; i < matrix.length; i++){ for(int j = 0; j < matrix[i].length; j++){ System.out.print(matrix[i][j] + " "); } System.out.println(); } } private static int getMin(int a, int b, int c){ if(a <= b && a <= c) return a; if(b <= a && b <= c) return b; return c; } public static int getMaxArea(int[][] matrix){ int[][] arr = new int[matrix.length][matrix[0].length]; int maxArea = 0; for(int i = 0; i < matrix.length; i++){ for(int j = 0; j < matrix[i].length; j++){ //if value = 0, enter 0 to second matrix if(matrix[i][j] == 0){ arr[i][j] = 0; //if value at the upper or left border, neighbours are 0 //0 + 1 = 1 }else if(i == 0 || j == 0){ arr[i][j] = matrix[i][j]; }else{ //check upper, left and upper-left neighbour, take min value int min = getMin(arr[i - 1][j], arr[i][j - 1], arr[i - 1][j - 1]); arr[i][j] = min + matrix[i][j]; } //store largest value if(arr[i][j] > maxArea){ maxArea = arr[i][j]; } } } return maxArea * maxArea; } public static void main(String[] args) { System.out.println("test matrix:"); int[][] test = {{1,0,1,0,0}, {1,0,1,1,1}, {1,1,1,1,1}, {1,0,0,1,0}}; printMatrix(test); System.out.println(); System.out.println("maximum area of square: " + getMaxArea(test)); System.out.println(); System.out.println("random matrix:"); int[][] matrix = getMatrix(); printMatrix(matrix); System.out.println(); System.out.println("maximum area of square: " + getMaxArea(matrix)); } }

max area of square