class LargestSquare {
private static final class Square {
private final int x, y, size;
public Square(int x, int y, int size) {
super();
this.x = x;
this.y = y;
this.size = size;
}
@Override
return String.
format("Square at (%d,%d) is size %d", x, y, size
); }
}
public static void main
(String[] args
) { int[][] matrix = {
{1, 0, 1, 0, 1},
{1, 1, 1, 0, 1},
{1, 0, 1, 1, 1},
{1, 0, 1, 1, 1},
{1, 0, 1, 1, 1}
};
Square sq = getLargestSquare(matrix);
System.
out.
println("Largest square: " + sq
); }
private static Square getLargestSquare(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return null;
}
final int height = matrix.length;
final int width = matrix[0].length;
Square max = null;
// cheat, here, and use the first matrix row as 'current'
// this will become 'previous' in the loop, and will not be changed.
// note that the y-loop starts from 1, not 0.
int[] previous = null;
int[] current = matrix[0];
for (int y = 1; y < height; y++) {
// prepare the memoization space.
// Forget the previous, move current back, and make a new current
previous = current;
current = new int[width];
for (int x = 0; x < width; x++) {
if (matrix[y][x] == 1) {
int span = 1;
if (x > 0) {
// no need to check the left-most column, if set, it is always size 1.
span
= 1 + Math.
min(current
[x
- 1],
Math.
min(previous
[x
], previous
[x
- 1])); }
if (max == null || span > max.size) {
// because we find the max at x, and y, which are the bottom-right,
// we need to subtract the span to get to the top-left instead.
max = new Square(x - span + 1, y - span + 1, span);
}
current[x] = span;
}
}
}
return max;
}
}
CmNsYXNzIExhcmdlc3RTcXVhcmUgewogICAgCiAgICBwcml2YXRlIHN0YXRpYyBmaW5hbCBjbGFzcyBTcXVhcmUgewogICAgICAgIHByaXZhdGUgZmluYWwgaW50IHgsIHksIHNpemU7CgogICAgICAgIHB1YmxpYyBTcXVhcmUoaW50IHgsIGludCB5LCBpbnQgc2l6ZSkgewogICAgICAgICAgICBzdXBlcigpOwogICAgICAgICAgICB0aGlzLnggPSB4OwogICAgICAgICAgICB0aGlzLnkgPSB5OwogICAgICAgICAgICB0aGlzLnNpemUgPSBzaXplOwogICAgICAgIH0KICAgICAgICAKICAgICAgICBAT3ZlcnJpZGUKICAgICAgICBwdWJsaWMgU3RyaW5nIHRvU3RyaW5nKCkgewogICAgICAgICAgICByZXR1cm4gU3RyaW5nLmZvcm1hdCgiU3F1YXJlIGF0ICglZCwlZCkgaXMgc2l6ZSAlZCIsIHgsIHksIHNpemUpOwogICAgICAgIH0KICAgICAgICAKICAgIH0KICAgIAogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIGludFtdW10gbWF0cml4ID0gewogICAgICAgICAgICAgICAgezEsIDAsIDEsIDAsIDF9LAogICAgICAgICAgICAgICAgezEsIDEsIDEsIDAsIDF9LAogICAgICAgICAgICAgICAgezEsIDAsIDEsIDEsIDF9LAogICAgICAgICAgICAgICAgezEsIDAsIDEsIDEsIDF9LAogICAgICAgICAgICAgICAgezEsIDAsIDEsIDEsIDF9CiAgICAgICAgICAgIH07CiAgICAgICAgCiAgICAgICAgU3F1YXJlIHNxID0gZ2V0TGFyZ2VzdFNxdWFyZShtYXRyaXgpOwogICAgICAgIAogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiTGFyZ2VzdCBzcXVhcmU6ICIgKyBzcSk7CiAgICB9CgogICAgcHJpdmF0ZSBzdGF0aWMgU3F1YXJlIGdldExhcmdlc3RTcXVhcmUoaW50W11bXSBtYXRyaXgpIHsKICAgICAgICBpZiAobWF0cml4ID09IG51bGwgfHwgbWF0cml4Lmxlbmd0aCA9PSAwKSB7CiAgICAgICAgICAgIHJldHVybiBudWxsOwogICAgICAgIH0KICAgICAgICAKICAgICAgICBmaW5hbCBpbnQgaGVpZ2h0ID0gbWF0cml4Lmxlbmd0aDsKICAgICAgICBmaW5hbCBpbnQgd2lkdGggPSBtYXRyaXhbMF0ubGVuZ3RoOwogICAgICAgIAogICAgICAgIFNxdWFyZSBtYXggPSBudWxsOwogICAgICAgIAogICAgICAgIC8vIGNoZWF0LCBoZXJlLCBhbmQgdXNlIHRoZSBmaXJzdCBtYXRyaXggcm93IGFzICdjdXJyZW50JwogICAgICAgIC8vIHRoaXMgd2lsbCBiZWNvbWUgJ3ByZXZpb3VzJyBpbiB0aGUgbG9vcCwgYW5kIHdpbGwgbm90IGJlIGNoYW5nZWQuCiAgICAgICAgLy8gbm90ZSB0aGF0IHRoZSB5LWxvb3Agc3RhcnRzIGZyb20gMSwgbm90IDAuCiAgICAgICAgaW50W10gcHJldmlvdXMgPSBudWxsOwogICAgICAgIGludFtdIGN1cnJlbnQgPSBtYXRyaXhbMF07CiAgICAgICAgCiAgICAgICAgZm9yIChpbnQgeSA9IDE7IHkgPCBoZWlnaHQ7IHkrKykgewogICAgICAgICAgICAvLyBwcmVwYXJlIHRoZSBtZW1vaXphdGlvbiBzcGFjZS4KICAgICAgICAgICAgLy8gRm9yZ2V0IHRoZSBwcmV2aW91cywgbW92ZSBjdXJyZW50IGJhY2ssIGFuZCBtYWtlIGEgbmV3IGN1cnJlbnQKICAgICAgICAgICAgcHJldmlvdXMgPSBjdXJyZW50OwogICAgICAgICAgICBjdXJyZW50ID0gbmV3IGludFt3aWR0aF07CiAgICAgICAgICAgIGZvciAoaW50IHggPSAwOyB4IDwgd2lkdGg7IHgrKykgewogICAgICAgICAgICAgICAgaWYgKG1hdHJpeFt5XVt4XSA9PSAxKSB7CiAgICAgICAgICAgICAgICAgICAgaW50IHNwYW4gPSAxOwogICAgICAgICAgICAgICAgICAgIGlmICh4ID4gMCkgewogICAgICAgICAgICAgICAgICAgICAgICAvLyBubyBuZWVkIHRvIGNoZWNrIHRoZSBsZWZ0LW1vc3QgY29sdW1uLCBpZiBzZXQsIGl0IGlzIGFsd2F5cyBzaXplIDEuCiAgICAgICAgICAgICAgICAgICAgICAgIHNwYW4gPSAxICsgTWF0aC5taW4oY3VycmVudFt4IC0gMV0sIE1hdGgubWluKHByZXZpb3VzW3hdLCBwcmV2aW91c1t4IC0gMV0pKTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgaWYgKG1heCA9PSBudWxsIHx8IHNwYW4gPiBtYXguc2l6ZSkgewogICAgICAgICAgICAgICAgICAgICAgICAvLyBiZWNhdXNlIHdlIGZpbmQgdGhlIG1heCBhdCB4LCBhbmQgeSwgd2hpY2ggYXJlIHRoZSBib3R0b20tcmlnaHQsCiAgICAgICAgICAgICAgICAgICAgICAgIC8vIHdlIG5lZWQgdG8gc3VidHJhY3QgdGhlIHNwYW4gdG8gZ2V0IHRvIHRoZSB0b3AtbGVmdCBpbnN0ZWFkLgogICAgICAgICAgICAgICAgICAgICAgICBtYXggPSBuZXcgU3F1YXJlKHggLSBzcGFuICsgMSwgeSAtIHNwYW4gKyAxLCBzcGFuKTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgY3VycmVudFt4XSA9IHNwYW47CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgCiAgICAgICAgcmV0dXJuIG1heDsKICAgIH0KCn0K