Find largest block in matrix

Question

(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 < matrix.length - 1; i++) {
            for (int j = 0; j < matrix[i].length - 1; j++) {
                int squareSize = 0;
                while (isSquare(i, j, squareSize, matrix)) {
                    squareSize++;
                }
                
                if (squareSize > 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][j] != 1)
                    return false;
            }
        }
        return true;
    }
}

Answer 1

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...

1. start at the top-left of the matrix
2. scan every position in the matrix
3. for each position, check whether it is the top-left of an increasing square of set values.
4. 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:

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

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

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

Answer 2

Don't repeat work

One of the first things that leaps out at me is that you check the entire square each time, even though you only need to check the new edges.

            int squareSize = 0;
            while (isSquare(i, j, squareSize, matrix)) {
                squareSize++;
            }

You can save time by changing this just to check the row and column that you just added:

            if (isClear(matrix, i, j)) {
                continue;
            }

            int squareSize = 1;
            while (isRowSegmentSet(matrix, i + squareSize, j, squareSize)
                && isColumnSegmentSet(matrix, i, j + squareSize, squareSize - 1)
                  )
            {
                squareSize++;
            }

This works because you already know that the rest of the square is set. You only need to check the new elements. Note that our sizes are different for the two segments. This is because they contain one square in common and we only need to check it once.

public static boolean isRowSegmentSet(int[][] matrix, int row, int column, int squareSize) {
    int lastColumn = column + squareSize;
    if (lastColumn >= matrix.length) {
        return  false;
    }

    for (int i = column; i <= lastColumn; i++) {
        if (isClear(matrix, row, i)) {
            return false;
        }
    }

    return true;
}

public static boolean isClear(int[][] matrix, int row, int column) {
    return matrix[row][column] != 1;
}

Note: this also changes squareSize to represent the number of elements in a row or column. Your original code made a squareSize of 0 represent a single element square, which I found confusing. We'll have to adjust for this later.

Also, I deliberately added the block markers in the if with only a single statement. Always using them makes a certain hard to diagnose bug harder to create.

Try to avoid magic indexes

            if (squareSize > maxSize) {
                largestBlock[0] = i;
                largestBlock[1] = j;
                maxSize = squareSize;
            }
        }
    }

    largestBlock[2] = maxSize + 1;

Your largestBlock variable uses position to differentiate between the row and column. For this simple example, it works. However for any more complicated example, it's easy to mix the positions around. Is 0 the row? Or the column? Or the size? The really robust solution would be to create a class to hold this information, but if that's overkill, three variables are simpler.

    int leftCorner = 0;
    int topCorner = 0;
    int maxSize = 0;

and then the equivalent of your code:

            if (squareSize > maxSize) {
                topCorner = i;
                leftCorner = j;
                maxSize = squareSize;
            }
        }
    }

Note that we can use maxSize directly because we previously changed squareSize to the actual square size.

What if there isn't an answer?

Your code assumes that there will always be a largest set square. What if there isn't? You should notify the user of that fact.

if (maxSize > 0 ) {
    System.out.println("The first largest sub-square is located at (" + topCorner
  + ", " + leftCorner + ") and is of size " + maxSize);
} else {
    System.out.println("There are no sub-squares of this matrix that have all the elements set.");
}

Your original code would have said

The first largest sub-square is located at (0, 0) and is of size 1

Note that this assumes that largestBlock was 0 initialized, which is the default behavior for Java arrays of integer types.