Find largest block in matrix

(Largest block)

Given a square matrix with the elements 0 or 1, write a program to find a maximum square submatrix whose elements are all 1s. Your program should prompt the user to enter the number of rows in the matrix. The program then displays the location of the first element in the maximum square submatrix and the number of the rows in the submatrix.

Here is a sample run:

Enter the number of rows in the matrix:

5

Enter the matrix row by row:

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

The maximum square submatrix is at (2, 2) with size 3

My solution is this:

(I didn't make it prompt an input because my computer hasn't arrived and the ide on my phone can't use text files as input. I didn't want to type in all the numbers to try different inputs.)

```
public class Main {
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}
};

//Check each location for sub-squares
int[] largestBlock = new int[3];
int maxSize = 0;
for (int i = 0; i maxSize) {
largestBlock[0] = i;
largestBlock[1] = j;
maxSize = squareSize;
}
}
}

largestBlock[2] = maxSize + 1;
System.out.println("The first largest sub-square is located at (" + largestBlock[0]
+ ", " + largestBlock[1] + ") and is of size " + largestBlock[2]);
}

public static boolean isSquare(int row, int column, int squareSize, int[][] matrix) {
int size = squareSize + 2;

if (row + size - 1 >= matrix.length || column + size - 1 >= matrix.length)
return false;

for (int i = row; i < row + size; i++) {
for (int j = column; j < column + size; j++) {
if (matrix[i][

There is a neat trick in many computer algorithms called memoization - the remembering of critical aspects of one computation, to reuse them in another. Memoization can help a lot in this problem. To explain this, consider the basic algorithm you have...

• start at the top-left of the matrix

• scan every position in the matrix

• for each position, check whether it is the top-left of an increasing square of set values.

• keep track of the maximum.

This process is effective, but not very efficient. What if I were to tell you there is a way to solve the problem without having to do step 3, just by remembering what you did in previous iterations of step 1 and 2?

The way we do things, is to remember the size of previously-computed squares of set positions. We remember the previous row, and the current row only. No need to remember more than that....

Looking at your example:

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

It is a matrix of size 5. We create two temporary arrays to record the previous and current memoization:

int[] previous = new int[5];
int[] current = new int[5];

Now, we compute the values for the current memoization - it works like this:

• if the cell in the current column is not set, then the square at the current position is size 0.

-
if the cell is set, then it is 1 more than the smallest square above , above-left, or left of it. This needs a picture.....

As you can see, I have marked 3 squares - red, blue, and purple. Each of them is 2x2. The position at the bottom right, is the end of the 3x3 square. it is 1 + the minimum size of the blue, red, and purple squares.

So, it becomes relatively simple to identify squares, we only need to check three values for each cell.... the code is surprisingly simple, even if the concept is hard...

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  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;
}

Note that I have created a container-class Square to hold the result:

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
    public String toString() {
        return String.format("Square at (%d,%d) is size %d", x, y, size);
    }

}

Additionally, the main method is now simple:

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);
}

You can see the whole thing on ideone: Largest Square

StackExchange Code Review Q#88555, answer score: 6