[Java] Find biggest square in matrix

Given an input matrix of only 0s and 1s, find the biggest square composed only of 0s. The square must be parallel to the matrix edges.

We could solve this in O(MxN)^2 time and constant space, by checking for each cell the biggest square that can be formed starting from there, but since we know a bit of dynamic programming, we decide that O(MxN) extra space is worth reducing the time to O(MxN) :)

The problem can be solved by decomposing it in smaller subproblems considering as base case the single cell; if it contains a 0, it's a valid 1x1 square.
From there, we expand considering the cell as either the BOTTOM-RIGHT corner of a bigger square which is valid if and only if the VALID (left, top, top-left) neighbours are 0s as well OR the TOP-LEFT cell of a new square starting there. Consider these cases:

0

00
00

000
000
000

The black 0 is the one we are evaluating now, the red zeroes are the neighbours we are considering for our case and the green zeroes are the cells we already evaluated before, when we were applying the logic to each of the neighbours we are considering now. The DP matrix for each of those situations would be:

1

1 1
1 2

1 1 1
1 2 2
1 2 3

Where each number indicates the number of extensions (length of one side) the particular cell contributes to the biggest square having the current cell as BOTTOM-RIGHT corner of it.

The solution would then be that number, squared.

We can only extend a square starting from row and column number 1, otherwise we are 1D square of course.

Therefore, for any 2x2 or bigger matrix at each step, if we are a 0, we add us (+1) to the MIN of the best result from our VALID neighbours (left, top-left, top). MIN because we are NOT extending any square UNLESS our neighbours are part of a bigger square as well. Eg:

000
000
100

In this case, that bold green 1 made it impossible to form a complete 3x3 square, therefore when evaluating the bold red zero, we would realize that at best it can contribute to a square involving it in any position EXCEPT the BOTTOM-RIGHT, due to the proximity of the 1.
The bold zero would receive this information, together with the one from its blue neighbours (top and top-left) that could themselves be part of a bigger square, and realize that it can only extend the square he is in by 1. The DP matrix for this would be, step by step,

1

1 1
1 2

1 1 1
1 2 2
0 1 2

Where it's easy to realize we actually have three valid 2x2 squares, starting as TOP-LEFT corner at each of the marked positions.

You can check my implementation of getBiggestSquare on my Gist alongside some test cases in BiggestSquareJTests.