fork(1) download
copy 
  1.  
  2. class LargestSquare {
  3.  
  4.     private static final class Square {
  5.         private final int x, y, size;
  6.  
  7.         public Square(int x, int y, int size) {
  8.             super();
  9.             this.x = x;
  10.             this.y = y;
  11.             this.size = size;
  12.         }
  13.  
  14.         @Override
  15.         public String toString() {
  16.             return String.format("Square at (%d,%d) is size %d", x, y, size);
  17.         }
  18.  
  19.     }
  20.  
  21.     public static void main(String[] args) {
  22.         int[][] matrix = {
  23.                 {1, 0, 1, 0, 1},
  24.                 {1, 1, 1, 0, 1},
  25.                 {1, 0, 1, 1, 1},
  26.                 {1, 0, 1, 1, 1},
  27.                 {1, 0, 1, 1, 1}
  28.             };
  29.  
  30.         Square sq = getLargestSquare(matrix);
  31.  
  32.         System.out.println("Largest square: " + sq);
  33.     }
  34.  
  35.     private static Square getLargestSquare(int[][] matrix) {
  36.         if (matrix == null || matrix.length == 0) {
  37.             return null;
  38.         }
  39.  
  40.         final int height = matrix.length;
  41.         final int width = matrix[0].length;
  42.  
  43.         Square max = null;
  44.  
  45.         // cheat, here, and use the first matrix row as 'current'
  46.         // this will become 'previous' in the loop, and will not be changed.
  47.         // note that the y-loop starts from 1, not 0.
  48.         int[] previous = null;
  49.         int[] current = matrix[0];
  50.  
  51.         for (int y = 1; y < height; y++) {
  52.             // prepare the memoization space.
  53.             // Forget the previous, move current back, and make a new current
  54.             previous = current;
  55.             current = new int[width];
  56.             for (int x = 0; x < width; x++) {
  57.                 if (matrix[y][x] == 1) {
  58.                     int span = 1;
  59.                     if (x > 0) {
  60.                         // no need to check the left-most column, if set, it is always size 1.
  61.                         span = 1 + Math.min(current[x - 1], Math.min(previous[x], previous[x - 1]));
  62.                     }
  63.                     if (max == null || span > max.size) {
  64.                         // because we find the max at x, and y, which are the bottom-right,
  65.                         // we need to subtract the span to get to the top-left instead.
  66.                         max = new Square(x - span + 1, y - span + 1, span);
  67.                     }
  68.                     current[x] = span;
  69.                 }
  70.             }
  71.         }
  72.  
  73.         return max;
  74.     }
  75.  
  76. }
  77.  
Success #stdin #stdout 0.11s 320256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Largest square: Square at (2,2) is size 3
https://ideone.com/qVahlz
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!